树形结构,别再用递归实现了,这才是最优的方案;更快、更强、更实用

  |   0 评论   |   0 浏览

大家好,我是一航;

不管你是做前端还是后端的开发,那我相信树形结构的需求一定有遇到过,特别是管理平台类型的项目,一般都会有一个树形结构的菜单栏,再比如说,公司组织架构层级关系归属关系等等需求,本质上都是树形结构的一种体现;

遇到这种需求,最常见也最容易想到的设计思路就是:父子关系的方式,子项通过一个字段来保存他的父ID,然后通过递归的方式得到层级关系;

前几天,技术交流群里面有小伙伴在问,实际的业务中,树形结构的数据太多、层级还深,查询过程一顿递归之后,性能表现的比较差,问有没有什么好的设计思路,让查询、统计更加的便捷高效;

今天就给大家介绍一种新的树形结构设计方案:改进后的先序树方式,在查询、统计方面的优势,要远大于父子关系的递归设计方案;

本文就来详细的讲解并对比一下两个方案的实现方式以及优缺点。

文章目录:

对于树形结构的需求,不管是采用什么方式,要处理的问题都是差不多的,下面先列举一下树形结构常见的问题点那些:

  • 节点的增删改
  • 是否存在子节点(叶子节点)
  • 查询出所有的子节点
  • 查询所有的孙节点
  • 查询所有的子孙节点
  • 父节点查询
  • 祖先节点查询
  • 统计所有子孙部门的数量

针对上面的这些问题,就以一个简单的公司组织架构示例,一起来看看,两种方案都是如何实现和解决的?

本文所有的示例都是采用的MySQL+Java实现,核心思路都类似,实际使用,可根据语言特性以及自己习惯的方式调整即可。

父子关系方案

父子关系,顾名思义,就是当前节点只关注自己的父节点是谁,并将其保存起来即可,查询我的子节点有那些,只需要全局找到所有父ID是和我的ID一致的项;

如下图所示:

方案特点

  • 优点

    • 方案简单易懂

    • 数据结构简单清晰

    • 层级直观、鲜明

    • 易维护

      层级关系只需要关注自己的父ID,所以在添加、修改的时候,一旦关系发生变化,调整对应的父ID即可。

  • 缺点

    • 查找麻烦、统计麻烦

      根据当前节点的数据,只能获取到子节点的数据,一旦查询、统计超出父子范围,就只能通过递归逐层查找了;

示例

根据上面的图示示例,与其对应的表结构如下:

| ID | dep_name(部门名称) | level(层级) | parent_id(父ID) |
| -- | ------------------ | ----------- | --------------- |
| 1 | 董事会 | 1 | 0 |
| 2 | 总经理 | 2 | 1 |
| 3 | 董事会秘书 | 2 | 1 |
| 4 | 产品部 | 3 | 2 |
| 5 | 行政总监 | 3 | 2 |
| 6 | 设计部 | 4 | 4 |
| 7 | 技术部 | 4 | 4 |
| 8 | 财务部 | 4 | 5 |
| 9 | 行政部 | 4 | 5 |
| 10 | 客户端 | 5 | 7 |
| 11 | 服务端 | 5 | 7 |

SQL脚本:

DROP TABLE IF EXISTS `department_info`;
CREATE TABLE `department_info`  (
  `id` int(11) NOT NULL,
  `dep_name` varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NULL DEFAULT NULL COMMENT '名称',
  `level` int(11) NULL DEFAULT NULL,
  `parent_id` int(11) NULL DEFAULT NULL COMMENT '父ID',
  PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8mb4 COLLATE = utf8mb4_general_ci ROW_FORMAT = Dynamic;

INSERT INTO `department_info` VALUES (1, '董事会', 1, 0);
INSERT INTO `department_info` VALUES (2, '总经理', 2, 1);
INSERT INTO `department_info` VALUES (3, '董事会秘书', 2, 1);
INSERT INTO `department_info` VALUES (4, '产品部', 3, 2);
INSERT INTO `department_info` VALUES (5, '行政总监', 3, 2);
INSERT INTO `department_info` VALUES (6, '设计部', 4, 4);
INSERT INTO `department_info` VALUES (7, '技术部', 4, 4);
INSERT INTO `department_info` VALUES (8, '财务部', 4, 5);
INSERT INTO `department_info` VALUES (9, '行政部', 4, 5);
INSERT INTO `department_info` VALUES (10, '客户端', 5, 7);
INSERT INTO `department_info` VALUES (11, '服务端', 5, 7);

函数的创建

由于父子节点的查询,需要依赖递归,为了查询方便,这里创建两个函数:

  • 递归查询子孙节点ID的函数

    DROP FUNCTION IF EXISTS queryChildrenDepInfo;
    DELIMITER ;;
    CREATE FUNCTION queryChildrenDepInfo(dep_id INT)
    RETURNS VARCHAR(4000)
    BEGIN
    	DECLARE sTemp VARCHAR(4000);
    	DECLARE sTempChd VARCHAR(4000);
    	SET sTemp='$';
    	SET sTempChd = CAST(dep_id AS CHAR);
    	WHILE sTempChd IS NOT NULL DO
    		SET sTemp= CONCAT(sTemp,',',sTempChd);
    		SELECT GROUP_CONCAT(id) INTO sTempChd FROM department_info WHERE FIND_IN_SET(parent_id,sTempChd)>0;
    	END WHILE;
    	RETURN sTemp;
    END
    ;;
    DELIMITER ;
    

    测试:查询技术部下的所有孙节点?

    SELECT queryChildrenDepInfo(4);
    

    SELECT * FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(4));
    

  • 递归查询祖先节点ID的函数

    DROP FUNCTION IF EXISTS queryParentDepInfo;
    DELIMITER;;
    CREATE FUNCTION queryParentDepInfo(dep_id INT)
    RETURNS VARCHAR(4000)
    BEGIN
    	DECLARE sTemp VARCHAR(4000);
    	DECLARE sTempChd VARCHAR(4000);
    	SET sTemp='$';
    	SET sTempChd = CAST(dep_id AS CHAR);
    	SET sTemp = CONCAT(sTemp,',',sTempChd);
    	SELECT parent_id INTO sTempChd FROM department_info WHERE id = sTempChd;
    	WHILE sTempChd <> 0 DO
    		SET sTemp = CONCAT(sTemp,',',sTempChd);
    		SELECT parent_id INTO sTempChd FROM department_info WHERE id = sTempChd;
    	END WHILE;
    	RETURN sTemp;
    END
    ;;
    DELIMITER ;
    

    测试:查询技术部所有的祖先节点?

    SELECT queryParentDepInfo(7);
    

    SELECT * FROM department_info WHERE FIND_IN_SET(id,queryParentDepInfo(7));
    

节点的增删改

  • 增加节点

    比如要在技术部下添加一个测试部门

    INSERT INTO department_info(`id`, `dep_name`, `level`, `parent_id`) VALUES (12, '测试部', 5, 7);
    
  • 修改节点

    比如:将测试部(ID = 12)提出来,放到产品部(ID = 4)下;就只需要将测试部对应的父节点ID修改为4即可

    SET @id = 12;
    SET @pid = 4;
    UPDATE department_info SET `parent_id` = @pid WHERE `id` = @id;
    
  • 删除节点

    删除相比于添加修改,情况就会特殊一些,如果删除的节点存在子节点,意味着子节点也需要同步删除掉;

    因此这里就需要用到上面创建的递归查询子孙节点ID的函数(queryChildrenDepInfo)

    比如:删除技术部门;

    DELETE FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(7));
    

是否存在子节点(叶子节点)

在该方案下,要想判断是否是叶子节点,有两种实现方式:

  • 统计当前节点以及子孙节点的数量

    递归查询所有子节点的ID,并统计数量,由于函数查询包含了节点自身,所以这里使用了 COUNT(*)-1来计算子节点的数量,如果等于0就是叶子节点,大于0说明不是叶子节点;

    -- 查看设计部(ID=6)是不是叶子节点
    SET @id = 6;
    -- 由于数量包含了自身,由于统计的是子节点的数量,所以这里需要-1将自己去掉
    SELECT COUNT(*)-1 FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(@id));
    

  • 添加叶子节点的标记

    在表中添加一个isLeaf字段,当节点增删改操作的时候,用这个字段来标记一下当前是否是叶子节点

查询出所有的下级部门(子节点)

查询所有的下级部门,此时就需要借助当前节点的id和level字段

例:查询产品部(id = 4,level = 3)的子节点

SET @id = 4;
SET @lv = 3;
SELECT * from department_info where parent_id = @id AND `level` = @lv + 1;

查询所有的下下级部门(孙节点)

实际业务场景下,这种需求很少,这里主要用来演示可操作性,不排除特殊的场合下用的上;

查询孙节点相比与子节点就麻烦很多了,因为当前节点和孙节点是没有任何数据上的关联,因此需要借助子节点才能找到孙节点,因此这里又必须得用上递归查询子孙节点ID的函数了;

例:查询产品部(id = 4,level = 3)的孙节点

-- 查询孙节点
SET @id = 4;
SET @lv = 3;
SELECT * FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(@id)) AND `level` = @lv + 2;

查询所有的下属部门

查询下属部门就和查询下下级部门(孙节点)类似,只是不用校验层级即可;

例:查询产品部下所有的下属部门?

SET @id = 4;
SELECT * FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(@id));

查询隶属部门

也就是查询父节点;在该方案下,节点中已经保存了父节点的ID,通过ID就能直接获取到父节点

查询所有上级部门

由于当前节点只保存了父级节点ID,更上一级的信息只能通过递归逐级获取;

例:查询技术部(id = 7)的所有上级部门;

SET @id = 7;
SELECT * FROM department_info WHERE FIND_IN_SET(id,queryParentDepInfo(@id));

统计所有下属部门的数量

和查询是否是叶子节点方式一样,只是对得到的数据解读的方式不同而已;

例:统计技术部的下属部门数量?

SET @id = 7;
SELECT COUNT(*)-1 FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(@id));

改进后的先序树方案

上述的父子关系方案可以看出,大部分的操作,都需要递归查询出所有的子孙节点后才行,如果出现文章开始说的,层级多,深度深的话,递归的过程,就会大大影响查询、统计的性能;

下面就来介绍一下改进后的先序树的树形结构方案,节点不再保存父节点的ID,而是为每个节点增加左值和右值

如下图示:

对应的表数据如下:

| id | dep_name(部门名称) | lt(左值) | rt(右值) | lv(层级) |
| -- | ------------------ | -------- | -------- | -------- |
| 1 | 董事会 | 1 | 22 | 1 |
| 2 | 总经理 | 2 | 19 | 2 |
| 3 | 董事会秘书 | 20 | 21 | 2 |
| 4 | 产品部 | 3 | 12 | 3 |
| 5 | 行政总监 | 13 | 18 | 3 |
| 6 | 设计部 | 4 | 5 | 4 |
| 7 | 技术部 | 6 | 11 | 4 |
| 8 | 财务部 | 14 | 15 | 4 |
| 9 | 行政部 | 16 | 17 | 4 |
| 10 | 客户端 | 7 | 8 | 5 |
| 11 | 服务端 | 9 | 10 | 5 |

SQL语句:

DROP TABLE IF EXISTS `department_info2`;
CREATE TABLE `department_info2`  (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `dep_name` varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NOT NULL COMMENT '名称',
  `lt` int(11) NOT NULL COMMENT '节点左数',
  `rt` int(11) NOT NULL COMMENT '节点右数',
  `lv` int(11) NOT NULL,
  PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 12 CHARACTER SET = utf8mb4 COLLATE = utf8mb4_general_ci ROW_FORMAT = Dynamic;

INSERT INTO `department_info2` VALUES (1, '董事会', 1, 22, 1);
INSERT INTO `department_info2` VALUES (2, '总经理', 2, 19, 2);
INSERT INTO `department_info2` VALUES (3, '董事会秘书', 20, 21, 2);
INSERT INTO `department_info2` VALUES (4, '产品部', 3, 12, 3);
INSERT INTO `department_info2` VALUES (5, '行政总监', 13, 18, 3);
INSERT INTO `department_info2` VALUES (6, '设计部', 4, 5, 4);
INSERT INTO `department_info2` VALUES (7, '技术部', 6, 11, 4);
INSERT INTO `department_info2` VALUES (8, '财务部', 14, 15, 4);
INSERT INTO `department_info2` VALUES (9, '行政部', 16, 17, 4);
INSERT INTO `department_info2` VALUES (10, '客户端', 7, 8, 5);
INSERT INTO `department_info2` VALUES (11, '服务端', 9, 10, 5);

方案特点

  • 优点

    • 查询汇总简单高效
    • 无需递归查询,性能高
  • 缺点

    • 结构相对复杂,数据层面理解难度较高

    • 不易维护

      以为左右值的存在,会直接影响到后续的节点,因此,当前节点增删改时,都会对后续的节点产业影响;

示例

节点的增删改

  • 新增

    如下图:在技术部下新增一个测试部,新增节点对应的左右值分别为11、12;

    过程分析:

    第一步,所有比11(新增节点的左数)大的左数全部+2(紫色部分)

    第二步,所有比12(新增节点的右数)大的右数全部+2(橙色部分)

    第三步,添加左右数分别为11、12的部门节点

    由于这里涉及到多个步骤,我们需要保证数据库操作的原子性,因此需要做事务操作,这里为了方便,创建一个存储过程;存储过程并不式必须的,同样也可以以代码的形式来保证事务操作;只是使用存储过程,可靠性会高一些;

    添加节点存储过程

    DROP PROCEDURE IF EXISTS insertDepartment;
    CREATE PROCEDURE insertDepartment(IN lt_i INT,IN rt_i INT,IN lv_i INT,IN dn VARCHAR(256))
    BEGIN
    	  DECLARE d_error INTEGER DEFAULT 0;
        DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET d_error= -2;-- 异常时设置为1
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET d_error = -3; -- 如果表中没有下一条数据则置为2
    
    		START TRANSACTION;
    		-- 将所有左值大于新增左值的部门全部+2
    		UPDATE department_info2 SET lt=lt+2 WHERE lt > lt_i;
    		-- 将所有右值大于新增右值的部门全部+2
    		UPDATE department_info2 SET rt=rt+2 WHERE rt >= lt_i;
    		-- 新增部门
    		INSERT INTO department_info2(dep_name,lt,rt,lv) VALUES(dn,lt_i,rt_i,lv_i);
    		SET d_error= ROW_COUNT();
    
        IF d_error != 1 THEN
            ROLLBACK;-- 结果不等于1 的时候,说明新增失败,回滚操作
        ELSE
            COMMIT; -- 等于1的时候,说明添加成功,提交
        END IF;
        select d_error;
    END
    

    输入参数

    lt_i :新增部门的左值

    rt_i:新增部门的右值

    lv_i:行政部门的层级

    dn:部门名称

    如上图的示例,就可以调用新增的存储过程添加:

    call insertDepartment(11, 12, 5,"测试部");
    

  • 修改

    普通的节点信息修改,这里就不多多说了,很简单;

    节点移动是此方案下,最复杂的修改操作,因为整个过程涉及到位置的变化,层级的变化等多个维度的调整,而且还得保证事务操作;

    例:我们要将技术部(id = 4)交由总经理(id = 2)直接负责,也就是移动到总经理之下;

    过程分析:

    第一步,计算技术部的左右数差值

    第二步,计算与移动后的上级节点之间的差值

    第三步,确定是左移还是右移

    第四步,将本节点与目标节点之间的差值减去(左移)/加上(右移)

    第五步,将移动的节点以及子孙的节点与父节点之间的差值减去(左移)/加上(右移)

    第六步,调整层级

    整个过程如下图所示,稍微有点点复杂,可以结合图示以及存储过程的代码,仔细的理解一下:

    为了方便操作,避免出错,这里同样以存储过程的方式来实现核心逻辑,降低出错风险:

    DROP PROCEDURE IF EXISTS moveDepartment;
    CREATE PROCEDURE moveDepartment(IN fid INT,IN tid INT)
    BEGIN
    	  DECLARE d_error INTEGER DEFAULT 0;
    		DECLARE num INTEGER DEFAULT 0; -- 删除节点左右值之间的差值
    		DECLARE mnum INTEGER DEFAULT 0; -- 移动阶段与上级节点之间的差值
    		DECLARE ids VARCHAR(1000); -- 保存所有正在移动的id集合,保证多个节点移动时也能正常
    		DECLARE blt INT; -- 需要移动节点的左数
    		DECLARE brt INT; -- 需要移动节点的右数
    		DECLARE blv INT; -- 需要移动节点的层级
    		DECLARE tlt INT; -- 目标节点的左数
    		DECLARE trt INT; -- 目标节点的右数
    		DECLARE tlv INT; -- 目标节点的层级
        DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET d_error= -2;-- 异常时设置为1
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET d_error = -3; -- 如果表中没有下一条数据则置为2
    
    		START TRANSACTION;
    		-- 查询待移动的节点的左右数以及层级
    		SELECT lt,rt,lv	INTO blt, brt,blv FROM department_info2 WHERE id = fid;
    		-- 查询目标节点的左右数以及层级
    		SELECT lt,rt,lv INTO tlt, trt,tlv FROM department_info2 WHERE id = tid;
    		-- 查询所有要一定的节点,当前节点以及其子孙节点
    		SELECT GROUP_CONCAT(id) INTO ids FROM department_info2 WHERE lt>=blt AND rt <=brt;
    		IF tlt > blt AND trt < brt THEN
    		  -- 将自己移动到自己的下属节点 暂时不允许 如果要如此操作,需要将下级调整为平级 再移动
    			SET d_error = -4;
    		ELSEIF blt > tlt AND brt < trt AND blv = tlv + 1 THEN
    		  -- 说明本身就已经是目标节点在子节点了,不需要处理,直接成功
    		  SET d_error = 0;
    		ELSE
    		  -- 计算移动节点与上级节点之间的差值
    			SET mnum = trt - brt -1;
    			-- 计算当前节点及其子节点的差值
    			SET num = brt - blt + 1;
    
    			-- 首先将移动前的节点整个元素表中移除掉
    			IF trt > brt THEN
    			  -- 左往右移动
    				UPDATE department_info2 SET lt=lt-num WHERE lt > brt AND lt < trt;
    				UPDATE department_info2 SET rt=rt-num WHERE rt > brt AND rt < trt;
    			ELSE
    			  -- 从右往左移动 将系数全部变为负值,-负数就等于+正数
    				SET mnum = -mnum;
    				SET num = -num;
    				UPDATE department_info2 SET lt=lt-num WHERE lt >= trt AND lt < blt;
    				UPDATE department_info2 SET rt=rt-num WHERE rt >= trt AND rt < blt;
    			END IF;
    
    			-- 调整移动的节点以及下属节点
    			UPDATE department_info2 SET lt=lt+mnum,rt=rt+mnum,lv = lv - (blv - tlv -1) WHERE FIND_IN_SET(id,ids);
    			SET d_error= ROW_COUNT();
    
    			IF d_error <= 0 THEN
    					ROLLBACK;
    			ELSE
    					COMMIT;
    			END IF;
    		END IF;
        select d_error;
    END
    

    输入参数

    fid:移动的节点id

    tid:目标节点id

    测试:

    CALL moveDepartment(7,2)
    

  • 删除

    删除的过程正好与新增相反,在删除节点及其自己点的时候,大于删除节点的所有左右值都需要减去删除节点的左右差值+1;

    如下图示例:删除技术部

    过程:

    第一步,计算出删除节点的左右差值+1;技术部的左右值分别时6和11,差值+1:11 - 6 + 1

    第二步,删除节点机器所有子节点

    第三步,所有大于删除节点左右值的节点,全部减去差值

    同样为了方便操作,我们也创建一个存储过程:

    DROP PROCEDURE IF EXISTS removeDepartment;
    CREATE PROCEDURE removeDepartment(IN did INT)
    BEGIN
    	  DECLARE d_error INTEGER DEFAULT 0;
    		DECLARE num INTEGER DEFAULT 0; -- 删除节点左右值之间的差值
    		DECLARE dlt INT; -- 删除节点的左值
    		DECLARE drt INT; -- 删除节点的右值值
        DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET d_error= -2;-- 异常时设置为1
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET d_error = -3; -- 如果表中没有下一条数据则置为2
    
    		START TRANSACTION;
    		-- 查询删除节点的左右值
    		SELECT lt,rt INTO dlt, drt FROM department_info2 WHERE id = did;
    		-- 计算当前节点及其子节点的差值
    		SET num = drt - dlt + 1;
    
    		-- 删除当前节点及其子节点
    		DELETE FROM department_info2 WHERE lt>=dlt AND rt<=drt;
    		SET d_error= ROW_COUNT();
    
    		-- 左右值减少对应的插值
    		UPDATE department_info2 SET lt=lt-num WHERE lt > dlt;
        UPDATE department_info2 SET rt=rt-num WHERE rt > drt;
    
        IF d_error != num/2 THEN -- 判断删除的数量与当前节点+子孙节点的数量是否一致;不一致的话,直接回滚
            ROLLBACK;
        ELSE
            COMMIT;
        END IF;
        select d_error;
    END
    

    测试:

    -- 设计部的id = 7
    SET @id=7;
    call removeDepartment(@id);
    

是否存在子节点(叶子节点)

无需额外的查询,直接通过节点的左右数,即可判断是否是叶子节点了;当右数 - 左数 = 1时,说明当前节点就属于叶子节点,否则就不是;

查询所有的下级部门

等价于:查询左数比当前节点大,右数比当前节点小,且层比当前节点大1的所有节点;

例:查询产品部(lt = 3,rt = 12,lv = 3)的所有下级部门:

SET @lt = 3;  -- 节点左数
SET @rt = 12; -- 节点右数
SET @lv = 3;  -- 当先的层级
SELECT * from department_info2 where lt > @lt AND rt < @rt AND `lv` = @lv + 1

查询所有的下下级部门(孙节点)

实际业务中很少会出现此需求,这里仅仅用于可行性演示;

孙节点的查询和子节点类似,仅仅层级由+1变为了+2

例:查询产品部(lt = 3,rt = 12,lv = 3)的所有下下级部门:

SET @lt = 3;  -- 节点左数
SET @rt = 12; -- 节点右数
SET @lv = 3;  -- 当先的层级
SELECT * from department_info2 where lt > @lt AND rt < @rt AND `lv` = @lv + 2;

查询所有下属部门

等价于:比当前节点左数大,右数小的节点,全部是子孙节点;

例,查询产品部(lt = 3,rt = 12)的所有下属部门:

SET @lt = 3;  -- 节点左数
SET @rt = 12; -- 节点右数
SELECT * from department_info2 where lt > @lt AND rt < @rt;

查询隶属部门

等价于:左数比自己小,右数比自己大,且层级-1的节点,也就是父节点

例,查询技术部(lt = 6 , rt = 11)的隶属部门:

SET @lt = 6;  -- 节点左数
SET @rt = 11; -- 节点右数
SET @lv = 4;  -- 当先的层级
SELECT * from department_info2 where lt < @lt AND rt > @rt AND `lv` = @lv - 1 ;

查询所有的上级部门

与查询父节点类似,只是不再需要校验层级了,所有左数比自己小,右数比自己大都是自己的祖先节点;

例,查询产品部(lt = 3,rt = 12)的所有上级部门

SET @lt = 3;  -- 节点左数
SET @rt = 12; -- 节点右数
SELECT * from department_info2 where lt < @lt AND rt > @rt;

统计所有下属部门的数量

统计子孙节点数量,无需额外查询,只需根据自己的左右数,即可计算出子节点的数量;

计算公式:(右数 - 左数 - 1 )/ 2

例,计算产品部(id = 4)的下属部门的数量:

SELECT dep_name,(rt - lt - 1) / 2 as num FROM department_info2 where id = 4

格式化数据

不管是那种方案,数据层面都是扁平的,只是通过字段逻辑表达了结构化的关系,那查询出来之后,要如何将数据结构化成树形结构之后展示呢,下面介绍递归和非递归的两种方式实现方式:

  • 基础的对象

    @Data
    @RequiredArgsConstructor
    public class LrItem {
    
        @NonNull
        private Integer id;
    
        @NonNull
        private String depName;
    
        @NonNull
        private Integer left;
    
        @NonNull
        private Integer right;
    
        private Integer level;
    
        private Integer parentId;
    
        /**
         * 是否是叶子
         */
        private Boolean isLeaf;
    
        private List<LrItem> childItem;
    }
    
  • 测试数据

    这里只是演示格式化数据,就不整那么复杂了;实际业务场景,这批数据一般都是从数据库中查询出来的。

    List<LrItem> deps = new ArrayList<>();
    deps.add(new LrItem(1, "董事会", 1, 22));
    deps.add(new LrItem(2, "总经理", 2, 19));
    deps.add(new LrItem(3, "董事会秘书", 20, 21));
    deps.add(new LrItem(4, "产品部", 3, 12));
    deps.add(new LrItem(5, "行政总监", 13, 18));
    deps.add(new LrItem(6, "设计部", 4, 5));
    deps.add(new LrItem(7, "技术部", 6, 11));
    deps.add(new LrItem(8, "财务部", 14, 15));
    deps.add(new LrItem(9, "行政部", 16, 17));
    deps.add(new LrItem(10, "客户端", 7, 8));
    deps.add(new LrItem(11, "服务端", 9, 10));
    
  • 整理数据

    public static void init(List<LrItem> deps) {
        // 如果数据库排序过了之后  这里就不用排序了
        deps.sort(Comparator.comparing(LrItem::getLeft));
    
        // 为计算层级 缓存节点右侧的值
        List<Integer> rights = new ArrayList<>();
        Map<Integer, Integer> mp = new HashMap<>();
    
        // 初始化节点的层级,叶子节点 以及 父节点ID 对应的数据
        deps.forEach(item -> {
            if (rights.size() > 0) {
                // 一旦发现本次节点右侧的值比前一次的大,说明出现层级上移了 需要移除前一个底层及的值
                // 这里大部分情况下只存在移除前面一个值情况
                while (rights.get(rights.size() - 1) < item.getRight()) {
                    rights.remove(rights.size() - 1);//从rights末尾去除
                }
            }
            Integer _level = rights.size() + 1;
            item.setLevel(_level);
            mp.put(_level, item.getId());
            item.setParentId(mp.containsKey(_level - 1) ? mp.get(_level - 1) : 0); //计算出上级部门编号
            item.setIsLeaf(item.getLeft() == item.getRight() - 1);//判断是否叶子部门
            rights.add(item.getRight());
        });
    
        System.out.println(rights);
        System.out.println(mp);
    }
    

递归整理

递归的思路比较简单清晰,就是拿到当前节点之后,在所有是节点中找自己的子节点,当所有节点都找过一遍之后,整个树形结构话的过程就完了;

我们可以结合Java 8 Stream新特性,让整个递归代码相对简单清晰;

/**
 * @param deps 所有数据
 */
public static void recursive(List<LrItem> deps) {
    init(deps);
    //获取父节点
    List<LrItem> collect = deps.stream()
            .filter(m -> m.getParentId() == 0)
            .map(m ->
                    {
                        m.setChildItem(getChildrens(m, deps));
                        return m;
                    }
            ).collect(Collectors.toList());

    // 普遍请求下,根节点只会有一个,所以这里取出第一个元素,如果由多个,可根据需求调整,这里仅做测试使用
    System.out.println(JSON.toJSON(collect.get(0)));
}

/**
 * 递归查询子节点
 *
 * @param root 根节点
 * @param all  所有节点
 * @return 根节点信息
 */
private static List<LrItem> getChildrens(LrItem root, List<LrItem> all) {
    List<LrItem> children = all.stream()
            .filter(m -> Objects.equals(m.getParentId(), root.getId()))
            .map(m -> {
                        m.setChildItem(getChildrens(m, all));
                        return m;
                    }
            ).collect(Collectors.toList());
    return children;
}

非递归倒序整理

这是一个以空间换时间的方案;

此方式的特点:按层级排序后的数据,只需要一次for循环,就能整理出结构化的数据。

  • 第一步,计算出层级以及父节点ID

  • 第二步,按层级进行排序

  • 第三步,倒序从最深的节点让root节点遍历

    遍历过程以 Map<Integer, List<LrItem>>的方式缓存ID及当前节点的数据,当上升一个层级之后,就将Map中缓存的关于我的自阶段取出来,保存到自己对象的 childItem字段中

public static void reverseFormat(List<LrItem> deps) {
    init(deps);

    deps.sort(Comparator.comparing(LrItem::getLevel));
    deps.forEach(item -> System.out.println(JSON.toJSONString(item)));

    // 临时缓存各自节点的容器
    Map<Integer, List<LrItem>> childCache = new HashMap<>();

    // 当前节点
    LrItem lrItem = null;
    //int level = 0;
    // 采用倒序遍历,整理各个子节点的集合
    for (int i = deps.size() - 1; i >= 0; i--) {
        lrItem = deps.get(i);
        Integer parentId = lrItem.getParentId();
        if (null == lrItem || null == parentId) {
            continue;
        }

        List<LrItem> childItems = childCache.get(parentId);
        if (null == childItems) {
            childCache.put(parentId, childItems = new ArrayList<>());
        }
        childItems.add(lrItem);

        // 如果不是叶子节点的时候,说明他肯定有子节点,去缓存中找到,回填回去
        if (!lrItem.getIsLeaf()) {
            childItems = childCache.get(lrItem.getId());
            childItems.sort(Comparator.comparing(LrItem::getId));
            lrItem.setChildItem(childItems);
            childCache.remove(lrItem.getId());
        }
    }

    System.out.println(JSON.toJSONString(lrItem));
}

格式化后的数据

不管那种方式,最终都会得到以下的结构化数据;

{
    "depName": "董事会",
    "id": 1,
    "isLeaf": false,
    "left": 1,
    "level": 1,
    "prientId": 0,
    "right": 22,
    "childItem": [
        {
            "depName": "总经理",
            "id": 2,
            "isLeaf": false,
            "left": 2,
            "level": 2,
            "prientId": 1,
            "right": 19,
            "childItem": [
                {
                    "depName": "行政总监",
                    "id": 5,
                    "isLeaf": false,
                    "left": 13,
                    "level": 3,
                    "prientId": 2,
                    "right": 18,
                    "childItem": [
                        {
                            "depName": "设计部",
                            "id": 6,
                            "isLeaf": true,
                            "left": 4,
                            "level": 4,
                            "prientId": 4,
                            "right": 5
                        },
                        {
                            "depName": "技术部",
                            "id": 7,
                            "isLeaf": false,
                            "left": 6,
                            "level": 4,
                            "prientId": 4,
                            "right": 11,
                            "childItem": [
                                {
                                    "depName": "客户端",
                                    "id": 10,
                                    "isLeaf": true,
                                    "left": 7,
                                    "level": 5,
                                    "prientId": 7,
                                    "right": 8
                                },
                                {
                                    "depName": "服务端",
                                    "id": 11,
                                    "isLeaf": true,
                                    "left": 9,
                                    "level": 5,
                                    "prientId": 7,
                                    "right": 10
                                }
                            ]
                        }
                    ],
                    "depName": "产品部",
                    "id": 4,
                    "isLeaf": false,
                    "left": 3,
                    "level": 3,
                    "prientId": 2,
                    "right": 12
                },
                {
                    "childItem": [
                        {
                            "depName": "财务部",
                            "id": 8,
                            "isLeaf": true,
                            "left": 14,
                            "level": 4,
                            "prientId": 5,
                            "right": 15
                        },
                        {
                            "depName": "行政部",
                            "id": 9,
                            "isLeaf": true,
                            "left": 16,
                            "level": 4,
                            "prientId": 5,
                            "right": 17
                        }
                    ]
                }
            ]
        },
        {
            "depName": "董事会秘书",
            "id": 3,
            "isLeaf": true,
            "left": 20,
            "level": 2,
            "prientId": 1,
            "right": 21
        }
    ]
}

比较

针对上面的详解,下来以表格的形式来更直观的对两者做一下对比:

功能父子关系方案先序数方案
新增简单复杂
修改简单复杂
删除复杂复杂
判断叶子节点复杂(除非增加编辑难度,提前整理好)简单
查询子节点简单简单
查询孙节点复杂简单
查询父节点简单简单
查询祖先节点复杂简单
统计子孙节点数量复杂简单
适用场景结构简单,层级少,统计少,频繁改动结构复杂,改动少,层级深,需要复杂统计

总结

经过对两种方案常用场景的分析,发现其实各自都有自己的优缺点,所以原谅我标题稍微有点点标题党;相比起来,个人还是比较喜欢改进的先序数方案

父子关系方案适合结构相对简单、层级少的需求;

而先序数方案就更适合结构复杂,改动少,层级深,需要频繁汇总统计的需求了;

所以说,还是那句话,没有绝对好的方案,只有合不合适的场景;需要更具自己业务的实际情况,酌情挑选对项目最有利的方案。

好了,今天的分享就到这里;如果有任何问题,欢迎随时交流指正!

非常感谢你的点赞、关注和收藏!



标题:树形结构,别再用递归实现了,这才是最优的方案;更快、更强、更实用
作者:码霸霸
地址:https://lupf.cn/articles/2022/05/23/1653282737930.html