如何在postgresql中进行嵌套排序

Question

我有列

id

（字符串）、

parentId

（字符串或空）和

order

（数字）。它是类似树的结构，其中具有相同

parentId

的行是同一节点的子节点。

order

用于对每个父母的孩子进行排序（因此对于不同父母的孩子来说，它们可能是相同的）。

对于给定的

id

，我想提取其上一行和下一行。我需要以某种方式首先通过

parentId

查看其

order

来对数据进行排序，然后将其放在其子项的表中间，再次按

order

排序并再次（递归）。这是运行查询后我的数据的样子：

SELECT "content"."id", "content"."parentId", "content"."order" FROM "course_content_entity" "content" WHERE ( "content"."deletedAt" IS NULL ) AND ("content"."courseId" = '05dd28d5-a244-4ca1-b7fb-fc3bc7b2e422') order by "content"."parentId", "content"."order" 

这当然是我现在想要的。有什么想法如何做到这一点吗？

Answer 1

要获取按树的 DFS 顺序排序的行，您可以尝试以下查询：

WITH RECURSIVE node(id, parent_id, position, position_array) AS (
    SELECT
        root.id,
        root.parent_id,
        root.position,
        ARRAY[ROW_NUMBER() OVER (ORDER BY root.position, root.id)] AS position_array
    FROM forest_node root
    WHERE root.parent_id IS NULL
UNION ALL
    SELECT
        child.id,
        child.parent_id,
        child.position,
        parent.position_array || ROW_NUMBER() OVER (PARTITION BY child.parent_id ORDER BY child.position) AS position_array
    FROM forest_node child
    INNER JOIN node parent ON parent.id = child.parent_id
)
SELECT
    n.id,
    n.parent_id,
    n.position,
    n.position_array,
    ROW_NUMBER() OVER (ORDER BY n.position_array) AS dfs_position
FROM node n
ORDER BY dfs_position;

此查询从根 (

parent_id IS NULL

) 开始，并递归地 (

WITH RECURSIVE

) 添加其子项，通过

position_array

窗口函数构建

ROW_NUMBER() OVER ()

（窗口函数教程、窗口函数列表） ）。最终排序是通过

position_array

排序完成的，依赖于数组比较（数组函数和运算符）。

将

forest_node

重命名为

"course_content_entity"

以及

id

、

parent_id

和

position

到

"id"

、

"parentId"

和

"order"

应使其适用于您的情况。我出于多种原因选择了不同的名称，包括更好的通用示例以及避免使用带引号的标识符的冲动。

假设：

• 根节点可能有也可能没有

  position

  集。非根节点始终具有位置集。
• 表中可能有多个根节点（这就是为什么我使用

  forest_node

  而不是

  tree_node

  作为表名）。我们按

  position

  对它们进行排序，并按

  id

  打破平局。同一棵树的所有节点在最终列表中彼此相邻。

注意：如果表中存在某个循环，则查询将忽略该循环的所有条目，因为没有以根节点结尾的路径。

最后一句话：如果您正在处理一个大表，那么编写一个仅逐个节点遍历树以查找“DFS 邻居”的函数可能会更有效。提供的查询将始终适用于表中可能成为瓶颈的所有行。

用于测试目的：

CREATE TABLE forest_node (
    id text NOT NULL,
    parent_id text,
    position integer CHECK(position IS NOT NULL OR parent_id IS NULL),
    PRIMARY KEY(id),
    UNIQUE(parent_id, position)
);

INSERT INTO forest_node (id, parent_id, position)
VALUES
    ('root1', NULL, NULL),
    ('root2', NULL, NULL),
    ('root3', NULL, NULL),
    ('root1.1', 'root1', 1),
    ('root1.2', 'root1', 2),
    ('root3.2', 'root3', 2),
    ('root3.1', 'root3', 1),
    ('root2.1', 'root2', 1),
    ('root2.2', 'root2', 2),
    ('root2.1.1', 'root2.1', 1),
    ('root2.1.2', 'root2.1', 2),
    ('root2.4', 'root2', 4),
    ('root2.3', 'root2', 3);