你在用递归查询Mysql的树形结构吗？

通常树形结构的存储，是在子节点上存储父节点的编号来确定各节点的父子关系，例如这样的组织结构：

与之对应的表数据(department)：

idnameparent_idlevel1董事长总经理产品部研发部设计部行政总监财核部会计出纳行政部64

部门表结构（department）

id部门编号name部门名称level所在树层级parent_id上级部门编号复制代码1、问题来了

这样的方式很不错，可以很直观的体现各个节点之间的关系，通常可以满足大多数需求。但是当业务需求变得多了，数据量庞大了，这样的方式就不再适合用于生产。

例如：PM加了以下需求：

查出指定部门下所有子孙部门。查询子孙部门总数。判断节点是否叶子节点。查出所有子孙部门

使用指定部门编号，一层一层使用递归往下查，可能是多数人会想到的方法。尽管在mysql8.0支持了cte(公共表表达式)，递归效率比传统递归方式有明显提升，但是查询效率仍会随着部门树层级深度的提高而变差。

另外一种方法，一次性查出所有数据，放入内存中处理（数据量少时，可以选用。数据量多，不怕挨打的人也可以选这种）~

查询子孙部门总数

递归查询每一层的数量，最后相加。

判断是否叶子节点

方法1：可以加字段isLeaf的方式，来表示这个节点是否是叶子节点。

方法2：直接通过查询parent_id=当前id的count是否大于0，大于0表示不是叶子节点，等于0表示为叶子节点。

在日常中，可能会经常使用上述类似方法去解决类似的问题，但我觉得这样的方法在效率上不是最优解。于是乎开始查找更好的方案去解决这些问题。

要不试试这个方法？

直到后面查到国外一博客中，见到了所谓的《改进后的先序树遍历》文章（天哪，竟然是一篇年发表的文章）~

他具体是怎么做的呢？

还是回到刚刚的组织架构

我们从根节点开始，给董事长左值设为1，下级部门总经理左值设为2，以此类推地沿着边缘开始遍历，给每个节点加上左值，遇到叶子节点处给节点加上右值，再继续向上沿着边缘继续遍历，遍历结束回到根节点右侧,你将得到类似这样的结构。

image.png

遍历完后每一个节点都有与之对应的左右值。这个时候可以去除parent_id字段，添加lft,rgt，来存储左右值。

idnamelftrgtlevel1董事长12总经理产品部设计部研发部行政总监财核部出纳会计行政部

数据和结构准备完毕，我们来试试操作解决上面的需求~

查出所有子孙部门

根据当前表结构的规律，可以发现，要想查出所有子孙部门，只要查左值在被查寻部门的左\右数之间的节点，查出来都是他的子节点。例如：查询行政总监的所有子部门，行政总监的左右数是9和18，因此只需要用9和18做lft字段的between查询，查询出的结果就是；

SET

lft:=9;SET

rgt:=18;SELECT*FROMdepartmentWHERElftBETWEEN

lftAND

rgtORDERBYlftASC;/*例子中用BETWEEN将被查部门本身也查了出来。实际中可以用大于小于*/

完美~

查询子孙部门总数

到这里可能会说，需求1都解决了，查总数自然也就解决了，直接上selectcount就可以了，确实没有错，但是没有那个必要，因为有个简单公式可以直接计算

公式：总数=(右值-左值-1)/2

例如：

行政总监的子孙部门数=(18-9-1)/2=4董事长的子孙部门数=(20-1-1)/2=9会计的子部门数=(14-13-1)/2=0可以数数看，确实没错哦～判断是否叶子节点

通过有了上述计算公式算总数的经验后，现在判断是否叶子节点，有的小伙伴已经知道了怎么做，那就是：

右值-1==左值那他就是叶子节点，或者左值+1==右值那他就是叶子节点，反之则不是叶子节点。

例如：

设计部，5-1==4，因此他是叶子节点。

董事长，20-1!=1，因此他不是叶子节点。

至此已经完美的解决了上述需求问题，接下来再尝试一下业务的基本操作。

我们创建了一个高质量的技术交流群，与优秀的人在一起，自己也会优秀起来，赶紧点击加群，享受一起成长的快乐。另外，如果你最近想跳槽的话，年前我花了2周时间收集了一波大厂面经，节后准备跳槽的可以点击这里领取！

其他基本操作新增部门

当新增一个部门时，需要对新增节点位置的后续边缘进行加2操作，因为每一个节点有左右两个数值。这个操作通常需要放到事务中进行处理。例如：在研发部门下添加一个新部门：

对应sql：

SET

lft:=7;/*新部门的左值*/SET

rgt:=8;/*新部门的左值*/SET

level:=5;/*新部门的层级*/begin;/*将插入的后续边缘的节点左右数+2*/UPDATEdepartmentSETlft=lft+2WHERElft

lft;UPDATEdepartmentSETrgt=rgt+2WHERErgt=

lft;/*插入数据*/INSERTINTOdepartment(name,lft,rgt,level)VALUES(新部门,

lft,

rgt,level);/*新增影响行数为0时，必须回滚*/