Postgres：以深度优先方式在递归查询中嵌套记录

Question

我正在开发一个简单的评论系统，用户可以对其他评论进行评论，从而创建一个层次结构。为了以分层顺序获取注释，我在 Postgres 中使用通用表表达式。

以下是使用的字段和查询：

id
user_id
parent_comment_id
message

WITH RECURSIVE CommentCTE AS (
    SELECT id, parent_comment_id, user_id
    FROM comment
    WHERE parent_comment_id is NULL

    UNION ALL

    SELECT child.id, child.parent_comment_id, child.user_id
    FROM comment child
    JOIN CommentCTE
    ON child.parent_comment_id = CommentCTE.id
)
SELECT * FROM CommentCTE

上面的查询以广度优先的方式返回记录：

id       parent_comment_id       user_id
10              null                30
9               null                30
11               9                  30
14              10                  31
15              10                  31
12              11                  30
13              12                  31

但是可以对其进行修改以实现如下所示的功能，即以深度优先的方式一起返回该评论集的记录吗？重点是通过这种方式获取数据，让前端渲染更流畅。

id       parent_comment_id       user_id
9               null                30
11               9                  30
12              11                  30
13              12                  31
10              null                30
14              10                  31
15              10                  31

Answer 1

通常我通过合成一个可以按词法排序的“路径”列来解决这个问题，例如

0001:0003:0006:0009

是

0001:0003:0006

的子级。每个子条目都可以通过将路径元素连接到父条目的路径来创建。您不必将此列返回给客户端，只需使用它进行排序即可。

id       parent_comment_id       user_id     sort_key
9               null                30       0009
11               9                  30       0009:0011
12              11                  30       0009:0011:0012
13              12                  31       0009:0011:0012:0013
10              null                30       0010
14              10                  31       0010:0014
15              10                  31       0010:0015

路径元素不必是任何特殊的东西，只要它按照您希望该级别的子级排序的顺序进行词法排序，并且在该级别是唯一的。基于自动递增 ID 就可以了。

严格来说，使用固定长度的路径元素并不是必需的，但更容易推理。

WITH RECURSIVE CommentCTE AS (
SELECT id, parent_comment_id, user_id, 
    lpad(id::text, 4) sort_key
FROM comment
WHERE parent_comment_id is NULL

UNION ALL

SELECT child.id, child.parent_comment_id, child.user_id, 
    concat(CommentCTE.sort_key, ':', lpad(id::text, 4))
FROM comment child
JOIN CommentCTE
ON child.parent_comment_id = CommentCTE.id
)
SELECT * FROM CommentCTE order by sort_key

Answer 2

使用数组进行路径枚举，用于前序遍历

Ben 提到了字符串连接，但正如他在评论中指出的那样，数组方法更加简洁：，所以我们使用

array[0]

来初始化数组

WITH RECURSIVE CommentCTE AS (
SELECT id, parent_comment_id, user_id, 
    array[0] sort_key
FROM comment
WHERE parent_comment_id is NULL

UNION ALL

SELECT child.id, child.parent_comment_id, child.user_id,
    array_append(CommentCTE.sort_key, id)
FROM comment child
JOIN CommentCTE
ON child.parent_comment_id = CommentCTE.id
)
SELECT * FROM CommentCTE order by sort_key

我在以下位置提供了一个最小的可运行示例：Preorder tree traversal using recursive CTEs in SQL