课程 6.5: 递归 CTE 用于层次数据

递归 CTE 是 SQL 中最强大的功能之一，使您能够处理层次和树状结构的数据。在本课中，我们将探讨如何使用递归公共表表达式查询具有父子关系的数据，例如组织结构图、类别树和物料清单。

什么是递归 CTE？

递归 CTE 是一个引用自身的公共表表达式，允许您遍历层次数据结构。与普通 CTE 一次执行不同，递归 CTE 会迭代执行，直到满足终止条件。

递归 CTE 的常见用例：

组织层级：员工-经理关系
类别树：具有子类别的产品类别
物料清单 (BOM)：部件和子部件关系
文件系统结构：文件夹和子文件夹
社交网络：朋友的朋友关系
地理层级：国家 > 州 > 城市关系

递归 CTE 语法

递归 CTE 的一般语法是：

WITH RECURSIVE cte_name AS (
    -- 锚定成员（基本情况）
    SELECT ...
    FROM table
    WHERE condition
    
    UNION ALL
    
    -- 递归成员（递归情况）
    SELECT ...
    FROM table
    JOIN cte_name ON condition
)
SELECT * FROM cte_name;

组件：

WITH RECURSIVE：引入递归 CTE 的关键字
锚定成员：返回起始行的初始查询（基本情况）
UNION ALL：组合锚定和递归成员
递归成员：引用 CTE 本身的查询
终止：当递归成员返回零行时，递归停止

递归 CTE 的工作原理

执行过程：

执行锚定成员：获取初始行集
执行递归成员：使用步骤 1 的结果
重复步骤 2：使用上一次迭代的结果
继续直到：递归成员返回零行
返回所有结果：所有迭代的组合结果

基本示例：数字序列

让我们从一个简单的示例开始，生成一个数字序列：

WITH RECURSIVE number_sequence AS (
    -- 锚定成员：从 1 开始
    SELECT 1 AS n
    
    UNION ALL
    
    -- 递归成员：在前一个值上加 1
    SELECT n + 1
    FROM number_sequence
    WHERE n < 10
)
SELECT n
FROM number_sequence;

结果：

工作原理：

锚定：返回 1
迭代 1：1 + 1 = 2
迭代 2：2 + 1 = 3
... 继续直到 n < 10 为假
最终迭代：返回 10，但 10 < 10 为假，因此递归停止

员工层级示例

让我们创建一个表示组织结构的表：

-- 示例员工表
CREATE TABLE employee (
    employee_id INT PRIMARY KEY,
    employee_name VARCHAR(100),
    manager_id INT,
    title VARCHAR(100)
);

-- 示例数据
INSERT INTO employee VALUES
    (1, 'Alice Johnson', NULL, 'CEO'),
    (2, 'Bob Smith', 1, 'VP of Engineering'),
    (3, 'Carol White', 1, 'VP of Sales'),
    (4, 'David Brown', 2, 'Engineering Manager'),
    (5, 'Eve Davis', 2, 'Engineering Manager'),
    (6, 'Frank Miller', 3, 'Sales Manager'),
    (7, 'Grace Wilson', 4, 'Senior Developer'),
    (8, 'Henry Moore', 4, 'Developer'),
    (9, 'Ivy Taylor', 5, 'Developer'),
    (10, 'Jack Anderson', 6, 'Sales Representative');

查找所有下属

要查找所有向特定经理汇报的员工（直接或间接）：

WITH RECURSIVE subordinates AS (
    -- 锚定：从经理开始
    SELECT
        employee_id,
        employee_name,
        manager_id,
        title,
        0 AS level
    FROM
        employee
    WHERE
        employee_name = 'Bob Smith'
    
    UNION ALL
    
    -- 递归：查找直接下属
    SELECT
        e.employee_id,
        e.employee_name,
        e.manager_id,
        e.title,
        s.level + 1
    FROM
        employee e
    INNER JOIN
        subordinates s ON e.manager_id = s.employee_id
)
SELECT
    employee_id,
    employee_name,
    title,
    level
FROM
    subordinates
ORDER BY
    level, employee_name;

结果：

employee_id | employee_name   | title                | level
------------|-----------------|----------------------|------
2           | Bob Smith       | VP of Engineering    | 0
4           | David Brown     | Engineering Manager  | 1
5           | Eve Davis       | Engineering Manager  | 1
7           | Grace Wilson    | Senior Developer     | 2
8           | Henry Moore     | Developer            | 2
9           | Ivy Taylor      | Developer            | 2

构建完整的组织结构图

要显示从 CEO 到下属的完整层级：

WITH RECURSIVE org_chart AS (
    -- 锚定：从 CEO 开始（没有经理）
    SELECT
        employee_id,
        employee_name,
        manager_id,
        title,
        0 AS level,
        CAST(employee_name AS VARCHAR(1000)) AS path
    FROM
        employee
    WHERE
        manager_id IS NULL
    
    UNION ALL
    
    -- 递归：添加每一层
    SELECT
        e.employee_id,
        e.employee_name,
        e.manager_id,
        e.title,
        oc.level + 1,
        CONCAT(oc.path, ' > ', e.employee_name)
    FROM
        employee e
    INNER JOIN
        org_chart oc ON e.manager_id = oc.employee_id
)
SELECT
    REPEAT('  ', level) || employee_name AS hierarchy,
    title,
    level,
    path
FROM
    org_chart
ORDER BY
    path;

结果：

hierarchy                      | title                | level | path
-------------------------------|----------------------|-------|---------------------------
Alice Johnson                  | CEO                  | 0     | Alice Johnson
  Bob Smith                    | VP of Engineering    | 1     | Alice Johnson > Bob Smith
    David Brown                | Engineering Manager  | 2     | Alice Johnson > Bob Smith > David Brown
      Grace Wilson             | Senior Developer     | 3     | Alice Johnson > Bob Smith > David Brown > Grace Wilson
      Henry Moore              | Developer            | 3     | Alice Johnson > Bob Smith > David Brown > Henry Moore
    Eve Davis                  | Engineering Manager  | 2     | Alice Johnson > Bob Smith > Eve Davis
      Ivy Taylor               | Developer            | 3     | Alice Johnson > Bob Smith > Eve Davis > Ivy Taylor
  Carol White                  | VP of Sales          | 1     | Alice Johnson > Carol White
    Frank Miller               | Sales Manager        | 2     | Alice Johnson > Carol White > Frank Miller
      Jack Anderson            | Sales Representative | 3     | Alice Johnson > Carol White > Frank Miller > Jack Anderson

类别树示例

让我们处理一个产品类别层级：

-- 示例类别表
CREATE TABLE category (
    category_id INT PRIMARY KEY,
    category_name VARCHAR(100),
    parent_category_id INT
);

-- 示例数据
INSERT INTO category VALUES
    (1, 'Electronics', NULL),
    (2, 'Computers', 1),
    (3, 'Phones', 1),
    (4, 'Laptops', 2),
    (5, 'Desktops', 2),
    (6, 'Gaming Laptops', 4),
    (7, 'Business Laptops', 4),
    (8, 'Smartphones', 3),
    (9, 'Feature Phones', 3);

查找所有子类别

要查找“Computers”下的所有子类别：

WITH RECURSIVE category_tree AS (
    -- 锚定：从 Computers 开始
    SELECT
        category_id,
        category_name,
        parent_category_id,
        0 AS depth,
        CAST(category_name AS VARCHAR(1000)) AS path
    FROM
        category
    WHERE
        category_name = 'Computers'
    
    UNION ALL
    
    -- 递归：获取所有子类别
    SELECT
        c.category_id,
        c.category_name,
        c.parent_category_id,
        ct.depth + 1,
        CONCAT(ct.path, ' > ', c.category_name)
    FROM
        category c
    INNER JOIN
        category_tree ct ON c.parent_category_id = ct.category_id
)
SELECT
    category_id,
    REPEAT('  ', depth) || category_name AS category_hierarchy,
    depth,
    path
FROM
    category_tree
ORDER BY
    path;

结果：

category_id | category_hierarchy    | depth | path
------------|----------------------|-------|--------------------------------
2           | Computers            | 0     | Computers
4           |   Laptops            | 1     | Computers > Laptops
6           |     Gaming Laptops   | 2     | Computers > Laptops > Gaming Laptops
7           |     Business Laptops | 2     | Computers > Laptops > Business Laptops
5           |   Desktops           | 1     | Computers > Desktops

查找祖先

要查找特定类别的所有父类别：

WITH RECURSIVE category_ancestors AS (
    -- 锚定：从 Gaming Laptops 开始
    SELECT
        category_id,
        category_name,
        parent_category_id,
        0 AS level_up
    FROM
        category
    WHERE
        category_name = 'Gaming Laptops'
    
    UNION ALL
    
    -- 递归：获取父类别
    SELECT
        c.category_id,
        c.category_name,
        c.parent_category_id,
        ca.level_up + 1
    FROM
        category c
    INNER JOIN
        category_ancestors ca ON c.category_id = ca.parent_category_id
)
SELECT
    category_id,
    category_name,
    level_up
FROM
    category_ancestors
ORDER BY
    level_up;

结果：

category_id | category_name   | level_up
------------|-----------------|----------
6           | Gaming Laptops  | 0
4           | Laptops         | 1
2           | Computers       | 2
1           | Electronics     | 3

物料清单示例

递归 CTE 的经典用例是探索物料清单（部件和子部件）：

-- 示例部件表
CREATE TABLE parts (
    part_id INT PRIMARY KEY,
    part_name VARCHAR(100),
    quantity INT
);

-- 示例物料清单表
CREATE TABLE bom (
    parent_part_id INT,
    child_part_id INT,
    quantity_needed INT,
    PRIMARY KEY (parent_part_id, child_part_id)
);

-- 示例数据
INSERT INTO parts VALUES
    (1, 'Bicycle', 1),
    (2, 'Frame', 1),
    (3, 'Wheel', 2),
    (4, 'Tire', 1),
    (5, 'Rim', 1),
    (6, 'Spoke', 36);

INSERT INTO bom VALUES
    (1, 2, 1),  -- 自行车需要 1 个框架
    (1, 3, 2),  -- 自行车需要 2 个轮子
    (3, 4, 1),  -- 轮子需要 1 个轮胎
    (3, 5, 1),  -- 轮子需要 1 个轮圈
    (5, 6, 36); -- 轮圈需要 36 根辐条

计算所需的总部件

要查找构建自行车所需的所有部件：

WITH RECURSIVE parts_explosion AS (
    -- 锚定：从顶级产品开始
    SELECT
        p.part_id,
        p.part_name,
        1 AS quantity,
        0 AS level,
        CAST(p.part_name AS VARCHAR(1000)) AS path
    FROM
        parts p
    WHERE
        p.part_name = 'Bicycle'
    
    UNION ALL
    
    -- 递归：展开 BOM
    SELECT
        p.part_id,
        p.part_name,
        pe.quantity * b.quantity_needed,
        pe.level + 1,
        CONCAT(pe.path, ' > ', p.part_name)
    FROM
        parts_explosion pe
    INNER JOIN
        bom b ON pe.part_id = b.parent_part_id
    INNER JOIN
        parts p ON b.child_part_id = p.part_id
)
SELECT
    part_id,
    REPEAT('  ', level) || part_name AS part_hierarchy,
    quantity,
    level,
    path
FROM
    parts_explosion
ORDER BY
    path;

结果：

part_id | part_hierarchy | quantity | level | path
--------|----------------|----------|-------|--------------------------------
1       | Bicycle        | 1        | 0     | Bicycle
2       |   Frame        | 1        | 1     | Bicycle > Frame
3       |   Wheel        | 2        | 1     | Bicycle > Wheel
4       |     Tire       | 2        | 2     | Bicycle > Wheel > Tire
5       |     Rim        | 2        | 2     | Bicycle > Wheel > Rim
6       |       Spoke    | 72       | 3     | Bicycle > Wheel > Rim > Spoke

请注意，我们总共需要 72 根辐条：2 个轮子 × 每个轮子 1 个轮圈 × 每个轮圈 36 根辐条 = 72 根辐条。

防止无限循环

如果数据中存在循环引用，递归 CTE 可能会创建无限循环。以下是防止这种情况的策略：

1. 限制最大深度

WITH RECURSIVE limited_recursion AS (
    SELECT
        category_id,
        category_name,
        parent_category_id,
        0 AS depth
    FROM
        category
    WHERE
        parent_category_id IS NULL
    
    UNION ALL
    
    SELECT
        c.category_id,
        c.category_name,
        c.parent_category_id,
        lr.depth + 1
    FROM
        category c
    INNER JOIN
        limited_recursion lr ON c.parent_category_id = lr.category_id
    WHERE
        lr.depth < 10  -- 最大深度限制
)
SELECT * FROM limited_recursion;

2. 跟踪已访问节点

WITH RECURSIVE safe_traversal AS (
    SELECT
        category_id,
        category_name,
        parent_category_id,
        ARRAY[category_id] AS visited_ids
    FROM
        category
    WHERE
        parent_category_id IS NULL
    
    UNION ALL
    
    SELECT
        c.category_id,
        c.category_name,
        c.parent_category_id,
        st.visited_ids || c.category_id
    FROM
        category c
    INNER JOIN
        safe_traversal st ON c.parent_category_id = st.category_id
    WHERE
        NOT (c.category_id = ANY(st.visited_ids))  -- 防止循环
)
SELECT * FROM safe_traversal;

性能考虑

1. 为父子列建立索引

始终为递归连接中使用的列建立索引：

CREATE INDEX idx_employee_manager ON employee(manager_id);
CREATE INDEX idx_category_parent ON category(parent_category_id);

2. 限制结果集

使用 WHERE 子句限制递归的范围：

WITH RECURSIVE subordinates AS (
    SELECT employee_id, employee_name, manager_id, 0 AS level
    FROM employee
    WHERE employee_name = 'Bob Smith'
    
    UNION ALL
    
    SELECT e.employee_id, e.employee_name, e.manager_id, s.level + 1
    FROM employee e
    INNER JOIN subordinates s ON e.manager_id = s.employee_id
    WHERE s.level < 3  -- 仅深入 3 层
)
SELECT * FROM subordinates;

3. 使用适当的连接类型

当您只想要匹配的行时，使用 INNER JOIN
当您想要包含没有子节点的叶节点时，使用 LEFT JOIN

实际用例：线程/评论系统

一个常见的 Web 应用程序模式是嵌套评论或论坛线程：

CREATE TABLE comments (
    comment_id INT PRIMARY KEY,
    parent_comment_id INT,
    user_name VARCHAR(100),
    comment_text TEXT,
    created_at TIMESTAMP
);

WITH RECURSIVE comment_thread AS (
    -- 锚定：顶级评论
    SELECT
        comment_id,
        parent_comment_id,
        user_name,
        comment_text,
        0 AS depth,
        CAST(comment_id AS VARCHAR(1000)) AS sort_path
    FROM
        comments
    WHERE
        parent_comment_id IS NULL
    
    UNION ALL
    
    -- 递归：嵌套回复
    SELECT
        c.comment_id,
        c.parent_comment_id,
        c.user_name,
        c.comment_text,
        ct.depth + 1,
        CONCAT(ct.sort_path, '-', LPAD(c.comment_id::TEXT, 10, '0'))
    FROM
        comments c
    INNER JOIN
        comment_thread ct ON c.parent_comment_id = ct.comment_id
)
SELECT
    REPEAT('  ', depth) || user_name AS indented_user,
    comment_text,
    depth
FROM
    comment_thread
ORDER BY
    sort_path;

关键要点

递归 CTE 使得遍历具有父子关系的层次数据成为可能
WITH RECURSIVE 语法包括一个锚定成员和一个递归成员
锚定成员 定义起点（基本情况）
递归成员 引用 CTE 本身并处理每次迭代
终止发生在递归成员返回零行时
常见用例：组织图、类别树、物料清单、文件系统
层级跟踪：包含深度/层级列以了解层次位置
路径构建：连接路径以显示完整的血统
防止无限循环：使用深度限制或跟踪已访问节点
性能：为父列建立索引，并在可能的情况下限制递归深度
多功能：适用于任何自引用的表结构

递归 CTE 是处理 SQL 中树状和层次数据的重要工具。它们将复杂的多查询操作转变为优雅的单查询解决方案。

在下一个模块中，我们将探讨窗口函数以进行高级数据分析。

练习

课程

练习场

测试

课程 6.5: 递归 CTE 用于层次数据

什么是递归 CTE？

递归 CTE 语法

递归 CTE 的工作原理

基本示例：数字序列

员工层级示例

查找所有下属

构建完整的组织结构图

类别树示例

查找所有子类别

查找祖先

物料清单示例

计算所需的总部件

防止无限循环

1. 限制最大深度

2. 跟踪已访问节点

性能考虑

1. 为父子列建立索引

2. 限制结果集

3. 使用适当的连接类型

实际用例：线程/评论系统

关键要点

尝试解决以下任务，以巩固您在本课中学到的内容。

登录

注册

课程 6.5: 递归 CTE 用于层次数据

什么是递归 CTE？

递归 CTE 语法

递归 CTE 的工作原理

基本示例：数字序列

员工层级示例

查找所有下属

构建完整的组织结构图

类别树示例

查找所有子类别

查找祖先

物料清单示例

计算所需的总部件

防止无限循环

1. 限制最大深度

2. 跟踪已访问节点

性能考虑

1. 为父子列建立索引

2. 限制结果集

3. 使用适当的连接类型

实际用例：线程/评论系统

关键要点

尝试解决以下任务，以巩固您在本课中学到的内容。