企业官网建设流程全解析

在实际业务中，凡是存在“父子关系”或“层级关系”的数据结构，通常都可以抽象为层次树模型。例如：企业的组织架构与部门体系、员工之间的上下级关系、系统菜单结构、具备继承特性的权限体系、多级分类、文件目录结构，以及地址的省市区层级等。

接下来，你可以速览本文的一二级标题，把握本文主要内容：

层级树需求分析 |—— 树节点的操作设计 |—— 查询能力设计 技术实现方案 |—— 构建层级树 |—— 层级树转回List |—— 树节点的增删改：新增、删除、移动 |—— 查询根节点 |—— 查子树 |—— 查叶子节点 |—— 查层级节点 |—— 完整路径 |—— 缓存设计：缓存完整的层级树、缓存更新策略、代码实现

层级树需求分析

先了解一下2个基本核心概念

• 列表（List）结构：本质为二维表结构，通过 pid（parent_id） 指向上一级节点，用于表达父子关系。
• 树（Tree）结构：一种层级结构，每个节点通过 children 属性包含其所有直接子节点，用于表达完整的层级关系。

现在我们以这个部门结构为例，开始对层级树进行需求分析：

总部 ├── 技术中心 │ ├── 后端部 │ ├── Java │ ├── Go │ ├── Python │ ├── 前端部 │ └── 测试部 ├── 产品中心 │ ├── 产品部 │ └── 设计部 └── 运营中心 └── 运营部

树节点的操作设计

树节点的新增

• 新增顶级节点：直接作为根节点插入
• 新增子节点：挂载到指定父节点下
• 新增父节点：本质等价于“新增子节点后再进行结构调整”
• 不存在新增节点还有子树的这种情况，需要先新增子节点，再移动子树到此节点

树节点的删除

• 删除当前节点及其子树
• 只删除某个节点，如果有子树，则要进行子树的升级，依然保持树的层次结构

树节点的移动（修改）：任意节点的移动，依然保持树的层次结构

• 移动节点及其子树，子树上的任意节点自动升降级
• 移动节点，子树不跟着同步，子树自动升级

查询能力设计

根节点查询

• 获取所有根节点（层级最顶层节点）
• 判断某个节点是否为根节点

子树查询

• 获取某个节点的完整子树（包含自身）
• 并重建为层级树结构返回

叶子节点查询

• 获取所有叶子节点（层级最底层节点）
• 获取指定子树的叶子节点
• 判断某节点是否为叶子节点

层级查询

• 查询指定层级的所有节点
• 查询某节点的同级节点

完整路径查询

• 查询根节点到指定节点的完整路径，并按层级结构展示
• 查询某节点到其所有子节点的路径集合

技术实现方案

在正式进入技术方案的设计之前，我们必须要先确定表结构。确定了表的字段以后才能够更好的进行技术方案的设计与实现。

建议先下载完整的代码Demo，更方便理解：https://github.com/HackyleShawe/JavaBackEndDemos/tree/master/TechSolution/hierarchy-tree

CREATE 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 的 ancestors=0,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 List<DeptVo> buildTreeByFor(List<DeptVo> deptList) { List<DeptVo> 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
• 主要思路：先转换Map<pid, 子节点>，遍历list从map中找子节点
• 时间复杂度：第一次遍历构建Map：N；第二次遍历从Map中找子节点：N*1
• 为什么从Map中查找的时间复杂度是O(1)？由于Map中的Key是不重复的，不存在哈希冲突的情况，可以根据key的哈希值直接从桶中获取，复杂度为O(1)

public List<DeptVo> buildTreeByMap(List<DeptVo> deptList) { List<DeptVo> res = new ArrayList<>(); if(CollectionUtils.isEmpty(deptList)){ return res; } Map<Long, List<DeptVo>> pidMap = deptList.stream().collect(Collectors.groupingBy(DeptVo::getPid)); for (DeptVo deptEntity : deptList) { if(deptEntity.getPid() == 0L) { res.add(deptEntity); } List<DeptVo> children = pidMap.get(deptEntity.getId()); deptEntity.setChildren(CollectionUtils.isEmpty(children) ? new ArrayList<>() : children); } return res; }

递归

• 先转换Map<pid, 子节点>
• 从Map中获取根节点
• 遍历根节点，从Map中找子节点。如果根节点有子节点，则递归执行
• 时间复杂度：转换Map：O(N)；从Map获取：O(1)，递归至多执行(N-根节点个数)次：O(N)

public List<DeptVo> buildTreeByRe(List<DeptVo> deptList) { List<DeptVo> res = new ArrayList<>(); if(CollectionUtils.isEmpty(deptList)){ return res; } Map<Long, List<DeptVo>> pidMap = deptList.stream().collect(Collectors.groupingBy(DeptVo::getPid)); List<DeptVo> rootDeptList = pidMap.get(0L); //获取根节点 for (DeptVo deptEntity : rootDeptList) { findChildren(deptEntity, pidMap); } return rootDeptList; } private void findChildren(DeptVo deptEntity, Map<Long, List<DeptVo>> pidMap) { if(deptEntity == null) { return; } List<DeptVo> chaild = pidMap.get(deptEntity.getId()); deptEntity.setChildren(CollectionUtils.isEmpty(chaild) ? new ArrayList<>() : chaild); for (DeptVo child : deptEntity.getChildren()) { findChildren(child, pidMap); } }

栈

• 先转换Map<pid, 子节点>
• 从Map中获取根节点，并且压栈
• 循环出栈
  • 从Map中找当前出栈元素的所有子元素
  • 如果当前出栈元素的child不为空，则再压入栈中。这一步的目的是，再一次找child的子元素
• 时间复杂度：转换Map：O(N)；从Map获取：O(1)，压出栈至多执行(N-根节点个数)次：O(N)

public List<DeptVo> buildTreeByStack(List<DeptVo> deptList) { List<DeptVo> res = new ArrayList<>(); if(CollectionUtils.isEmpty(deptList)){ return res; } Map<Long, List<DeptVo>> pidMap = deptList.stream().collect(Collectors.groupingBy(DeptVo::getPid)); Stack<DeptVo> stack = new Stack<>(); List<DeptVo> rootDeptList = pidMap.get(0L); //获取根节点 stack.addAll(rootDeptList); while (!stack.isEmpty()) { DeptVo deptEntity = stack.pop(); List<DeptVo> child = pidMap.get(deptEntity.getId()); deptEntity.setChildren(CollectionUtils.isEmpty(child) ? new ArrayList<>() : child); if(CollectionUtil.isNotEmpty(child)) { stack.addAll(child); } } return rootDeptList; }

层级树转回List

主要有两种实现方式，思路都是一致的：

递归实现：遍历层级树节点，一个树节点如果有子树，则再次递归此子树，直到没有子树为止

栈实现

1. 依次遍历树，当前节点为Cur
   1. 如果Cur有子树，压栈
   2. 将Cur收集到某个List
2. 依次弹出栈元素
   1. 将弹出的元素放入List
   2. 如果弹出的元素还有子树，继续压栈

树节点的增删改

对树结构的增删改操作中，一般思路是：先构建节点，再增删list中的节点、最后才构建层级树。

关乎节点的增删改，需要注意的点

• 集群部署使用分布式锁，保证同一时刻只有一个请求进行DB修改
• 更新数据库时放在最后批量操作，放在一个事务里

新增

pid字段

• 新增顶级节点，pid置为0，直接新增。
• 新增子节点：给谁新增节点，pid就是谁，需要检查pid是否存在

ancestor_path字段

• 新增顶级节点，ancestor_path为空，直接新增
• 新增子节点，ancestor_path = 父ancestor_path + 父ID；level = level+1

/** * 新增节点，并返回树 * 新增顶级节点，则直接新增 * 新增子节点