主页 / dba / 问题 / 289515
Accepted
Jason Dreyzehner
Asked: 2021-04-09 21:10:28 +0800 CST

递归地找到从树中给定父节点下降的所有叶子的路径

  • 772

我正在尝试编写一个查询来识别树结构表中特定父节点的每个最远后代的路径，例如：

    0     1
    |     |
    2     3
    |     |
    4     5
   / \    |
 *6*  8  *7*
      |
     *9*

有很多父母，所有孩子都有一个父母，父母有0-5个孩子（但图表很“长”——大多数父母只有一个孩子）。没有周期。

我正在尝试有效地识别特定节点（而不是任何中间节点）的最远后代的路径。例如在上面：

  • get_leaf_paths(1)将返回 1 行：{1, 3, 5, 7}
  • get_leaf_paths(2)将返回 2 行：{2, 4, 6}和{2, 4, 8, 9}

样品表：

CREATE TABLE graph (
    id bigint PRIMARY KEY,
    parent_id bigint,
    FOREIGN KEY (parent_id) REFERENCES graph(id)
);
INSERT INTO graph (id, parent_id)
    VALUES (0, NULL),
           (1, NULL),
           (2, 0),
           (3, 1),
           (4, 2),
           (5, 3),
           (6, 4),
           (7, 5),
           (8, 4),
           (9, 8);

我希望结果看起来像：

SELECT get_leaf_paths.* FROM get_leaf_paths(0);
path
-----
{0, 2, 4, 6}
{0, 2, 4, 8, 9}
(2 rows)

在我最初尝试使用递归查询的函数时，我很难只选择最远的叶子，特别是因为某些分支比其他分支短（例如6，9以上分支处于不同的深度）。路径可能很深（数千或数百万个元素），所以我还想避免为每个中间节点生成路径的过多内存使用。

任何想法将不胜感激。谢谢！

postgresql recursive

1 个回答

  1. Best Answer
    WITH RECURSIVE
cte AS ( SELECT id, 
                parent_id, 
                id::TEXT path,
                NOT EXISTS ( SELECT NULL
                             FROM graph gr
                             WHERE graph.id = gr.parent_id ) is_leaf
                FROM graph 
                WHERE id = 2 /* initital node id */
         UNION ALL
         SELECT graph.id, 
                graph.parent_id, 
                cte.path || ',' || graph.id,
                NOT EXISTS ( SELECT NULL
                             FROM graph gr
                             WHERE graph.id = gr.parent_id ) 
         FROM cte JOIN graph ON cte.id = graph.parent_id)
SELECT path 
FROM cte
WHERE is_leaf

    https://dbfiddle.uk/?rdbms=postgres_12&fiddle=2e40ff454f302033bf5e8cba8b0b0d85

    也可以应用多个初始节点（WHERE id IN (0, 1)）。

    • 1

相关问题