Question

超赞，老外的一种避免递归查询所有子部门的树数据表设计与实现！

Answer 1

| 目录

通常树形结构的存储，是在子节点上存储父节点的编号来确定各节点的父子关系，例如这样的组织结构：[图片上传失败...(image-a14d87-1651886833418)]

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

[图片上传失败...(image-a73b71-1651886833418)]

部门表结构（department）

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

例如：PM加了以下需求：

使用指定部门编号，一层一层使用递归往下查，可能是多数人会想到的方法。尽管在mysql8.0支持了 cte(公共表表达式)，递归效率比传统递归方式有明显提升，但是查询效率仍会随着部门树层级深度的提高而变差。另外一种方法，一次性查出所有数据，放入内存中处理（数据量少时，可以选用。数据量多，不怕挨打的人也可以选这种）~

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

方法1：可以加字段 isLeaf 的方式，来表示这个节点是否是叶子节点。方法2：直接通过查询parent_id=当前id的count是否大于0，大于0表示不是叶子节点，等于0表示为叶子节点。在日常中，可能会经常使用上述类似方法去解决类似的问题，但我觉得这样的方法在效率上不是最优解。于是乎开始查找更好的方案去解决这些问题。

直到后面查到国外一博客中，见到了所谓的《改进后的先序树遍历》文章（天哪，竟然是一篇2003年发表的文章）~他具体是怎么做的呢？还是回到刚刚的组织架构[图片上传失败...(image-8b11ac-1651886833417)]

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

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

[图片上传失败...(image-278dca-1651886833417)]

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

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

<pre mp-original-font-size="17" mp-original-line-height="27.200000762939453" style="margin: 0px; padding: 0px; outline: 0px; max-width: 100%; box-sizing: border-box !important; word-wrap: break-word !important; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); font-size: 17px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: 0.5440000295639038px; orphans: auto; text-align: justify; text-indent: 0px; text-transform: none; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; line-height: 27.200000762939453px;">

完美~
</pre>

到这里可能会说，需求1都解决了，查总数自然也就解决了，直接上select count就可以了，确实没有错，但是没有那个必要，因为有个简单公式可以直接计算。公式：总数 = (右值 - 左值 - 1) / 2例如：

通过有了上述计算公式算总数的经验后，现在判断是否叶子节点，有的小伙伴已经知道了怎么做，那就是：右值 - 1 == 左值那他就是叶子节点，或者左值 + 1 == 右值那他就是叶子节点，反之则不是叶子节点。例如：设计部，5 - 1 == 4，因此他是叶子节点。董事长，20 - 1 != 1，因此他不是叶子节点。至此已经完美的解决了上述需求问题，接下来再尝试一下业务的基本操作。

当新增一个部门时，需要对新增节点位置的后续边缘进行加2操作，因为每一个节点有左右两个数值。这个操作通常需要放到事务中进行处理。例如：在研发部门下添加一个新部门：[图片上传失败...(image-36a719-1651886833417)]

对应sql：

<pre mp-original-font-size="17" mp-original-line-height="27.200000762939453" style="margin: 0px; padding: 0px; outline: 0px; max-width: 100%; box-sizing: border-box !important; word-wrap: break-word !important; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); font-size: 17px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: 0.5440000295639038px; orphans: auto; text-align: justify; text-indent: 0px; text-transform: none; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; line-height: 27.200000762939453px;">

</pre>

删除部门与新增部门类似，不同的是需要对删除节点的后续边缘节点减2操作。例如：删除刚刚添加的新部门：[图片上传失败...(image-504fd7-1651886833417)]

对应sql

<pre mp-original-font-size="17" mp-original-line-height="27.200000762939453" style="margin: 0px; padding: 0px; outline: 0px; max-width: 100%; box-sizing: border-box !important; word-wrap: break-word !important; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); font-size: 17px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: 0.5440000295639038px; orphans: auto; text-align: justify; text-indent: 0px; text-transform: none; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; line-height: 27.200000762939453px;">

</pre>

查询某部门的直接子部门（即不包含孙子部门），例如：查询总经理下的直接子部门。正常需要返回产品部和行政总监[图片上传失败...(image-e2c88e-1651886833417)]

对应的sql

<pre mp-original-font-size="17" mp-original-line-height="27.200000762939453" style="margin: 0px; padding: 0px; outline: 0px; max-width: 100%; box-sizing: border-box !important; word-wrap: break-word !important; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); font-size: 17px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: 0.5440000295639038px; orphans: auto; text-align: justify; text-indent: 0px; text-transform: none; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; line-height: 27.200000762939453px;">

</pre>

查询某部门的祖链路径。例如：查询产品部的祖链路径，正常需要返回董事长,总经理

<pre mp-original-font-size="17" mp-original-line-height="27.200000762939453" style="margin: 0px; padding: 0px; outline: 0px; max-width: 100%; box-sizing: border-box !important; word-wrap: break-word !important; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); font-size: 17px; font-style: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: 0.5440000295639038px; orphans: auto; text-align: justify; text-indent: 0px; text-transform: none; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; line-height: 27.200000762939453px;">

</pre>

在我目前看来，这个方法的唯一缺点就是，每一次的新增或删除，操作节点的后续边缘走到的节点都要加/减2操作。

欢迎指正、交流和评论，一起探讨更多解决方案 ...

-- 链接指导:
https://mp.weixin.qq.com/s/GDmrIwo89WVfDyAWYSBWQA