数据结构PTT优化部门树查询

数据结构PTT优化部门树查询

进入正文之前先给出一个概念,可以在看完文章后再来看这个数据结构概念

预排序遍历树（Modified Preorder Tree Traversal，简称MPTT）是一种通过冗余字段优化树形结构查询效率的算法，常用于解决多层级分类（如部门树、商品分类）的递归查询性能瓶颈问题。其核心是通过深度优先遍历预计算为每个节点添加左右边界值（lft和rgt），实现以空间换时间的高效查询。

1.业务场景

实际开发中遇到两个接口:

1. 部门树查询接口,部门结构中需要查出租户下的所有部门树结构
2. RBAC权限控制中有"本级及其自己"的权限范围,需要一次查出该部门及其子部门

数据表的设计上，通过一个 parent_id 字段关联是父部门id,通过该字段查询到这个部门的子部门的列表。然后通过递归不断地遍历查询出所有的部门并且组装成树。

public List<DepartMent> queryByParentId(int parentId){
        //这里执行数据库查询
        //select * from department where tenant_id=xxx and parent_id=xxx;
        ...
    };
    public List<DepartMent> getChildren(int parentId){
        //查出子部门
        List<DepartMent> children = queryByParentId(parentId);
        for (DepartMent departMent : children) {
            List<DepartMent> child = getChildren2(departMent.getId());
            departMent.setChildren(child);
        }
        return children;
    }

问题就出现在递归逻辑,此处是每封装一个部门,就需要执行一次sql查询,当

• 部门层级过深
• 部门数量过多

都会导致sql查询的执行次数过多

这里先考虑两种常见的树查询优化方案:

1. 懒查询:一次只查询一级部门节点,慢慢展开,但在数据权限查询接口不支持,因为需要一次查出所有子部门

2. 直接用租户 id 查询出所有的部门数据然后再组装成树

   确实可以解决部门树的查询，但是数据权限的子部门那里查询从出所有数据组装也会超时(解释这中方案有什么不适合权限接口的地方,我的想法是这种全查的方式在查出后还需要对数据进行递归处理)

   public List<DepartMent> getChildrenOptimized(int parentId) {
       List<DepartMent> allDepartments = queryAllDepartments(); // 一次性查询所有部门
       return buildTree(parentId, allDepartments);
   }
   
   private List<DepartMent> buildTree(int parentId, List<DepartMent> allDepartments) {
       List<DepartMent> children = new ArrayList<>();
       for (DepartMent dept : allDepartments) {
           if (dept.getParentId() == parentId) {
               dept.setChildren(buildTree(dept.getId(), allDepartments));
               children.add(dept);
           }
       }
       return children;
   }
   

解决问题的核心还是传入任何一个部门的id就能迅速查出子部门.

解决方案

1. 加缓存,每一个部门id都缓存子部门的数据,但初次构建缓存的查询依旧慢…(这里请分析缓存方案的缺点)
2. 减少数据库查询的次数

引入数据结构方案

实现及业务改造

以如下部门结构为例

设计数据结构规则:

为每个节点添加两个值leftValue, rightValue，代表数据的范围,需要满足以下要求：

1. 每个节点的 leftValue < rightValue
2. 子节点的 leftValue > 父节点的 leftValue
3. 子节点的 rightValue < 父节点的 rightValue

则部门结构树初始化如下:

此时可以发现一个部门的所有子部门的 leftValue 和 rightValue 是在父部门的范围内的。

如果想查出指定部门的子部门,执行以下sql即可

select * from dept where tenant_id=xxx and left_value > #{leftValue} and left_value < #{rightValue}

业务伪代码如下

//1. 查询该部门的 leftValue 和 rightValue
Dept dept = queryDeptFromMysql(parentId);
int leftValue = dept.getLeftValue();
int rightValue = dept.getRightValue();

//2. 通过leftValue 和 rightValue 查询子部门
List<Dept> childDepts = queryChildDeptsFromMysql(leftValue, rightValue);

//3.对childDepts组装查询结果

此时就可以实现一次查出指定部门的所有子部门

可以看出其实是"一次查出所有"的变式,加字段后可以实现"指定部门一次查出所有",而且"权限查询接口"这里查出来后不需要做递归封装逻辑

数据结构的增删改查

1.初始化

初始化其实就是对部门树进行深度优先遍历,初始value为1,每次value+1

2.增加子部门

这里业务场景只考虑单部门,多部门可以参考3

a. 新增了一个部门 4-2 他的值分别是 4-1 的（rightValue +1, rightValue+2）即 6,7
b. 因为 3-1 增加了子部门所以他的值范围必定发生变化，变化的增长值就是 2（也是增加的节点个数*2）因为部门 4-2 已经是 6,7 了所以 3-1 部门会发生变化为 3,8
c. 同理后续右边（比发生变化的值大的）节点的值都会发生对应的变化

其实不难看出，每个值大于等于 4-1 的 rightValue +1，（即新增加的 4-2 的 leftValue）的值都增加了 2，无论他是 leftValue 还是 rightValue。

那么新增加一个子节点的逻辑如下

1. 新加部门初始化值后插入

2. 更新右侧所有部门的值

   UPDATE dept
   SET left_value = IF(left_value > #{leftValue}, left_value + #{changeValue}, left_value),
       right_value = IF(right_value > #{leftValue}, right_value + #{changeValue}, right_value)
   where tenant_id= #{tenantId};
   

3.刪除

1. 先将目标部门移除

2. 目标部门右侧的所有值-changeValue(2*删除节点数量)

   UPDATE dept
   SET left_value = IF(left_value > #{leftValue}, left_value - #{changeValue}, left_value),
       right_value = IF(right_value > #{leftValue}, right_value - #{changeValue}, right_value)
   where tenant_ids = #{tenantId};
   

删除部门包含子部门同理(changValue变化)

4.移动部门:

比如将部门3-1转移到部门3-2下

移动部门可以结合删除和新增分为两步走:

1. 先将目标部门移除
2. 将目标部门及其子部门进行初始化
3. 执行插入

相比于单部门插入,前置多了一步初始化,即从父部门的rightValue+1开始深度遍历移动部门,之后走"新增子部门"逻辑插入部门,右侧的值增加changeValue(插入节点数*2)

优化效果

部门树接口(约1.8W个部门)返回速度从20s优化到400ms

本人的思考点

在学习这个技术方案的过程中,较为困惑的一点就是数据结构优化的方案相比一次查出所有然后进行封装的方案有什么改进的地方

1. 零递归处理：通过left_value BETWEEN parent_left AND parent_right即可直接获得完整子树
2. 数据库级过滤：权限校验可直接在SQL层面完成，避免全量数据传输

非常感谢你看到这里,针对这种方案如果还有什么疑惑或思考点,欢迎交流

                  | 需全量重构左右值（移动子树时间复杂度O(n^2)） |

1. 零递归处理：通过left_value BETWEEN parent_left AND parent_right即可直接获得完整子树
2. 数据库级过滤：权限校验可直接在SQL层面完成，避免全量数据传输

非常感谢你看到这里,针对这种方案如果还有什么疑惑或思考点,欢迎交流

文末声明:此技术方案出自师兄夜斗,一位优秀的前辈