PostgreSQL - 检索树中给定子节点的所有 ID

Question

我有一个客户的非二叉树，我需要为给定节点获取树中的所有 ID。

该表非常简单，只是一个带有父ID和子ID的连接表。这是我存储在数据库中的树的表示。

在这个例子中，如果我搜索节点 17，我需要返回 14-17。如果我搜索 11，我需要返回 1-6-5-4-8-11-12-7-2-10-3。

顺序并不重要。在将子节点添加到节点时，我只需要 ID 以避免循环。

我创建了这个查询。祖先部分工作正常，我检索了所有父节点，但对于后代我有一些麻烦。我只能检索树的某些部分。例如，对于节点 11，我检索 4-10-6-11-7-8，因此树的所有正确部分都丢失了。

WITH RECURSIVE
-- starting node(s)
starting (parent, child) AS
(
  SELECT t.parent, t.child
  FROM public.customerincustomer AS t
  WHERE t.child = :node or t.parent = :node
)
,
ancestors (parent, child) AS
(
  SELECT t.parent, t.child
  FROM public.customerincustomer AS t
  WHERE t.parent IN (SELECT parent FROM starting)
  UNION ALL
  SELECT t.parent, t.child
  FROM public.customerincustomer AS t JOIN ancestors AS a ON t.child = a.parent
),
descendants (parent, child) AS
(
  SELECT t.parent, t.child
  FROM public.customerincustomer AS t
  WHERE t.parent IN (SELECT parent FROM starting) or t.child in (select child from starting)
  UNION ALL
  SELECT t.parent, t.child
  FROM public.customerincustomer AS t JOIN ancestors AS a ON t.parent = a.child
)

table ancestors
union all
table descendants

更新

我看到树表中包含的许多示例也是表单中的根 (root_id, null)。

就我而言，我没有这个记录。

例如，取最小的树 14->17，在我的表中我只有一个记录 parent、child

14 17

Answer 1

一个非常原始的实现：

它基本上将问题分为两个子问题：

• 首先找到有问题的节点的所有祖先（包括节点本身）。如果节点没有父节点，那么这就是它自己。
• 然后找到所有这些祖先的后代（包括他们自己）。我们可能在ancestors结果集中有多个节点，我们可能会在这里得到重复项，因此我们使用UNION（而不是UNION ALL）来删除它们。
• 请注意，即使输入节点是没有子节点的根，该查询也将起作用。
• 如果数据集不是树木森林而是任意有向图（其中节点可以有多个父节点），它也将起作用。

查询：

WITH RECURSIVE 
ancestors (parent) AS
(
  SELECT :node                      -- start with the given node
  UNION ALL
  SELECT t.parent                   -- and find all its ancestors
  FROM public.customerincustomer AS t JOIN ancestors AS a ON t.child = a.parent
),
descendants (customer) AS
(
  SELECT parent AS customer       -- now start with all the ancestors
  FROM ancestors
  UNION 
  SELECT t.child                  -- and find all their descendants
  FROM public.customerincustomer AS t JOIN descendants AS d ON t.parent = d.customer
)
SELECT customer
FROM descendants ;

Answer 2

此函数返回 的父级node_id：

_{由于父行没有行（id，null），因此存在“级别”行。}

CREATE FUNCTION get_parent(node_id int)
RETURNS integer AS
$$
  WITH RECURSIVE get_parent AS
  (
      SELECT 
          t1.id, 
          t1.parent_id, 
          t1.name, 
          0 AS level
      FROM 
          tree t1
      WHERE 
          t1.id = node_id
      UNION ALL
      SELECT 
          t2.id, 
          t2.parent_id, 
          t2.name,
          level+1
      FROM 
          tree t2 
      INNER JOIN 
          get_parent ON get_parent.parent_id = t2.id
  )
  SELECT
      id
  FROM
      get_parent
  ORDER BY
      level DESC
  LIMIT 1 ;
$$
LANGUAGE SQL;

选择 get_parent(7);

| 获取父级 |
| ---------: |
| 6 |

现在，下一个查询返回基于父节点的整个树结构。

WITH RECURSIVE childs AS
(
    SELECT 
        t1.id, 
        t1.parent_id, 
        t1.name
    FROM 
        tree t1
    WHERE 
        t1.id = get_parent(7)
    UNION ALL
    SELECT 
        t2.id, 
        t2.parent_id, 
        t2.name
    FROM 
        tree t2 
    INNER JOIN 
        childs ON childs.id = t2.parent_id
)
SELECT
    id,
    parent_id,
    name
 FROM
    childs;

编号 | 父 ID | 姓名   
-: | --------： | :------
 6 | 1 | 节点6
 4 | 6 | 节点4
 8 | 6 | 节点8
11 | 11 6 | 节点11
 7 | 11 | 11 节点7
10 | 10 7 | 节点10

db<>在这里摆弄