当前位置:Gxlcms > mysql > Mysql树型结构2种方式及相互转换_MySQL

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

时间:2021-07-01 10:21:17 帮助过:26人阅读

Mysql实现树型结构,数据库上常见有2种方式:领接表、预排序遍历树(MPTT)。
领接表方式——
主要依赖于一个 parent 字段,用于指向上级节点,将相邻的上下级节点连接起来,id 为自动递增自动,parent_id 为上级节点的 id。
领接表方式的优点在于容易理解,代码也比较简单明了。缺点则是递归中的 SQL 查询会导致负载变大,特别是需要处理比较大型的树状结构的时候,查询语句会随着层级的增加而增加,WEB 应用的瓶颈基本都在数据库方面,所以这是一个比较致命的缺点,直接导致树结构的扩展困难重重。
排序遍历树方式
现在我们来聊聊第二种方式─预排序遍历树方式(即通常所说的 MPTT,Modified Preorder Tree Traversal)。此算法是在第一种方式的基础之上,给每个节点增加一个左、右数字,用于标识节点的遍历顺序,如下图所示:

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<当前节点lft,rgt>当前节点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

处理结束;

此算法已在项目中应用,代码是有版权的,就不贴了。

人气教程排行