记一次若依项目组装树型结构数据的效率优化

背景

最近公司的项目使用了若依框架做开发，发现部门管理功能的部门如果有3万笔记录时，查询部门信息并组装为父子结构时运行特别缓慢，本地运行需要3分钟才能加载出来，因此接到优化的工作。

代码展示

1. 首先看看表结构是这么定义的（下列代码仅保留当前博文分析的内容）

create table sys_dept (dept_id           bigint(20)      not null auto_increment    comment '部门id',parent_id         bigint(20)      default 0                  comment '父部门id',ancestors         varchar(50)     default ''                 comment '祖级列表',dept_name         varchar(30)     default ''                 comment '部门名称',order_num         int(4)          default 0                  comment '显示顺序',status            char(1)         default '0'                comment '部门状态（0正常 1停用）'-- 省略其他字段primary key (dept_id)
) engine=innodb auto_increment=1 comment = '部门表';

2. 父子结构的类对象如下

public class TreeSelect implements Serializable {/** 节点ID */private Long id;/** 节点名称 */private String label;/** 子节点 */private List<TreeSelect> children;// 省略setter/getter等其他内容
}

3. 查询数据就是简单的把sys_dept表内容全查出来，然后在java中遍历每行找到子级，找子级的代码如下

/*** 建立部门树型结构数据, 用于前端使用el-tree进行展示* @param depts 所有部门结果集*/
public List<TreeSelect> buildDeptTreeSelect(List<SysDept> depts) {List<SysDept> deptTrees = buildDeptTree(depts);return deptTrees.stream().map(TreeSelect::new).collect(Collectors.toList());
}
/*** 找到每个部门记录的子级集合, 建立部门树型结构* @param dept 查询条件*/
public List<SysDept> buildDeptTree(List<SysDept> depts) {List<SysDept> returnList = new ArrayList<SysDept>();List<Long> tempList = depts.stream().map(SysDept::getDeptId).collect(Collectors.toList());for (SysDept dept : depts) {// 如果是顶级节点, 遍历该父节点的所有子节点if (!tempList.contains(dept.getParentId())) {recursionFn(depts, dept);returnList.add(dept);}}if (returnList.isEmpty()) {returnList = depts;}return returnList;
}
/*** 递归列表*/
private void recursionFn(List<SysDept> list, SysDept t) {// 得到子节点列表List<SysDept> childList = getChildList(list, t);t.setChildren(childList);for (SysDept tChild : childList) {if (hasChild(list, tChild)) {recursionFn(list, tChild);}}
}
/*** 得到子节点列表*/
private List<SysDept> getChildList(List<SysDept> list, SysDept t) {List<SysDept> tlist = new ArrayList<SysDept>();Iterator<SysDept> it = list.iterator();while (it.hasNext()) {SysDept n = (SysDept) it.next();if (StringUtils.isNotNull(n.getParentId()) && n.getParentId().longValue() == t.getDeptId().longValue()) {tlist.add(n);}}return tlist;
}/*** 判断是否有子节点*/
private boolean hasChild(List<SysDept> list, SysDept t) {return getChildList(list, t).size() > 0;
}

问题分析

通过分析上面的代码可以得出以下问题：

1. 使用List集合进行查找，时间复杂度高：buildDeptTree中先通过遍历获取所有主键到List集合中，用于后面再次遍历时用contains判断是否有父级元素在查询结果集中，此处的List<Long> tempList如果用Set类型来去重和查找元素效率会更高，因为List查找的时间复杂度是O(n)，Set的时间复杂度为O(1)
2. 重复获取子元素：在recursionFn中的hasChild()方法判断是否存在子元素是再执行一遍getChildList()方法遍历获取所有子级，然后判断子级的长度，此处感觉白白花费了比较多时间
3. 通过List集合遍历获取子元素效率比较低，要获取每个元素的子级，每次都要遍历所有元素

解决思路

1. 问题1，将List修改为Set即可
2. 问题2和3，既然用List找到子级遍历很慢，能不能也用Set集合来减少遍历的次数，将查询出的数据按父级（parentId）分组，分组后的对象为groupByParentIdDepts，这样一来分组后的值就是每个父级的子元素，获取每个元素的子级只需要一次遍历：用当前元素的deptId作为键就能直接取到子元素，而判断是否有子元素也不用每次都遍历了，直接通过groupByParentIdDepts获取值的长度大于0即可。

代码修改

修改的内容就集中在buildDeptTree和recursionFn两个方法了（想直接获取修改后的项目代码可以看文章最后的相关链接哈~）

public List<SysDept> buildDeptTree(List<SysDept> depts) {List<SysDept> returnList = new ArrayList<SysDept>();List<Long> tempList = depts.stream().map(SysDept::getDeptId).collect(Collectors.toList());// 按父级分组Map<Long, List<SysDept>> groupByParentIdDepts = depts.stream().filter(dept -> dept.getParentId() != null).collect(Collectors.groupingBy(SysDept::getParentId));for (SysDept dept : depts) {// 如果是顶级节点, 遍历该父节点的所有子节点if (!tempList.contains(dept.getParentId())) {recursionFn(groupByParentIdDepts, dept);returnList.add(dept);}}if (returnList.isEmpty()) {returnList = depts;}return returnList;
}private void recursionFn(Map<Long, List<SysDept>> groupByParentIdDepts, SysDept t) {// 得到子节点列表List<SysDept> childList = groupByParentIdDepts.get(t.getDeptId());if (childList != null) {t.setChildren(childList);// 为每个子节点递归找到子节点for (SysDept tChild : childList) {recursionFn(groupByParentIdDepts, tChild);}} else {t.setChildren(new ArrayList<>(0));}
}
// hasChild方法也可以直接省略了。

总结

1. 这次的优化其实有点空间换时间的意思，将每次遍历的元素缓存到Map中，然后再通过Map去快速获取子级元素，不知道上面的表述有没有说的够清楚。
2. 再就是这个框架大大减少了我们开发后台系统的开发时间，有一点小问题也是瑕不掩瑜；毕竟当数据量低的时候感知不大，前期开发者可能也没想到有这么大数据量的部门，为了开发效率也无可厚非啦。
3. 另外前端接收那么大数据怎么展示呢，我们是引入了@wchbrad/vue-easy-tree虚拟加载树组件来展示的，不然前端也要卡顿好久，这里就不过多阐述了，下文也有链接，可以直接跳转查看官方文档

大家有不同的见解都可以留下你们的评论哈，或者直接到gitee上直接拉取修改也行。

相关链接

若依gitee
在gitee克隆后修改的代码
el-tree虚拟加载树组件：vue-easy-tree