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

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

层级树需求分析
 |—— 树节点的操作设计
 |—— 查询能力设计
技术实现方案
 |—— 构建层级树
 |—— 层级树转回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

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

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

栈实现

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

树节点的增删改

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

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

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

新增

pid字段

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

ancestor_path字段

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

/**
 * 新增节点，并返回树
 * 新增顶级节点，则直接新增
 * 新增子节点
 * 新增父节点，等价于新增子节点
 * 不存在新增节点还有子树的这种情况，需要先新增子节点，再移动子树到此节点
 */
@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字段

删除当前节点及其子树：递归pid
只删除某个节点，如果有子树，则要进行子树的升级，依然保持树的层次结构
- 只需要删除该节点的直接儿子节点，不用管孙子节点
- 因为孙子节点本来就是保持层级顺序的

ancestor_path字段

删除当前节点及其子树：WHERE ancestor_path LIKE CONCAT(#{ancestorPath}, '%') OR id = #{id}
只删除某个节点，如果有子树，则要进行子树的升级，依然保持树的层次结构
- ancestor_path= 剔除掉当前ancestor_path中含有当前节点id的内容
- level一定是+1，因为节点自动升级了

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字段：任意节点的移动，依然保持树的层次结构

移动节点，子树也同步跟着移动（自动升降级）
- 条件检查：①不能自己成为自己的子节点；②注意注意回环：不能移动到自己的子节点下
- 更新当前节点的pid。子树的pid不用管，因为子树的pid本来就是保持层级顺序的
移动节点，子树不跟着同步，子树自动升级
- 条件检查：注意不用检查回环，这个需求就是满足降低某个节点的层级的
- 更新当前节点的pid
- 注意需要同步更改原节点的儿子节点的pid，因为儿子节点将会升级；孙子节点不用管

ancestor_path字段：任意节点的移动，依然保持树的层次结构

移动节点，子树也同步跟着移动（自动升降级）
- ancestor_path= 从新父节点的ancestor_path中，剔除掉当前节点的ancestor_path内容
- level = 新父节点的level + 1 - 原节点的level，本质是计算树的高度差
移动节点，子树不跟着同步，子树自动升级
- ancestor_path= 从当前节点的ancestor_path中，剔除掉含有当前节点id的内容
- level一定是+1，因为节点自动升级了

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=目标节点

查子树

查某个节点的所有子节点，并构建为树

实现思路：

先获取该个节点的ancestorPath
在根据ancestorPath左模糊查询：WHERE ancestor_path LIKE CONCAT(#{ancestorPath}, '%')
最后调用上文中构建树的逻辑，但是需要明确pid是几。因为在默认的构建树逻辑中，pid我们写死为0,而我们构建子树，就需要指定顶级节点的id为pid。

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}, '%')

查叶子节点

获取全部叶子节点(层次最低的)

ID不在整个表所有的PID之中的，就是叶子节点
自己LEFT JOIN自己，后者id为NULL的，就是叶子节点
注意错误方案：查出level的值，再根据该个level查库。为什么错？这个只能查深度最深的叶子节点。

获取某个子树的叶子节点：使用递归查询获取某节点的子树节点，于是这个问题回归到上文的“获取全部的叶子节点”。

判定某个节点是否为叶子节点：在获取全部叶子节点的基础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;

查层级节点

查层级节点

获取指定层次的节点
- 如果有level字段，直接按照level查表
- 没有level字段：需要使用递归查询，构建出level，再按照level查询
查询某节点的同级节点：获取该个节点的pid，按pid去查库
查某个子树的第N层
- 注意如果原表如果有level字段，不可用，因为此字段代表的是整个层次表，不是我们要查询的目标子树
- 使用递归查询，构建出子树的level，再按照level查询

完整路径

查根节点到某节点的完整路径，并且按层级路径展示

parentPath = ancestor_path + “/” + id
如果需要展示中文路径：根据parentPath，split出id，再根据IN查库，转换为Map<id, Entity>，遍历parentPath，从map中获取Entity中的name拼接

缓存设计

都有那些数据需要缓存？

首先，一个完整的层级树是必须要缓存的。在获取整体树的场景下，直接从缓存返回，避免查库构建树，直接提升效率。
然后是树节点的详细信息，例如，我想要看某个树节点的详情，虽然根据id查也很快，但是在高并发时，性能可以直接拉满。
其次考虑缓存某节点的儿子节点、子树。

所以，有以下的缓存设计：

查整棵树（组织架构）：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

缓存完整的层级树

情况1：极小体量 + 极低频修改

典型特征：节点总数 < 10000，修改频率按月/年计。
解决方案：把树节点后台组装好，序列化成一个完整的 JSON 树，直接丢进缓存中。
多节点集群之间的L1缓存数据一致性：修改后怎么通知其他节点
Redis Pub/Sub，它是“发后即忘”的，机器一旦 Full GC 停顿就会漏收消息。
对于极度严苛的场景，使用Redis Stream 或 RocketMQ 依靠 ACK 机制保证失效消息的必达。
终极兜底机制：必须设置一个合理的 TTL（比如 1 小时），考虑业务容忍度。

情况2：海量节点 + 高频动态修改

典型特征：节点数达到几十万，随时有人在新增部门、修改层级。
大量高频数据缓存为什么不能用"大JSON"？
整体遍历问题：修改任何一个节点，都要先获取大JSON，修改，再把大JSON写回，非常耗时
并发覆盖问题：两个线程同时修改，导致后修改的覆盖了前面修改的，造成数据丢失。
大Key问题：如果这个JSON有几十MB，在网络传输、反序列化、查找遍历都是非常耗时、耗资源。
解决方案：用 Hash 存节点，用 Set / ZSet 存边（关系）。
每个树节点的信息用Hash存储，谁是谁的子节点用Set/ZSet存储。
存节点，以技术中心为例：Key=prefix:dept，HKey=部门id，KVal={"id":2,"name":"技术中心","manager":"张三","level":2}
存关系，以技术中心的子节点为例：Key=prefix:deptchild:部门id，Val=子部门的id
例如：
- 设置技术中心的子部门：SADD prefix:deptchild:2 4 5
- 查询技术中心都有那些子部门：SMEMBERS prefix:deptchild:2

什么时候用Set？只关注谁是谁的子节点

什么时候用Zset？强调顺序、权重：组织架构顺序、菜单顺序、地区展示顺序

注意事项

保证原子性：新增部门时，HSET 和 SADD 绝不能分开调！必须封装成一段 Lua 脚本丢给 Redis 执行。
热点防击穿：当根部门名字修改时，通过 Canal 监听到变更。此时千万不能发广播让所有机器删除 Caffeine 缓存！正确做法是：广播消息里直接带上最新的部门名称（Push 模式），让所有 JVM 原地覆盖更新本地缓存，彻底阻断打向 Redis 的并发洪峰！

缓存更新策略

新增节点

删除、更新完整树
删除所有缓存的子树，因为完全不知道新增的这个节点是那些的子树
删除新增节点的父节点的所有儿子节点

删除节点

删除、更新完整树
删除所有缓存的子树，因为完全不知道删除的这个节点是那些的子树
删除待删除节点的父节点的所有儿子节点

移动节点

删除、更新完整树
删除所有缓存的子树，因为完全不知道变动的节点是那些的子树
删除原节点的父节点缓存的儿子节点，删除移动到新的父节点的儿子节点

代码实现

/**
 * 缓存场景：
 * 查整棵树（组织架构）：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);
    }
}

本文结束。

————————————————
版权声明：非明确标注皆为原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上本文链接及此声明。
原文链接：https://blog.hackyle.com/article/ifLUQDI9UpTT

层级树的构建与节点增删改全解析：从设计到落地