sql - PostgreSQL ltree - 如何从使用 ltree 构造的二叉树中获取最左/最右路径和子级？

Question

我正在使用 PostgreSQL 和 ltree 构建大量二叉树数据。对于特定逻辑，我必须获取给定节点的最左/最右路径。

我的二叉树示例

我的表格内容示例

示例输入和预期输出:

输入 - 节点 1，最左边的子节点

输出 - 1, 1.L2, 1.L2.L3,...(仅最左边的子节点)

我想在 postgresql、ltree 查询中得到这个结果。

请帮我解决这个问题。

任何更好的 postgre 表设计也可以建议，但必须在处理大量数据时获得良好的性能。

Answer 1

SQL 中树的传统实现是 node_id -parent_id 模型，这意味着在查询中使用递归(例如参见 Recursive CTE concatenate fields with parents from arbitrary point )。 Ltree 扩展是此方法的替代方法，它允许您在许多情况下避免递归查询。您似乎试图在您的方法中混合使用这两种方法。如果你想使用ltree，你基本上只需要一列来存储整个树结构:

create table my_table(
    id int primary key,
    tree ltree,
    person_id int);

根据normalization rules ，您应该避免包含可从其他列派生的数据的列。请注意，parent、level 和 side 列是多余的，因为 tree 已包含以下信息:

select 
    tree, 
    nlevel(tree) as level, 
    subpath(tree, 0, -1) as parent,
    substring(subpath(tree, -1, 1)::text from '[R|L]') as side
from my_table
    
    tree    | level | parent  | side
------------+-------+---------+------
 1          |     1 |         |
 1.L2       |     2 | 1       | L
 1.R2       |     2 | 1       | R
 1.L2.L3    |     3 | 1.L2    | L
 1.L2.R3    |     3 | 1.L2    | R
 1.L2.L3.L4 |     4 | 1.L2.L3 | L
 1.L2.R3.R4 |     4 | 1.L2.R3 | R
 1.L2.R3.L4 |     4 | 1.L2.R3 | L
(8 rows)

回到你的主要问题，正式的解决方案可能会使用递归:

with recursive recursive_tree as (
    select *
    from my_table
    where tree = '1'
union all
    select t.*
    from my_table t
    join recursive_tree r 
        on subpath(t.tree, 0, -1) = r.tree
        and left(subpath(t.tree, -1, 1)::text, 1) = 'L'
    )
select *
from recursive_tree

但您也可以以智能方式将 ltree 值解释为文本，从而实现更简单、更快的查询:

select *
from my_table
where subpath(tree, 0, 1) = '1'
and tree::text not like '%R%'

 id |    tree    | person_id
----+------------+-----------
  1 | 1          |         1
  2 | 1.L2       |         2
  4 | 1.L2.L3    |         4
  6 | 1.L2.L3.L4 |         6
(4 rows)

Db<>fiddle.