设为首页收藏本站
查看: 73|回复: 0

[PHP] Mysql树型结构2种方式及相互转换_MySQL

[复制链接]

论坛元老

Rank: 6Rank: 6

积分
34274
主题
17031
UID
1347
M币
67
贡献
17176

  • 发表于 2017-5-12 16:11:00 | 显示全部楼层 |阅读模式
    Mysql实现树型结构,数据库上常见有2种方式:领接表、预排序遍历树(MPTT)。
    领接表方式——
    主要依赖于一个 parent 字段,用于指向上级节点,将相邻的上下级节点连接起来,id 为自动递增自动,parent_id 为上级节点的 id。
    领接表方式的优点在于容易理解,代码也比较简单明了。缺点则是递归中的 SQL 查询会导致负载变大,特别是需要处理比较大型的树状结构的时候,查询语句会随着层级的增加而增加,WEB 应用的瓶颈基本都在数据库方面,所以这是一个比较致命的缺点,直接导致树结构的扩展困难重重。
    排序遍历树方式
    现在我们来聊聊第二种方式─预排序遍历树方式(即通常所说的 MPTT,Modified Preorder Tree Traversal)。此算法是在第一种方式的基础之上,给每个节点增加一个左、右数字,用于标识节点的遍历顺序,如下图所示:
    [i]vcq9yrXA/Q==" src="http://www.bitsCN.com/uploadfile/Collfiles/20150701/2015070110073241.gif" title="PHP+Mysql树型结构(无限分类)数据库设计的2种方式实例" />
    从根节点开始左边为 1,然后下一个节点的左边为 2,以此类推,到最低层节点之后,最低层节点的右边为其左边的数字加 1。顺着这些节点,我们可以很容易地遍历完整个树。根据上图,我们对数据表做一些改变,增加两个字段,lft 和 rgt 用于存储左右数字( left 和 right 是 MySQL 的保留字,所以改用简写)。
    可以看出,由于MPTT方式存储不仅包含隶属关系,还包括了顺序,因此在读取子树时不需递归,效率大大提高。
    下面面讨论下如何在这两着间转换.
    MPTT转领接表比较容易,只要寻找层级比当前节点小1,且lft当前节点rgt的节点,即为父节点。
    领接表转MPTT,一般直观想到的是递归生成。但是这个不是尾递归,递归层数有限制, mysql没有数组自建堆栈要用表,效率很低,怎么办?
    笔者设计了一个近似递推的算法,分享一下:
    首先确定问题:领接表结构(id,pid),目标MPTT表结构(id,lvl,lft,rgt)。
    为处理需要,MPTT表增加cnt、seq字段,用于记录节点及其子节点的个数、在MPTT中遍历的序号。
    处理过程算法如下:
    1】根节点,转入MPTT表,令lvl=1,lft=1,rgt=null,cnt=null,seq=1;
    2】逐层处理p的子节点,lvl+1;
    3】从最底层(lvl最大)向上(lvl递减)处理各层的节点,cnt=子节点的cnt数+1
    4】从最上曾(lvl=1)向下(lvl递增)处理各层的节点,seq=父节点seq+ sum(id小于本节点的兄弟节点的cnt)+1
    5】对每一个节点,lft=seq*2-lvl,rgt = lft +cnt *2 -1
    处理结束;
    此算法已在项目中应用,代码是有版权的,就不贴了。
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    在我站开通SVIP可同时获得17个站点VIP资源 立即登录 立即注册
    快速回复 返回顶部 返回列表