postgresql 在SQL中使用递归CTE遍历前序树

0s0u357o 于 2023-10-18 发布在 PostgreSQL

关注(0)|答案(1)|浏览(127)

我需要遍历一个节点树，以生成一个菜单列表，到目前为止，我已经想出了这个递归CTE：

WITH RECURSIVE nodes AS (
    SELECT '' as spacer,
           1::numeric as level,
           (rank() OVER (PARTITION BY parent_id order by name ASC ))::numeric as node_rank,
           node_tree.*
    FROM node_tree
    where parent_id IS NULL
UNION
    SELECT parent.spacer || '-' as spacer,
           parent.level * 10.0 as level,
           parent.node_rank + (rank()  OVER (PARTITION BY node.parent_id order by node.name ASC )) / (parent.level * 10.0) as node_rank,
           node.*
    FROM node_tree node
             join nodes parent
                  on parent.id = node.parent_id
)
SELECT 
  trim(spacer || ' ' || name) as item_name,
  id,
  parent_id,
  name
FROM nodes
order by node_rank nulls first, name

假设我需要保持表的自引用结构，有没有更好的方法？
这是最小的模式和示例数据：

CREATE TABLE node_tree (
  id uuid primary key,
  parent_id uuid default null,
  name text
  );
  
ALTER TABLE node_tree ADD CONSTRAINT node_parent_check
CHECK (parent_id is NULL OR parent_id <> id);
ALTER TABLE node_tree 
    ADD CONSTRAINT node_parent_fk 
    FOREIGN KEY (parent_id)
    REFERENCES node_tree(id);
    
    
INSERT INTO node_tree (id,parent_id,name) VALUES
('B4352249-3BCC-4110-964B-368AAA2DCE4C', null, 'Node 1'),
('AE3C21B1-9F4E-4C62-A2C7-2C729591CE60', 'B4352249-3BCC-4110-964B-368AAA2DCE4C', 'Node 1.1'),
('CED81F20-6598-42EA-95F8-2D5E8B1FCA73', 'AE3C21B1-9F4E-4C62-A2C7-2C729591CE60', 'Node 1.1.1'),
('9B2BC4D7-D387-4726-A3E2-2466883152CC', 'AE3C21B1-9F4E-4C62-A2C7-2C729591CE60', 'Node 1.1.2'),
('1492A9D9-D24F-47E6-9926-9D198B7F57A0', 'B4352249-3BCC-4110-964B-368AAA2DCE4C', 'Node 1.2'),
('F1B22F5B-34A7-4A92-9792-C2D023147E4D', '1492A9D9-D24F-47E6-9926-9D198B7F57A0', 'Node 1.2.1'),
('5B0AA9B2-1DB8-4DDE-A184-77872F2BC990', '1492A9D9-D24F-47E6-9926-9D198B7F57A0', 'Node 1.2.2'),
('7450E2EC-3E20-45F0-BE59-9F5BEE7D2955', null, 'Node 2'),
('F60B7772-D6E3-42A7-8AAE-D6CB862F4D96', '7450E2EC-3E20-45F0-BE59-9F5BEE7D2955', 'Node 2.1'),
('954C6010-DA37-41B1-8933-93B15552E6CB', 'F60B7772-D6E3-42A7-8AAE-D6CB862F4D96', 'Node 2.1.1'),
('2F3EBEC7-B038-4E7D-B7AF-F22D524B1AF8', '954C6010-DA37-41B1-8933-93B15552E6CB', 'Node 2.1.1.1'),
('4BA13434-2DA5-4913-B9F6-5AFEF4892000', '954C6010-DA37-41B1-8933-93B15552E6CB', 'Node 2.1.1.2'),
('337238CC-FED0-40D2-B54B-603A36C075A0', 'F60B7772-D6E3-42A7-8AAE-D6CB862F4D96', 'Node 2.1.2'),
('F7996999-D024-428A-BF61-78958695DDB3', null, 'Node 3'),
('81BAE0B8-70CF-4152-BCBF-632964E30904', 'F7996999-D024-428A-BF61-78958695DDB3', 'Node 3.1'),
('E88F9BD9-4288-46FC-9972-215623BE3949', '81BAE0B8-70CF-4152-BCBF-632964E30904', 'Node 3.1.1'),
('992AE037-9DAA-49D9-A725-AC1BBCE46037', null, 'Node 4'),
('9CFC7634-E1DA-4AC3-9D9D-4995B28EB148', '992AE037-9DAA-49D9-A725-AC1BBCE46037', 'Node 4.1'),
('E53C022B-1E4E-4D6F-A740-26A23211BF1F', '9CFC7634-E1DA-4AC3-9D9D-4995B28EB148', 'Node 4.1.1');

这是一个DB小提琴：DB Fiddle

postgresql

来源：https://stackoverflow.com/questions/65247873/preorder-tree-traversal-using-recursive-ctes-in-sql

1条答案

按热度按时间

hmtdttj41#

arrays的路径枚举

这将为深度嵌套的树占用大量“不必要”的内存，但这是我能想到的最好的方法，至少在某些用例中应该有效。
表：

psql <<'EOF'
DROP TABLE  IF EXISTS "tmp";
CREATE TABLE "tmp" (
  "id" INTEGER PRIMARY KEY,
  "parentId" INTEGER,
  "childIndex" INTEGER NOT NULL,
  "value" INTEGER NOT NULL,
  "name" TEXT NOT NULL,
  FOREIGN KEY ("parentId") REFERENCES "tmp"("id")
);
EOF

数据类型：

psql <<'EOF'
INSERT INTO "tmp" VALUES
(3, NULL, 0, 1, 'one'  ),
(1, 3,    0, 2, 'two'  ),
(2, 3,    1, 3, 'three'),
(0, 1,    0, 4, 'four' ),
(4, 1,    1, 5, 'five' )
EOF

代表树：

查询方式：

psql <<'EOF'
WITH RECURSIVE "cte" (
  "id",
  "parentId",
  "childIndex",
  "value",
  "name",
  "prefix"
) AS (
  SELECT
    "id",
    "parentId",
    "childIndex",
    "value",
    "name",
    array[0]
  FROM "tmp"
  WHERE "parentId" IS NULL
  UNION ALL
  SELECT
    "child"."id",
    "child"."parentId",
    "child"."childIndex",
    "child"."value",
    "child"."name",
    "parent"."prefix" || "child"."childIndex"
  FROM "tmp" AS "child"
  JOIN "cte" AS "parent"
    ON "child"."parentId" = "parent"."id"
)
SELECT * FROM "cte"
ORDER BY "prefix"
EOF

按所需的前序输出：

id | parentId | childIndex | value | name  | prefix  
----+----------+------------+-------+-------+---------
  3 |          |          0 |     1 | one   | {0}
  1 |        3 |          0 |     2 | two   | {0,0}
  0 |        1 |          0 |     4 | four  | {0,0,0}
  4 |        1 |          1 |     5 | five  | {0,0,1}
  2 |        3 |          1 |     3 | three | {0,1}

SEARCH是一个快捷关键字，它可以产生完全相同的查询，但代码更少：

psql <<'EOF'
WITH RECURSIVE "cte" (
  "id",
  "parentId",
  "childIndex",
  "value",
  "name"
) AS (
  SELECT
    "id",
    "parentId",
    "childIndex",
    "value",
    "name"
  FROM "tmp"
  WHERE "parentId" IS NULL
  UNION ALL
  SELECT
    "child"."id",
    "child"."parentId",
    "child"."childIndex",
    "child"."value",
    "child"."name"
  FROM "tmp" AS "child"
  JOIN "cte" AS "parent"
    ON "child"."parentId" = "parent"."id"
)
SEARCH DEPTH FIRST BY "childIndex" SET "prefix"
SELECT * FROM "cte"
ORDER BY "prefix"
EOF

技巧是创建一个prefix数组列，它注册每个元素的完整路径，然后按字典顺序进行排序。
本手册中还记录了这一点和其他一些相关技术，网址为：https://www.postgresql.org/docs/16/queries-with.html#QUERIES-WITH-RECURSIVE
在Postgresql 15.4，Ubuntu 23.04上测试。
标签：https://dba.stackexchange.com/questions/63153/how-do-i-sort-the-results-of-a-recursive-query-in-an-expanded-tree-like-fashion

展开查看全部

赞(0）回复(0）举报 2023-10-18

我来回答

postgresql 在SQL中使用递归CTE遍历前序树

1条答案

相关问题

热门标签

最新问答