Java基础、中级、高级、架构面试资料

推荐一种避免递归查询所有子部门的数据结构设计与实现

JAVA herman 828浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog2,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog2,之前的微信号好友位已满,备注:返现
受密码保护的文章请关注“业余草”公众号,回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领
腾讯云】1核2G5M轻量应用服务器50元首年,高性价比,助您轻松上云

最近我阅读了一篇老外的文章,里面介绍了通过一种巧妙的设计,实现了高效的部门树查询设计。避免递归等低效查询。今天分享推荐给大家!

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

递归遍历部门树
递归遍历部门树

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

idnameparent_idlevel
1董事长01
2总经理12
3产品部23
4研发部34
5设计部34
6行政总监23
7财核部64
8会计75
9出纳75
10行政部64

部门表结构(department)

id          部门编号
name        部门名称
level       所在树层级
parent_id   上级部门编号

问题来了

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

例如:PM 加了以下需求:

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

查出所有子孙部门

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

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

查询子孙部门总数

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

判断是否叶子节点

  • 方法1:可以加字段isLeaf的方式,来表示这个节点是否是叶子节点。
  • 方法2:直接通过查询parent_id=当前id的 count 是否大于 0,大于 0 表示不是叶子节点,等于 0 表示为叶子节点。

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

要不试试这个方法?

直到后面查到国外一博客中,见到了所谓的《改进后的先序树遍历》(https://www.sitepoint.com/hierarchical-data-database-2)文章(天哪,竟然是一篇 2003 年发表的文章)~

他具体是怎么做的呢?

还是回到刚刚的组织架构。

复杂的部门组织架构
复杂的部门组织架构

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

高效部门树数据结构
高效部门树数据结构

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

idnamelftrgtlevel
1董事长1201
2总经理2192
3产品部383
4设计部454
4研发部674
6行政总监9183
7财核部10154
8出纳11125
9会计13145
10行政部16174

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

查出所有子孙部门

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

SET @lft := 9;
SET @rgt := 18;
SELECT * FROM department WHERE lft BETWEEN @lft AND @rgt ORDER BY lft ASC;
/*例子中用BETWEEN将被查部门本身也查了出来。实际中可以用大于小于*/

完美~

查询子孙部门总数

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

公式:总数 = (右值 - 左值 - 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操作,因为每一个节点有左右两个数值。这个操作通常需要放到事务中进行处理。

新增或删除节点时右节点判断条件应该是 lft >= 当前节点的 lft

例如:在研发部门下添加一个新部门

新增部门
新增部门

对应 sql:

SET @lft := 7;/*新部门的左值*/
SET @rgt := 8;/*新部门的左值*/
SET @level := 5;/*新部门的层级*/
begin;
/*将插入的后续边缘的节点左右数+2*/
UPDATE department SET lft=lft+2 WHERE lft > @lft;
UPDATE department SET rgt=rgt+2 WHERE rgt >= @lft;
/*插入数据*/
INSERT INTO department(name,lft,rgt,level) VALUES('新部门',@lft,@rgt,level);
/*新增影响行数为0时,必须回滚*/
commit;
/*rollback;*/

删除部门

删除部门与新增部门类似,不同的是需要对删除节点的后续边缘节点减2操作。 例如:删除刚刚添加的新部门:

删除部门
删除部门

对应 sql:

SET @lft := 7;/*要删除的节点左值*/
SET @rgt := 8;/*要删除的节点右值*/
begin;
UPDATE department SET lft=lft-2 WHERE lft > @lft;
UPDATE department SET rgt=rgt-2 WHERE rgt > @lft;

/*删除节点*/
DELETE FROM department WHERE lft=@lft AND rgt=@rgt;
/*删除影响行数为0时,必须回滚*/
commit;

查询直接子部门

查询某部门的直接子部门(即不包含孙子部门),例如:查询总经理下的直接子部门。正常需要返回产品部行政总监

查询直接子部门
查询直接子部门

对应的 sql:

SET @level := 2;/*总经理的level*/
SET @lft := 2;/*总经理的左值*/
SET @rgt := 19;/*总经理的右值*/

SELECT * FROM department WHERE lft > @lft AND rgt < @rgt AND level = @level+1;

查询祖链路径

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

SET @lft := 3;/*产品部左值*/
SET @rgt := 8;/*产品部右值*/

SELECT * FROM department WHERE lft < @lft AND rgt > @rgt ORDER BY lft ASC;

完结

目前就这些,欢迎指正、交流、评论。。。我感觉这个部门设计很经典,非常值得收藏,以便用时只需!

参考资料

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号:xttblog2。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » 推荐一种避免递归查询所有子部门的数据结构设计与实现