第3章 角色树的数据结构实现：邻接表、嵌套集、闭包表、物化路径对比及核心CRUD

3.1 角色树的存储需求

角色树（Role Tree）是RBAC中权限继承与角色层次的核心表达。对角色树的存储需支持：

• 查询父/子/祖先/后代 —— 权限判定与角色聚合
• 插入/删除节点 —— 组织架构变动
• 移动子树 —— 角色重组
• 快速遍历整棵树 —— 角色树菜单渲染

四种主流数据结构各有优劣，本章从原理、CRUD代码、调试、性能优化逐项剖析。

3.2 四种数据结构原理对比

3.3 邻接表（Adjacency List）

原理：每个节点记录 parent_id，根节点 parent_id IS NULL。查询子树需递归CTE（MySQL 8.0+ / PostgreSQL / SQL Server）。

CREATE TABLE role_adj (
    id       INT PRIMARY KEY,
    name     VARCHAR(64),
    parent_id INT,
    FOREIGN KEY (parent_id) REFERENCES role_adj(id)
);

-- 插入根节点
INSERT INTO role_adj (id, name, parent_id) VALUES (1, 'CEO', NULL);

-- 插入子节点
INSERT INTO role_adj (id, name, parent_id) VALUES (2, 'CTO', 1);

-- 查询子树（含自身）
WITH RECURSIVE cte AS (
    SELECT id, name, parent_id, 1 AS level
    FROM role_adj WHERE id = 1
    UNION ALL
    SELECT r.id, r.name, r.parent_id, c.level+1
    FROM role_adj r JOIN cte c ON r.parent_id = c.id
)
SELECT * FROM cte;

-- 移动节点：只需更新 parent_id
UPDATE role_adj SET parent_id = 3 WHERE id = 4;

调试与常见错误

致命错误：递归CTE写法错误导致死循环（如 ON r.id = c.parent_id）；循环引用（节点A父为B，B父为A）无约束检测。

优化：在 parent_id 上建索引，深度递归时考虑设置 cte_max_recursion_depth。

3.4 嵌套集（Nested Sets）

原理：每个节点分配 lft（左值）和 rgt（右值），满足：若A是B的祖先，则 A.lft < B.lft < B.rgt < A.rgt。查询子树只需范围过滤，无需递归。

CREATE TABLE role_nested (
    id   INT PRIMARY KEY,
    name VARCHAR(64),
    lft  INT NOT NULL,
    rgt  INT NOT NULL
);
-- 初始化根节点（lft=1, rgt=2）
INSERT INTO role_nested (id, name, lft, rgt) VALUES (1, 'CEO', 1, 2);

-- 插入子节点（以插入到id=1下为例：需腾出区间）
-- 实际应用中应使用存储过程重新编号，此处略。

-- 查询id=1的所有后代
SELECT * FROM role_nested
WHERE lft >= 1 AND rgt <= 2
ORDER BY lft;

调试与常见错误

错误：插入时未正确更新所有受影响节点的lft/rgt，导致区间重叠或丢失；数据间隙过大。建议使用 Gap 策略（非连续整数）减少更新范围，或结合物化路径做双校验。

3.5 闭包表（Closure Table）

原理：用一张路径表 role_path 存储所有祖先-后代关系，ancestor 和 descendant 均为角色ID。查询子树时只需JOIN路径表。

CREATE TABLE role_node (
    id   INT PRIMARY KEY,
    name VARCHAR(64)
);
CREATE TABLE role_path (
    ancestor   INT NOT NULL,
    descendant INT NOT NULL,
    depth      INT NOT NULL,   -- 深度差（0表示自身）
    PRIMARY KEY (ancestor, descendant),
    FOREIGN KEY (ancestor)   REFERENCES role_node(id),
    FOREIGN KEY (descendant) REFERENCES role_node(id)
);

-- 插入根节点
INSERT INTO role_node (id, name) VALUES (1, 'CEO');
INSERT INTO role_path (ancestor, descendant, depth) VALUES (1, 1, 0);

-- 插入子节点（id=2，父id=1）
INSERT INTO role_node (id, name) VALUES (2, 'CTO');
INSERT INTO role_path (ancestor, descendant, depth)
SELECT ancestor, 2, depth+1 FROM role_path WHERE descendant = 1
UNION ALL SELECT 2, 2, 0;   -- 自身路径

-- 查询id=1的所有后代
SELECT rn.* FROM role_node rn
JOIN role_path rp ON rn.id = rp.descendant
WHERE rp.ancestor = 1;

性能与优化

优点：子树/祖先查询极快，支持任意深度；缺点：路径表数据量 = O(n²) 最坏（每个节点到所有祖先都存一次），插入/移动需批量写大量行。

调优：在 role_path(ancestor, descendant) 上建立索引；使用批量INSERT；对 depth 列建索引加速层级过滤。

3.6 物化路径（Materialized Path）

原理：每个节点存储从根到自身的路径字符串，如 "1/4/5"。查询子树：WHERE path LIKE '1/4/%'。

CREATE TABLE role_mpath (
    id   INT PRIMARY KEY,
    name VARCHAR(64),
    path VARCHAR(255) NOT NULL UNIQUE
);

-- 插入根
INSERT INTO role_mpath (id, name, path) VALUES (1, 'CEO', '1/');

-- 插入子节点（父path='1/'）
INSERT INTO role_mpath (id, name, path) VALUES (2, 'CTO', '1/2/');

-- 查询id=1的所有后代
SELECT * FROM role_mpath WHERE path LIKE '1/%';

-- 移动节点（将id=2及其子树移到id=3下）
-- 需更新所有子节点的path：REPLACE or UPDATE SET path = CONCAT('3/', SUBSTRING(path, LENGTH('1/')+1))
UPDATE role_mpath SET path = CONCAT('3/', SUBSTRING(path, LENGTH('1/')+1))
WHERE path LIKE '1/2/%';

调试与常见错误

错误：路径分隔符设计不当造成模糊匹配歧义（如用“.”导致ID为1与10冲突）；路径过长导致VARCHAR溢出；移动节点时子节点路径更新遗漏。建议使用斜杠加填充ID（如 001/002/），并借助触发器自动维护。

3.7 角色树数据结构对比SVG

3.8 选择建议与稳定性优化

3.9 综合调试与部署提醒

• 测试数据量：每种模型至少压测1000节点、深度10级的树，观察插入/移动延迟。
• 数据库版本：使用MySQL 8.0+或PostgreSQL 12+以支持递归CTE；闭包表在MySQL中注意行长度限制（65535字节）。
• 事务与锁：嵌套集和物化路径在移动子树时需加表锁或使用SELECT ... FOR UPDATE，防止并发破坏一致性。
• 常见错误：
• 邻接表递归忘记终止条件 → 死循环 → 设置cte_max_recursion_depth。
• 嵌套集插入时未刷新所有右值 → 结构损坏 → 用存储过程封装并做原子检查。
• 闭包表路径冗余 → 使用ON DUPLICATE KEY或唯一约束避免重复。
• 物化路径使用LIKE '%/x/'（前导%） → 索引失效 → 重构为前缀匹配。

-- 物化路径批量移动示例（PostgreSQL）
UPDATE role_mpath
SET path = regexp_replace(path, '^1/2/', '3/')
WHERE path LIKE '1/2/%';