递归 CTE 遍历树结构

2 min高级2026/9/12

递归 CTE 遍历树形与图结构：组织架构层级查询、评论回复树构建、路径枚举与环检测。

1. 递归 CTE 基础

1.1 递归 CTE 语法结构

递归 CTE（Common Table Expression）由锚点成员和递归成员通过 UNION ALL 连接：

WITH RECURSIVE cte_name AS (
    -- 锚点查询：非递归的初始行集
    SELECT ...
    FROM ...
    WHERE ...

    UNION ALL

    -- 递归查询：引用 cte_name 自身
    SELECT ...
    FROM cte_name
    JOIN ... ON ...
    WHERE ...
)
SELECT * FROM cte_name;

执行流程：

1. 执行锚点查询，得到初始结果集 R0
2. 用 R0 作为输入执行递归查询，得到 R1
3. 用 R1 作为输入执行递归查询，得到 R2
4. 重复直到递归查询返回空集
5. 最终结果 = R0 ∪ R1 ∪ R2 ∪ ...

1.2 递归深度限制

-- MySQL：默认限制 1000 层，超深会报错 3636，可放宽
SET SESSION cte_max_recursion_depth = 10000;

-- PostgreSQL：没有专门的递归深度参数（受内存与 max_stack_depth 约束）
-- 深度防护要靠查询自身携带的 level/depth 列：
WITH RECURSIVE t AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1 FROM t WHERE n < 100   -- 在递归成员里显式设上限
)
SELECT * FROM t;

另外，把递归成员的 UNION ALL 换成 UNION（去重）可以让重复行不再增长，对有环数据也是一种天然的止涨手段。

2. 组织架构层级查询

2.1 自引用表设计

CREATE TABLE employees (
    emp_id      INT PRIMARY KEY,
    emp_name    VARCHAR(50),
    manager_id  INT,           -- 上级经理ID，顶级为 NULL
    dept_name   VARCHAR(50),
    FOREIGN KEY (manager_id) REFERENCES employees(emp_id)
);

-- 示例数据
INSERT INTO employees VALUES
(1, 'CEO', NULL, 'Executive'),
(2, 'CTO', 1, 'Technology'),
(3, 'CFO', 1, 'Finance'),
(4, 'VP Eng', 2, 'Technology'),
(5, 'VP Finance', 3, 'Finance'),
(6, 'Dev Lead', 4, 'Technology'),
(7, 'Dev Senior', 6, 'Technology');

2.2 自顶向下遍历：查询某人的所有下属

WITH RECURSIVE subordinates AS (
    -- 锚点：从指定员工开始
    SELECT emp_id, emp_name, manager_id, 0 AS level, CAST(emp_name AS CHAR(500)) AS path
    FROM employees
    WHERE emp_id = 1  -- 从 CEO 开始

    UNION ALL

    -- 递归：查找下一级下属
    SELECT
        e.emp_id,
        e.emp_name,
        e.manager_id,
        s.level + 1,
        CONCAT(s.path, ' → ', e.emp_name)
    FROM employees e
    INNER JOIN subordinates s ON e.manager_id = s.emp_id
)
SELECT emp_id, emp_name, level, path
FROM subordinates
ORDER BY level, emp_id;

输出：

emp_id | emp_name   | level | path
-------|------------|-------|---------------------------
1      | CEO        | 0     | CEO
2      | CTO        | 1     | CEO → CTO
3      | CFO        | 1     | CEO → CFO
4      | VP Eng     | 2     | CEO → CTO → VP Eng
5      | VP Finance | 2     | CEO → CFO → VP Finance
6      | Dev Lead   | 3     | CEO → CTO → VP Eng → Dev Lead
7      | Dev Senior | 4     | CEO → CTO → VP Eng → Dev Lead → Dev Senior

2.3 自底向上遍历：查询某人的所有上级

WITH RECURSIVE managers AS (
    -- 锚点：从指定员工开始
    SELECT emp_id, emp_name, manager_id, 0 AS level
    FROM employees
    WHERE emp_id = 7  -- 从 Dev Senior 开始

    UNION ALL

    -- 递归：向上查找经理
    SELECT
        e.emp_id,
        e.emp_name,
        e.manager_id,
        m.level + 1
    FROM employees e
    INNER JOIN managers m ON e.emp_id = m.manager_id
)
SELECT emp_id, emp_name, level
FROM managers
ORDER BY level DESC;

2.4 计算每人的下属人数

WITH RECURSIVE sub_tree AS (
    SELECT emp_id, emp_name, manager_id
    FROM employees
    WHERE manager_id IS NULL  -- 顶级

    UNION ALL

    SELECT e.emp_id, e.emp_name, e.manager_id
    FROM employees e
    INNER JOIN sub_tree s ON e.manager_id = s.emp_id
)
SELECT
    s.emp_id,
    s.emp_name,
    COUNT(child.emp_id) AS direct_reports,
    (SELECT COUNT(*) FROM sub_tree st WHERE st.manager_id = s.emp_id) AS total_reports
FROM sub_tree s
LEFT JOIN employees child ON child.manager_id = s.emp_id
GROUP BY s.emp_id, s.emp_name;

3. 评论回复树

3.1 邻接表模型

CREATE TABLE comments (
    comment_id  INT PRIMARY KEY AUTO_INCREMENT,
    post_id     INT NOT NULL,
    parent_id   INT,           -- 父评论ID，顶级评论为 NULL
    user_id     INT NOT NULL,
    content     TEXT,
    created_at  TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    FOREIGN KEY (parent_id) REFERENCES comments(comment_id)
);

3.2 构建评论树

WITH RECURSIVE comment_tree AS (
    -- 锚点：顶级评论
    SELECT
        comment_id,
        post_id,
        parent_id,
        user_id,
        content,
        created_at,
        0 AS depth,
        CAST(comment_id AS CHAR(1000)) AS path,
        CAST(LPAD(comment_id, 10, '0') AS CHAR(1000)) AS sort_path
    FROM comments
    WHERE post_id = 42 AND parent_id IS NULL

    UNION ALL

    -- 递归：子评论
    SELECT
        c.comment_id,
        c.post_id,
        c.parent_id,
        c.user_id,
        c.content,
        c.created_at,
        ct.depth + 1,
        CONCAT(ct.path, '.', c.comment_id),
        CONCAT(ct.sort_path, '.', LPAD(c.comment_id, 10, '0'))
    FROM comments c
    INNER JOIN comment_tree ct ON c.parent_id = ct.comment_id
)
SELECT
    comment_id,
    parent_id,
    content,
    depth,
    -- 缩进展示：PostgreSQL 用 || 拼接；MySQL 请改写为 CONCAT(REPEAT('  ', depth), content)
    REPEAT('  ', depth) || content AS indented_content,
    path
FROM comment_tree
ORDER BY sort_path;

3.3 限制递归深度

-- 只获取2级评论（顶级 + 1层回复）
WITH RECURSIVE comment_tree AS (
    SELECT comment_id, parent_id, content, 0 AS depth
    FROM comments WHERE post_id = 42 AND parent_id IS NULL

    UNION ALL

    SELECT c.comment_id, c.parent_id, c.content, ct.depth + 1
    FROM comments c
    INNER JOIN comment_tree ct ON c.parent_id = ct.comment_id
    WHERE ct.depth < 1  -- 限制深度
)
SELECT * FROM comment_tree;

4. 环检测与防护

4.1 检测循环引用

WITH RECURSIVE org_path AS (
    SELECT
        emp_id,
        emp_name,
        manager_id,
        CAST(emp_id AS CHAR(1000)) AS visited_path,
        0 AS depth
    FROM employees
    WHERE emp_id = 1

    UNION ALL

    SELECT
        e.emp_id,
        e.emp_name,
        e.manager_id,
        CONCAT(o.visited_path, ',', e.emp_id),
        o.depth + 1
    FROM employees e
    INNER JOIN org_path o ON e.manager_id = o.emp_id
    -- 环检测：确保当前节点不在已访问路径中
    WHERE FIND_IN_SET(e.emp_id, o.visited_path) = 0
      AND o.depth < 20  -- 安全深度限制
)
SELECT * FROM org_path;

4.2 PostgreSQL 数组环检测

WITH RECURSIVE org_path AS (
    SELECT
        emp_id,
        emp_name,
        manager_id,
        ARRAY[emp_id] AS visited,
        0 AS depth
    FROM employees
    WHERE emp_id = 1

    UNION ALL

    SELECT
        e.emp_id,
        e.emp_name,
        e.manager_id,
        o.visited || e.emp_id,
        o.depth + 1
    FROM employees e
    INNER JOIN org_path o ON e.manager_id = o.emp_id
    WHERE e.emp_id <> ALL(o.visited)  -- 数组包含检测
      AND o.depth < 20
)
SELECT * FROM org_path;

5. 递归 CTE 与其他树模型对比

5.1 四种树存储模型

模型	查询子树	插入	移动节点	空间
邻接表（Adjacency List）	递归 CTE	O(1)	O(1)	优
路径枚举（Path Enumeration）	LIKE	O(1)	O(n)	中
嵌套集（Nested Set）	BETWEEN	O(n)	O(n)	优
闭包表（Closure Table）	JOIN	O(depth)	O(n)	差

5.2 闭包表 + 递归 CTE

-- 闭包表：存储所有祖先-后代关系
CREATE TABLE tree_closure (
    ancestor_id   INT NOT NULL,
    descendant_id INT NOT NULL,
    depth         INT NOT NULL,
    PRIMARY KEY (ancestor_id, descendant_id),
    FOREIGN KEY (ancestor_id) REFERENCES employees(emp_id),
    FOREIGN KEY (descendant_id) REFERENCES employees(emp_id)
);

-- 查询子树：无需递归
SELECT e.*
FROM tree_closure tc
JOIN employees e ON e.emp_id = tc.descendant_id
WHERE tc.ancestor_id = 1;

-- 查询深度
SELECT depth FROM tree_closure
WHERE ancestor_id = 1 AND descendant_id = 7;
-- 结果: 4

5.3 递归 CTE 实现图遍历

-- 有向图最短路径
CREATE TABLE edges (
    from_node VARCHAR(10),
    to_node   VARCHAR(10),
    weight    INT
);

WITH RECURSIVE paths AS (
    SELECT
        from_node,
        to_node,
        weight,
        CAST(from_node || '→' || to_node AS VARCHAR(500)) AS path,
        weight AS total_weight
    FROM edges
    WHERE from_node = 'A'

    UNION ALL

    SELECT
        p.from_node,
        e.to_node,
        e.weight,
        p.path || '→' || e.to_node,
        p.total_weight + e.weight
    FROM paths p
    JOIN edges e ON p.to_node = e.from_node
    WHERE p.path NOT LIKE '%' || e.to_node || '%'  -- 避免环
)
SELECT path, total_weight
FROM paths
WHERE to_node = 'G'
ORDER BY total_weight
LIMIT 1;  -- 最短路径

6. 小结

初学者要点：递归 CTE = 锚点（起点行集）+ UNION ALL + 引用自身的递归成员；记住执行模型是”逐层迭代直到空集”，每层都能携带 level、path 等派生列。
自顶向下查子孙、自底向上查祖先，只是把递归成员的连接方向反过来；评论树用 LPAD 编码的 sort_path 排序即可得到”深度优先”的展示顺序。
进阶注意：MySQL 有 cte_max_recursion_depth（默认 1000）兜底，PostgreSQL 只能靠查询自带的 level 上限或 UNION 去重止涨；图数据必须显式做环检测（路径数组/ FIND_IN_SET）；单表深层级、写多读多的场景先评估闭包表等物化方案，递归 CTE 是灵活的默认解，不总是最快的解。

递归 CTE 遍历树结构

1. 递归 CTE 基础#

1.1 递归 CTE 语法结构#

1.2 递归深度限制#

2. 组织架构层级查询#

2.1 自引用表设计#

2.2 自顶向下遍历：查询某人的所有下属#

2.3 自底向上遍历：查询某人的所有上级#

2.4 计算每人的下属人数#

3. 评论回复树#

3.1 邻接表模型#

3.2 构建评论树#

3.3 限制递归深度#

4. 环检测与防护#

4.1 检测循环引用#

4.2 PostgreSQL 数组环检测#

5. 递归 CTE 与其他树模型对比#

5.1 四种树存储模型#

5.2 闭包表 + 递归 CTE#

5.3 递归 CTE 实现图遍历#

6. 小结#