在实际业务中，凡是存在“父子关系”或“层级关系”的数据结构，通常都可以抽象为层次树模型。例如：企业的组织架构与部门体系、员工之间的上下级关系、系统菜单结构、具备继承特性的权限体系、多级分类、文件目录结构，以及地址的省市区层级等。
接下来，你可以速览本文的一二级标题，把握本文主要内容：
层级树需求分析
|—— 树节点的操作设计
|—— 查询能力设计
技术实现方案
|—— 构建层级树
|—— 层级树转回List
|—— 树节点的增删改：新增、删除、移动
|—— 查询根节点
|—— 查子树
|—— 查叶子节点
|—— 查层级节点
|—— 完整路径
|—— 缓存设计：缓存完整的层级树、缓存更新策略、代码实现先了解一下2个基本核心概念
现在我们以这个部门结构为例，开始对层级树进行需求分析：
总部
├── 技术中心
│ ├── 后端部
│ ├── 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字段：包含父级，也包含本身
ancestor（祖级）字段：只包含父级，不包含本身
为什么不用path，而用ancestor？
ancestor字段的内容形式设计：
接下来我将介绍4种构建树的实现方式，我们从最朴实的双层for开始。
双层for
/**
* @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转换
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;
}递归
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);
}
}栈
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中的节点、最后才构建层级树。
关乎节点的增删改，需要注意的点
pid字段
ancestor_path字段
/**
* 新增节点，并返回树
* 新增顶级节点，则直接新增
* 新增子节点
* 新增父节点，等价于新增子节点
* 不存在新增节点还有子树的这种情况，需要先新增子节点，再移动子树到此节点
*/
@Transactional
public DeptEntity add(DeptAddDto deptAddDto) {
DeptEntity deptEntity = new DeptEntity();
Long pid = deptAddDto.getPid();
if(pid == null || pid < 1) { //表示添加顶级节点
deptEntity.setPid(0L);
deptEntity.setAncestorPath("");
deptEntity.setLevel(1);
} else {
//检查pid是否存在
DeptEntity existEntity = deptMapper.selectById(pid);
if(existEntity == null) {
throw new IllegalArgumentException("父部门不存在");
}
deptEntity.setPid(pid);
deptEntity.setAncestorPath(existEntity.getAncestorPath()+"/"+existEntity.getId());
deptEntity.setLevel(existEntity.getLevel()+1);
}
deptEntity.setName(deptAddDto.getName());
deptEntity.setWeight(deptAddDto.getWeight());
int inserted = deptMapper.insert(deptEntity);
if(inserted != 1) {
throw new IllegalStateException("新增失败");
}
return deptEntity;
}pid字段
ancestor_path字段
UPDATE dept
SET ancestor_path = REPLACE(ancestor_path , '/1/2/5', '/1/5') #把path中的'/1/2/5'替换为'/1/5'
WHERE path LIKE '/1/2/5%';@Transactional
public List<DeptVo> delWithSubTree(long id) {
DeptEntity dept = deptMapper.selectById(id);
if(dept == null) {
throw new IllegalArgumentException("节点不存在");
}
int deleted = deptMapper.deleteById(dept.getId());
if(deleted < 1) {
throw new RuntimeException("删除节点失败");
}
boolean exists = this.existsChildren(id);
if(exists) {
String ancestorPath = dept.getAncestorPath()+"/"+dept.getId();
int deletedSubTree = deptMapper.delWithSubTree(id, ancestorPath);
log.info("删除子树deleted={}", deletedSubTree);
if(deletedSubTree < 1) {
throw new RuntimeException("删除子树失败");
}
}
return deptBuildTreeService.buildTree();
}
@Transactional
public List<DeptVo> delWithoutSubTree(long id) {
DeptEntity dept = deptMapper.selectById(id);
if(dept == null) {
throw new IllegalArgumentException("节点不存在");
}
int deleted = deptMapper.deleteById(dept.getId());
if(deleted < 1) {
throw new RuntimeException("删除节点失败");
}
boolean exists = this.existsChildren(id);
if (exists) {
long oldPid = dept.getId();
long newPid = dept.getPid();
int updatedPId = deptMapper.updateChildrenPid(oldPid, newPid);
if (updatedPId < 1) {
throw new RuntimeException("更新子节点失败");
}
String ancestorPath = dept.getAncestorPath();
String curPath = dept.getAncestorPath() + "/" + dept.getId();
int updatedChildren = deptMapper.updateSubTreeAncestorPath(ancestorPath, curPath, -1);
if (updatedChildren < 1) {
throw new RuntimeException("更新子树失败");
}
}
return deptBuildTreeService.buildTree();
}
/**
* 检查某个节点是否有子节点，有子节点就一定有子树
*/
private boolean existsChildren(long pid) {
Long pidCount = deptMapper.selectCount(Wrappers.<DeptEntity>lambdaQuery().eq(DeptEntity::getPid, pid));
return pidCount != null && pidCount > 0;
}pid字段：任意节点的移动，依然保持树的层次结构
ancestor_path字段：任意节点的移动，依然保持树的层次结构
UPDATE dept
SET ancestor_path = REPLACE(ancestor_path, '/1/2/5', '/1/3/5') #把path中的'/1/2/5'替换为'/1/3/5'
WHERE ancestor_path LIKE '/1/2/5%';
例如：/1/2/5/8/11，自动变成：/1/3/5/8/11，所有子节点全部自动跟着移动。/**
* 移动节点，子树也同步跟着移动
* @param nodeId 当前移动的节点是谁
* @param newParentId 新移动的节点的父节点是谁
*/
public List<DeptVo> moveWithSubTree(Long nodeId, Long newParentId) {
if(nodeId == null || newParentId == null) {
throw new IllegalArgumentException("参与移动的节点不能为空");
}
if(nodeId.equals(newParentId)) {
throw new IllegalArgumentException("不能自己移动到自己");
}
DeptEntity node = deptMapper.selectById(nodeId);
if(node == null) {
throw new IllegalArgumentException("移动的节点不存在");
}
DeptEntity newParent = deptMapper.selectById(newParentId);
if(newParent == null) {
throw new IllegalArgumentException("新移动的父节点不存在");
}
//判定是否移动到自己的子树，防止回环
List<DeptEntity> subTreeList = this.getSubTreeList(nodeId);
if(CollectionUtil.isNotEmpty(subTreeList)) {
Set<Long> idSet = subTreeList.stream().map(DeptEntity::getId).collect(Collectors.toSet());
if(idSet.contains(newParentId)) {
throw new IllegalArgumentException("不能移动到自己的子树");
}
}
boolean exists = this.existsChildren(node.getId());
if (exists) {
String ancestorPath = newParent.getAncestorPath() + "/" + newParentId + "/" + nodeId;
String curPath = node.getAncestorPath() + "/" + node.getId();
int levelDiff = (newParent.getLevel() + 1) - node.getLevel();
// 更新子树
int updatedChildren = deptMapper.updateSubTreeAncestorPath(ancestorPath, curPath, levelDiff);
if (updatedChildren < 1) {
throw new RuntimeException("更新子树失败");
}
}
// 更新当前节点
node.setPid(newParentId);
node.setAncestorPath(newParent.getAncestorPath() + "/" + newParentId);
node.setLevel(newParent.getLevel() + 1);
int updated = deptMapper.updateById(node);
if(updated < 1) {
throw new RuntimeException("更新节点失败");
}
return deptBuildTreeService.buildTree();
}
/**
* 移动节点，子树不跟着同步，子树自动升降级
* @param nodeId 当前移动的节点是谁
* @param newParentId 新移动的节点的父节点是谁
*/
public List<DeptVo> moveWithoutSubTree(Long nodeId, Long newParentId) {
if(nodeId == null || newParentId == null) {
throw new IllegalArgumentException("参与移动的节点不能为空");
}
if(nodeId.equals(newParentId)) {
throw new IllegalArgumentException("不能自己移动到自己");
}
DeptEntity node = deptMapper.selectById(nodeId);
if(node == null) {
throw new IllegalArgumentException("移动的节点不存在");
}
DeptEntity newParent = deptMapper.selectById(newParentId);
if(newParent == null) {
throw new IllegalArgumentException("新移动的父节点不存在");
}
boolean exists = this.existsChildren(node.getId());
if (exists) {
//获取当前节点的上一级，便于直接子节点挂载
DeptEntity parent = deptMapper.selectById(node.getPid());
//更新直接子节点的pid
long oldPid = node.getId();
long newPid = node.getPid();
int updateChildrenPid = deptMapper.updateChildrenPid(oldPid, newPid);
if(updateChildrenPid < 1) {
throw new RuntimeException("更新子节点的pid失败");
}
//更新子树的AncestorPath和level
String ancestorPath = node.getAncestorPath();
String curPath = node.getAncestorPath() + "/" + nodeId;
//int levelDiff = (newParent.getLevel() + 1) - node.getLevel();
int updateSubTree = deptMapper.updateSubTreeAncestorPath(ancestorPath, curPath, -1);
if(updateSubTree < 1) {
throw new RuntimeException("更新子树失败");
}
}
// 更新当前节点
node.setPid(newParentId);
node.setAncestorPath(newParent.getAncestorPath() + "/" + newParentId);
node.setLevel(newParent.getLevel() + 1);
int updated = deptMapper.updateById(node);
if(updated < 1) {
throw new RuntimeException("更新节点失败");
}
return deptBuildTreeService.buildTree();
}获取全部根节点(层次最高的)
查表，pid为0的
判断某个节点是否为根节点
查表，pid为0的，并且id=目标节点
查某个节点的所有子节点，并构建为树
实现思路：
eptVo> getSubTree(Long id) {
if(id == null || id < 1) {
return null;
}
DeptEntity deptEntity = deptMapper.selectById(id);
if(deptEntity == null) {
throw new RuntimeException("节点不存在");
}
List<DeptEntity> subTreeList = deptMapper.getSubTree(deptEntity.getAncestorPath()+"/"+deptEntity.getId());
if(CollectionUtil.isEmpty(subTreeList)) {
throw new RuntimeException("该节点没有子树");
}
List<DeptVo> deptVos = BeanCopyUtils.copyList(subTreeList, DeptVo.class);
deptVos.add(BeanCopyUtils.copy(deptEntity, DeptVo.class));
long pid = deptEntity.getId();
List<DeptVo> subTree = deptBuildTreeService.buildTree(deptVos, pid);
return subTree;
}
SELECT id, name, pid, weight, ancestor_path, level
FROM dept
WHERE ancestor_path LIKE CONCAT(#{ancestorPath}, '%')获取全部叶子节点(层次最低的)
获取某个子树的叶子节点：使用递归查询获取某节点的子树节点，于是这个问题回归到上文的“获取全部的叶子节点”。
判定某个节点是否为叶子节点：在获取全部叶子节点的基础SQL上，添加一个id为某节点的判定条件
SELECT d.*
FROM dept d
WHERE NOT EXISTS (
SELECT 1
FROM dept child
WHERE child.pid = d.id
);
SELECT d.*
FROM dept d
LEFT JOIN dept child ON child.pid = d.id
WHERE child.id IS NULL;查层级节点
查根节点到某节点的完整路径，并且按层级路径展示
都有那些数据需要缓存？
所以，有以下的缓存设计：
情况1：极小体量 + 极低频修改
情况2：海量节点 + 高频动态修改
什么时候用Set？只关注谁是谁的子节点
什么时候用Zset？强调顺序、权重：组织架构顺序、菜单顺序、地区展示顺序
注意事项
新增节点
删除节点
移动节点
/**
* 缓存场景：
* 查整棵树（组织架构）：key: sys:dept:tree；value: JSON（完整树结构）
* 查子节点（注意不是子树，而是儿子节点）：key: sys:dept:children:{pid}；value: List<Dept>
* 查某节点子树：key: sys:dept:subtree:{id}；value: List<Dept>（整个子树）
* 查节点（热节点）：
* 单个缓存方案：Key：sys:dept:{id}；value:JSON-Dept
* 全量缓存方案：key: sys:dept:map；field: deptId；value: Dept JSON
*
*/
@Slf4j
@Service
public class DeptCacheService {
private static final String TREE_KEY = "sys:dept:tree";
private static final String TREE_CHILDREN_PREFIX = "sys:dept:children:";
private static final String TREE_SUBTREE_PREFIX = "sys:dept:subtree:";
private static final String TREE_MAP_KEY = "sys:dept:map";
@Autowired
private RedisTemplate<String, Object> redisTemplate;
public void putTree(List<DeptVo> deptVos) {
//这种方式有什么问题？
//delete + 写入：不是原子操作，导致读请求可能会拿到空数据
//List 结构不适合这个场景
//没有防击穿/空保护：如果 refresh 失败，整个 KEY 直接没了
//redisTemplate.delete(KEY);
//redisTemplate.opsForList().rightPushAll(KEY, deptVos);
//redisTemplate.expire(KEY, 12, TimeUnit.HOURS);
redisTemplate.opsForValue().set(TREE_KEY, JSON.toJSONString(deptVos), 12, TimeUnit.HOURS);
}
public String getTree() {
Object object = redisTemplate.opsForValue().get(TREE_KEY);
return object == null ? null : String.valueOf(object);
}
public void evictTree() {
redisTemplate.delete(TREE_KEY);
}
public void putChildren(long pid, List<DeptVo> children) {
redisTemplate.opsForValue().set(TREE_CHILDREN_PREFIX+ pid, JSON.toJSONString(children), 12, TimeUnit.HOURS);
}
public List<DeptVo> getChildren(long pid) {
Object object = redisTemplate.opsForValue().get(TREE_CHILDREN_PREFIX+ pid);
if (object == null) {
return null;
}
return JSONArray.parseArray(String.valueOf(object), DeptVo.class);
}
public void evictChildren(long pid) {
redisTemplate.delete(TREE_CHILDREN_PREFIX+ pid);
}
public void evictAllChildren() {
Set<String> keys = redisTemplate.keys(TREE_CHILDREN_PREFIX + "*");
if (!keys.isEmpty()) {
redisTemplate.delete(keys);
}
}
public void putSubTree(long pid, List<DeptVo> subTree) {
redisTemplate.opsForValue().set(TREE_SUBTREE_PREFIX+ pid, JSON.toJSONString(subTree), 12, TimeUnit.HOURS);
}
public List<DeptVo> getSubTree(long pid) {
Object object = redisTemplate.opsForValue().get(TREE_SUBTREE_PREFIX+ pid);
if (object == null) {
return null;
}
return JSONArray.parseArray(String.valueOf(object), DeptVo.class);
}
public void evictSubTree(long id) {
redisTemplate.delete(TREE_SUBTREE_PREFIX+ id);
}
public void evictAllSubTree() {
Set<String> keys = redisTemplate.keys(TREE_SUBTREE_PREFIX + "*");
if (!keys.isEmpty()) {
redisTemplate.delete(keys);
}
}
public void put(List<DeptVo> deptVos) {
if(CollectionUtil.isEmpty(deptVos)) {
return;
}
Map<Long, DeptVo> deptVoMap = deptVos.stream().collect(Collectors.toMap(DeptVo::getId, deptVo -> deptVo));
redisTemplate.opsForHash().putAll(TREE_MAP_KEY, deptVoMap);
redisTemplate.expire(TREE_MAP_KEY,12,TimeUnit.HOURS);
}
public DeptVo get(long id) {
Object object = redisTemplate.opsForHash().get(TREE_MAP_KEY, id);
return object == null ? null : JSONObject.parseObject(JSON.toJSONString(object), DeptVo.class);
}
public void evict(long id) {
redisTemplate.opsForHash().delete(TREE_MAP_KEY, id);
}
}本文结束。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。