在 SQL 中使用递归 CTE 进行预序树遍历

Question

我需要按顺序遍历节点树以生成菜单列表，到目前为止我已经想出了这个递归 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 Fiddle

Answer 1

使用数组

进行路径枚举

对于深度嵌套的树来说，这会占用大量“不必要的”内存，但这是我能想到的最好的方法，至少应该在某些用例中起作用。

表：

CREATE TABLE "ParentIndexTree" (
  "id" INTEGER PRIMARY KEY,
  "parentId" INTEGER,
  "childIndex" INTEGER NOT NULL,
  "value" INTEGER NOT NULL,
  "name" TEXT NOT NULL,
  FOREIGN KEY ("parentId") REFERENCES "ParentIndexTree"(id)
)
CREATE INDEX "valueIndex" ON "ParentIndexTree" (value)

数据：

INSERT INTO "ParentIndexTree" 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' )
`)

代表树：

     1
    / \
   2   3
  / \
 4   5

查询：

WITH RECURSIVE "TreeSearch" (
  "id",
  "parentId",
  "childIndex",
  "value",
  "name",
  "prefix"
) AS (
  SELECT
    "id",
    "parentId",
    "childIndex",
    "value",
    "name",
    array[0]
  FROM "ParentIndexTree"
  WHERE "parentId" IS NULL

  UNION ALL

  SELECT
    "child"."id",
    "child"."parentId",
    "child"."childIndex",
    "child"."value",
    "child"."name",
    array_append("parent"."prefix", "child"."childIndex")
  FROM "ParentIndexTree" AS "child"
  JOIN "TreeSearch" AS "parent"
    ON "child"."parentId" = "parent"."id"
)
SELECT * FROM "TreeSearch"
ORDER BY "prefix"

按所需预序输出：

 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}

在 Postgresql 15.4、Ubuntu 23.04 上测试。