在实际业务中凡是存在“父子关系”或“层级关系”的数据结构通常都可以抽象为层次树模型。例如企业的组织架构与部门体系、员工之间的上下级关系、系统菜单结构、具备继承特性的权限体系、多级分类、文件目录结构以及地址的省市区层级等。接下来你可以速览本文的一二级标题把握本文主要内容层级树需求分析 |—— 树节点的操作设计 |—— 查询能力设计 技术实现方案 |—— 构建层级树 |—— 层级树转回List |—— 树节点的增删改新增、删除、移动 |—— 查询根节点 |—— 查子树 |—— 查叶子节点 |—— 查层级节点 |—— 完整路径 |—— 缓存设计缓存完整的层级树、缓存更新策略、代码实现层级树需求分析先了解一下2个基本核心概念列表List结构本质为二维表结构通过 pidparent_id 指向上一级节点用于表达父子关系。树Tree结构一种层级结构每个节点通过 children 属性包含其所有直接子节点用于表达完整的层级关系。现在我们以这个部门结构为例开始对层级树进行需求分析总部 ├── 技术中心 │ ├── 后端部 │ ├── Java │ ├── Go │ ├── Python │ ├── 前端部 │ └── 测试部 ├── 产品中心 │ ├── 产品部 │ └── 设计部 └── 运营中心 └── 运营部树节点的操作设计树节点的新增新增顶级节点直接作为根节点插入新增子节点挂载到指定父节点下新增父节点本质等价于“新增子节点后再进行结构调整”不存在新增节点还有子树的这种情况需要先新增子节点再移动子树到此节点树节点的删除删除当前节点及其子树只删除某个节点如果有子树则要进行子树的升级依然保持树的层次结构树节点的移动修改任意节点的移动依然保持树的层次结构移动节点及其子树子树上的任意节点自动升降级移动节点子树不跟着同步子树自动升级查询能力设计根节点查询获取所有根节点层级最顶层节点判断某个节点是否为根节点子树查询获取某个节点的完整子树包含自身并重建为层级树结构返回叶子节点查询获取所有叶子节点层级最底层节点获取指定子树的叶子节点判断某节点是否为叶子节点层级查询查询指定层级的所有节点查询某节点的同级节点完整路径查询查询根节点到指定节点的完整路径并按层级结构展示查询某节点到其所有子节点的路径集合技术实现方案在正式进入技术方案的设计之前我们必须要先确定表结构。确定了表的字段以后才能够更好的进行技术方案的设计与实现。建议先下载完整的代码Demo更方便理解https://github.com/HackyleShawe/JavaBackEndDemos/tree/master/TechSolution/hierarchy-treeCREATE TABLE dept ( id BIGINT PRIMARY KEY AUTO_INCREMENT, name VARCHAR(100) DEFAULT COMMENT 部门名称, pid BIGINT DEFAULT 0 COMMENT 父部门ID顶级部门为0, weight INT DEFAULT 0 COMMENT 排序权重值越小越靠前, ancestor_path VARCHAR(500) DEFAULT COMMENT 祖级节点从根节点到当前节点的父节点只包含父级不包含本身例如/1/3, level INT DEFAULT 1 COMMENT 层级从1开始, INDEX idx_pid (pid), INDEX idx_ancestor_path (ancestor_path) );如何设计祖级路径path字段包含父级也包含本身所有父节点完整路径就是path字段本身所有子节点SELECT * FROM dept WHERE path LIKE 1/3/%;#ID为3的部门的所有子节点ancestor祖级字段只包含父级不包含本身查所有祖节点完整路径ancestor 自己本身通过 ancestors 可以直接知道该部门的所有父级部门链路而不用递归查询多次 parent_id。例如102 的 ancestors0,100,101说明它的上级路径是「总公司 → 技术部 → 开发一组」。所有子节点直接通过 ancestors LIKE %,deptId,% 来匹配。例如要查找「技术部(101)」的所有子部门就可以写 WHERE ancestor LIKE %,101,% OR dept_id 101;为什么不用path而用ancestor两者含义相似path字段包含父级也包含本身ancestor祖级字段只包含父级不包含本身在新增节点时如果使用path则新增成功后还要回写path父path自己因为新增之前不知道自己的id是多少通过ancestor字段和id字段就可以计算出path并且冗余没有实际意义ancestor字段的内容形式设计祖级之间使用逗号分割(1,2,3)查找时使用FIND_IN_SET(2, ancestor)会全表扫描祖级之间包括收尾、使用逗号分割(,1,2,3,)LIKE %,2,%不走索引使用斜杠分割(/1/2/3)/1/2/%走索引前缀匹配结论使用斜杠的形式这样也可以直观体现层级为该个字段创建索引查询时也可以走索引构建层级树接下来我将介绍4种构建树的实现方式我们从最朴实的双层for开始。双层for外层for找根节点内层for找每个节点的子节点最终每个元素都会找一遍所有最终得到层级树时间复杂度N^2空间复杂度N/** * param deptList 传入要构建树的实体列表例如deptMapper.selectList(null); * return 层级树 */ public ListDeptVo buildTreeByFor(ListDeptVo deptList) { ListDeptVo res new ArrayList(); if(CollectionUtils.isEmpty(deptList)){ return res; } for (DeptVo deptEntity : deptList) { if(deptEntity.getPid() 0L) { res.add(deptEntity); } for (DeptVo entity : deptList) { if(deptEntity.getChildren() null) { deptEntity.setChildren(new ArrayList()); } if(Objects.equals(entity.getPid(), deptEntity.getId())) { deptEntity.getChildren().add(entity); } } } return res; }Map转换分析在双层for的解法中由于内层for也需要遍历List造成时间复杂度上身为平方级如果内层for不需要遍历完整的List而是事先预处理到Map中寻找时直接从Map中获取则时间复杂度降为LogN主要思路先转换Mappid, 子节点遍历list从map中找子节点时间复杂度第一次遍历构建MapN第二次遍历从Map中找子节点N*1为什么从Map中查找的时间复杂度是O(1)由于Map中的Key是不重复的不存在哈希冲突的情况可以根据key的哈希值直接从桶中获取复杂度为O(1)public ListDeptVo buildTreeByMap(ListDeptVo deptList) { ListDeptVo res new ArrayList(); if(CollectionUtils.isEmpty(deptList)){ return res; } MapLong, ListDeptVo pidMap deptList.stream().collect(Collectors.groupingBy(DeptVo::getPid)); for (DeptVo deptEntity : deptList) { if(deptEntity.getPid() 0L) { res.add(deptEntity); } ListDeptVo children pidMap.get(deptEntity.getId()); deptEntity.setChildren(CollectionUtils.isEmpty(children) ? new ArrayList() : children); } return res; }递归先转换Mappid, 子节点从Map中获取根节点遍历根节点从Map中找子节点。如果根节点有子节点则递归执行时间复杂度转换MapO(N)从Map获取O(1)递归至多执行(N-根节点个数)次O(N)public ListDeptVo buildTreeByRe(ListDeptVo deptList) { ListDeptVo res new ArrayList(); if(CollectionUtils.isEmpty(deptList)){ return res; } MapLong, ListDeptVo pidMap deptList.stream().collect(Collectors.groupingBy(DeptVo::getPid)); ListDeptVo rootDeptList pidMap.get(0L); //获取根节点 for (DeptVo deptEntity : rootDeptList) { findChildren(deptEntity, pidMap); } return rootDeptList; } private void findChildren(DeptVo deptEntity, MapLong, ListDeptVo pidMap) { if(deptEntity null) { return; } ListDeptVo chaild pidMap.get(deptEntity.getId()); deptEntity.setChildren(CollectionUtils.isEmpty(chaild) ? new ArrayList() : chaild); for (DeptVo child : deptEntity.getChildren()) { findChildren(child, pidMap); } }栈先转换Mappid, 子节点从Map中获取根节点并且压栈循环出栈从Map中找当前出栈元素的所有子元素如果当前出栈元素的child不为空则再压入栈中。这一步的目的是再一次找child的子元素时间复杂度转换MapO(N)从Map获取O(1)压出栈至多执行(N-根节点个数)次O(N)public ListDeptVo buildTreeByStack(ListDeptVo deptList) { ListDeptVo res new ArrayList(); if(CollectionUtils.isEmpty(deptList)){ return res; } MapLong, ListDeptVo pidMap deptList.stream().collect(Collectors.groupingBy(DeptVo::getPid)); StackDeptVo stack new Stack(); ListDeptVo rootDeptList pidMap.get(0L); //获取根节点 stack.addAll(rootDeptList); while (!stack.isEmpty()) { DeptVo deptEntity stack.pop(); ListDeptVo child pidMap.get(deptEntity.getId()); deptEntity.setChildren(CollectionUtils.isEmpty(child) ? new ArrayList() : child); if(CollectionUtil.isNotEmpty(child)) { stack.addAll(child); } } return rootDeptList; }层级树转回List主要有两种实现方式思路都是一致的递归实现遍历层级树节点一个树节点如果有子树则再次递归此子树直到没有子树为止栈实现依次遍历树当前节点为Cur如果Cur有子树压栈将Cur收集到某个List依次弹出栈元素将弹出的元素放入List如果弹出的元素还有子树继续压栈树节点的增删改对树结构的增删改操作中一般思路是先构建节点再增删list中的节点、最后才构建层级树。关乎节点的增删改需要注意的点集群部署使用分布式锁保证同一时刻只有一个请求进行DB修改更新数据库时放在最后批量操作放在一个事务里新增pid字段新增顶级节点pid置为0直接新增。新增子节点给谁新增节点pid就是谁需要检查pid是否存在ancestor_path字段新增顶级节点ancestor_path为空直接新增新增子节点ancestor_path 父ancestor_path 父IDlevel level1/** * 新增节点并返回树 * 新增顶级节点则直接新增 * 新增子节点