MySQL/MariaDB邻接列表的深度优先递归查询实现问题

场景与需求 #

• 表结构：comments_table（主键id，外键reply_to_id，字段content）
• 运行环境：MariaDB 10.4.27
• 核心需求：输入根节点ID（如12），按深度优先顺序返回所有子评论，预期结果顺序为13、15、14

示例数据 #

+----+-------------+---------+
| id | reply_to_id | content |
+----+-------------+---------+
| 12 |     NULL    |   text  |
| 13 |      12     |   text  |
| 14 |      12     |   text  |
| 15 |      13     |   text  |
+----+-------------+---------+

现有尝试的问题 #

1. 变量递归查询：顺序不符合要求 #

原查询能返回所有子评论，但无法实现深度优先排序：

select id 
from (
    select * from comments order by id
) comments_sorted, (
    select @pv := '62'
) initialisation 
where find_in_set(replied_to_id, @pv)
and length(@pv := concat(@pv, ',', id));

2. 递归CTE查询：x值未递增 #

尝试用递归CTE时，生成的x值始终为1，无法标记深度优先的遍历顺序：

测试数据

+----+---------------+
| id | replied_to_id |
+----+---------------+
| 81 |          NULL |
| 82 |          NULL |
| 83 |            82 |
| 84 |            83 |
| 85 |            83 |
| 86 |            83 |
| 87 |            84 |
| 88 |            87 |
| 93 |            88 |
+----+---------------+

原查询语句

WITH RECURSIVE cte AS ( 
   SELECT row_number() over (order by id) as x, id, replied_to_id 
   FROM comments 
   WHERE replied_to_id=82 
   UNION ALL 
   SELECT x, comments.id, comments.replied_to_id 
   FROM cte 
   INNER JOIN comments on comments.replied_to_id = cte.id 
) 
SELECT * FROM cte ORDER BY x,id;

返回结果（x值全部为1）

+---+----+---------------+
| x | id | replied_to_id |
+---+----+---------------+
| 1 | 83 |            82 |
| 1 | 84 |            83 |
| 1 | 85 |            83 |
| 1 | 86 |            83 |
| 1 | 87 |            84 |
| 1 | 88 |            87 |
| 1 | 93 |            88 |
+---+----+---------------+

正确的深度优先递归CTE实现 #

通过维护路径字段保证深度优先排序，同时生成递增的x值标记遍历顺序：

实现代码 #

WITH RECURSIVE cte AS (
    -- 锚点查询：获取根节点的直接子评论，初始化路径和顺序值
    SELECT 
        id, 
        reply_to_id,
        -- 拼接路径，用于深度优先排序
        CONCAT('.', id, '.') AS path,
        -- 直接子节点按id排序生成初始顺序值
        ROW_NUMBER() OVER (ORDER BY id) AS x
    FROM comments_table
    WHERE reply_to_id = 12 -- 替换为目标根节点ID
    
    UNION ALL
    
    -- 递归查询：遍历子节点，继承父节点路径并生成递增顺序值
    SELECT 
        c.id, 
        c.reply_to_id,
        CONCAT(cte.path, c.id, '.'),
        -- 基于父节点顺序值，生成全局递增的遍历顺序
        (cte.x * 1000) + ROW_NUMBER() OVER (PARTITION BY cte.id ORDER BY c.id)
    FROM cte
    INNER JOIN comments_table c ON c.reply_to_id = cte.id
)
-- 按路径排序实现深度优先，或直接按x值排序
SELECT id, x
FROM cte
ORDER BY path; -- 也可使用 ORDER BY x

效果说明 #

• 针对第一个示例数据（根节点12），返回顺序为13、15、14，完全符合深度优先要求
• 路径字段path通过拼接ID的方式，确保层级顺序（如.12.13.15.会排在.12.14.之前）
• x值会随遍历顺序递增，解决了原CTE中x值不变化的问题：
  • 直接子节点的x从1开始递增
  • 子节点的子节点x基于父节点x生成，保证全局唯一且按深度优先顺序排列

注意事项 #

• 如果评论ID是大数，可调整(cte.x * 1000)中的乘数（比如改为10000），避免x值溢出
• 若需要自定义子节点的排序规则（如按创建时间而非ID），只需修改ORDER BY中的字段即可

内容的提问来源于stack exchange，提问作者Jacopo V