从邻接树中获取所有子节点的列表

库片段

从邻接树中获取所有子节点的列表

适用于 PostgreSQL

任何版本

编写语言

Pl/pgSQL

依赖项

无

描述

假设您有一个基于邻接列表的树，例如一个结构类似于此的表

                           Table "public.test"
  Column   |  Type   |                     Modifiers
-----------+---------+---------------------------------------------------
 id        | integer | not null default nextval('test_id_seq'::regclass)
 parent_id | integer |
 x         | text    |
Indexes:
    "test_pkey" PRIMARY KEY, btree (id)
Foreign-key constraints:
    "test_parent_id_fkey" FOREIGN KEY (parent_id) REFERENCES test(id)

您可能想获取给定元素的所有子节点。

要做到这一点，您可以使用以下函数

CREATE OR REPLACE FUNCTION get_all_children_array(use_parent INT4) RETURNS INT4[] as $$
DECLARE
    process_parents INT4[] := ARRAY[ use_parent ];
    children INT4[] := '{}';
    new_children INT4[];
BEGIN
    WHILE ( array_upper( process_parents, 1 ) IS NOT NULL ) LOOP
        new_children := ARRAY( SELECT id FROM test WHERE parent_id = ANY( process_parents ) AND id <> ALL( children ) );
        children := children || new_children;
        process_parents := new_children;
    END LOOP;
    RETURN children;
END;
$$ LANGUAGE plpgsql;

使用方法

# select get_all_children_array(3);
 get_all_children_array
------------------------
 {5,6,9}
(1 row)


# select * from test where id = any( get_all_children_array(3) );
 id | parent_id | x
----+-----------+---
  5 |         3 | e
  6 |         3 | f
  9 |         5 | i
(3 rows)

PostgreSQL 8.4+

公用表表达式 (CTE) 使得将此写为查询而不是过程变得容易得多

首先，我们编写 CTE 来返回项目的祖先

WITH RECURSIVE tree AS (
  SELECT id, ARRAY[]::integer[] AS ancestors
  FROM test WHERE parent_id IS NULL

  UNION ALL

  SELECT test.id, tree.ancestors || test.parent_id
  FROM test, tree
  WHERE test.parent_id = tree.id
) SELECT * FROM tree WHERE 0 = ANY(tree.ancestors);

此查询可能会返回类似以下内容

 id | ancestors
------------------------
  3 | {}
  5 | {3}
  6 | {3}
  9 | {3,5}
(4 rows)

现在我们有了每个项目的祖先数组，检索后代就变得很简单了WHERE子句

WITH RECURSIVE tree AS (
  SELECT id, ARRAY[]::integer[] AS ancestors
  FROM test WHERE parent_id IS NULL

  UNION ALL

  SELECT test.id, tree.ancestors || test.parent_id
  FROM test, tree
  WHERE test.parent_id = tree.id
) SELECT * FROM tree WHERE 3 = ANY(tree.ancestors);

鉴于以上结果，此查询将返回以下内容

 id | ancestors
------------------------
  5 | {3}
  6 | {3}
  9 | {3,5}
(3 rows)