巧妙利用数据结构优化部门查询

一、出现的问题

部门树接口超时

二、问题分析

源代码分析

三、解决方案

具体实现思路

四、优化的效果

一、出现的问题

部门树接口超时

无论是在A项目还是在B项目中，都存在类似的页面，其实就是一个部门列表或者叫组织列表。

从页面的展示形式上来看它是一个树状结构。因此在最早的接口设计上也是通过一个接口返回该租户的部门页面进行显示。

接口的返回形式如上。其实也很简单。就是一个通过一个嵌套的对象实现了树

但是在我们私有化的过程中有一些大型的集团客户，他们整个集团的部门数量上万个甚至可能出现 10w 多个部门。因此出现了接口超时20s 都没有结果的情况出现了。

数据权限查询子部门超时

其实，不光有这个场景，在我们的数据权限设计上有一个，这个意思呢就是。如果用户的数据权限为本级及子级的，那这个用户就能查看用户所属部门和该部门子部门下产生的数据。按照目前的实现方式，那我们就要知道这个用户的部门和子部门。

那这个查询子部门的过程也会同样出现超时的情况。

二、问题分析

源代码分析

走读原先的部门树接口逻辑发现，是通过递归查询的方式实现。

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

伪代码逻辑其实就是

// 递归查询函数，参数为要查找的父部门id
List<Department> findDepartmentsByParentId(int parentId) {
    List<Department> departmentList = queryFromMysql(parentId);
  // 用于存放查询结果的列表
    List<Department> result = new List<Department>();
    for (Department department : departmentList) {
        if (department.parentId == parentId) {
            result.add(department);
            // 递归调用，查找当前部门下的子部门，并将结果合并
            List<Department> subDepartments = findDepartmentsByParentId(department.id);
            result.addAll(subDepartments);
        }
    }

    return result;

可能出现问题的原因

子部门数量太多。导致queryFromMysql 这个方法执行的次数多
部门层级深。导致queryFromMysql 这个方法执行的次数多

核心原因其实还是每一次查询子部门都需要通过queryFromMysql这个方法执行一次，类似如下的

select * from department where tenant_id=xxx and parent_id=xxx;

不难发现，问题的根本原因就是 sql 查询执行次数太多了。那么现在问题的核心就是减少 sql 查询的次数。就能解决问题。

当然这里没有考虑改交互的方式，比如一次只查询一级，慢慢展开呢，其实一样，数据权限的子部门那里保持原样还是会超时。

另外，细心的同学可能发现这个代码有问题呀，为什么要从 root 一层一层地查下去，直接用租户 id 查询出所有的部门数据然后再组装成树不是会解决吗。确实可以解决部门树的查询，但是数据权限的子部门那里保持原样还是会超时。

因此要解决的问题核心还是传入任何一个部门 id 能够快速查询出子部门列表。

三、解决方案

加缓存，可能存的数据比较多吧，每一个部门 id 都需要存一份子部门的数据。初始化构建缓存的时候查询依旧慢，这里不讨论了。因为核心问题是解决查询数据库慢的问题
减少查询数据库的次数，从而减少响应时间

具体实现思路

回顾标题，要用数据结构去优化查询，那可能就是在原先表的基础增加一些辅助字段来提高查询的效率。加索引肯定没啥大作用了，因为这里的查询慢是因为次数多而不是因为单词查询数据量大导致。当然索引该加还是得加。

我们可以添加为每个节点添加两个值，代表数据的范围（leftValut, rightValue）

需要满足以下要求：

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

我们按照，这个规则给上面的结构赋值下：

再观察下，怎么去查子部门呢？

比如 2-1（2,9）的子部门为 3-1（3,6）和 3-2（7,8）以及 3-1 的子部门 4-1（4,5）。可以看出 3,4,5,6,7,8 都在 2,9 之间。

因此可以用，2< leftValue/rightValue <9 查询到 3-1,3-2,4-1 .而这几个正好是 2-1 的子部门。

根据我们赋值的限制条件不难看出一个部门的所有子部门的 leftValue 和 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)

//sql 的话就是这样
// select * from dept where tenant_id=xxx and left_value > #{leftValue} and left_value < #{rightValue}

//3. 根据实际情况返回列表，或者组装成树

在我们有这两个左右值的情况下，一条 sql 就能查询出所有符合条件的结果。那么现在的问题来到了如何去为每个部门节点进行赋值。

如何对部门进行赋值

可以分为以下几种情况讨论：（这里只考虑增加修改的情况都是单部门）

初始化 初始化是最简单的，我们只需要以根节点（leftValue 值为 1）为开始深度优先遍历，每次+1 即可。

这里的初始值设置为 1 即可。很简单

新增部门

可以看出变化的部分是

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

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

那么新增加一个子节点可以这样去更新。当然你还要把新加的部门加进去

  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};

changeValue 是什么呢。其实就是变化的节点的个数*2，而这里就是 2，因为只新增了一个子节点 4-2

那如果，新增加的部门不是一个，而是多个呢？

其实这种情况在我们这种页面上不会出现。因为添加部门的时候只会添加一个。