PostgreSQL ltree - 如何从用 ltree 构建的二叉树中获取 left/right 大多数路径和 children？

Question

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

我的二叉树示例

我的 table 内容示例

示例输入和预期输出：

输入 - 节点 1，最左边 children

输出 - 1, 1.L2, 1.L2.L3,...（只有最左边的 children）

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

请帮我解决这个问题。

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

Answer 1

SQL 中树的传统实现是 node_id - parent_id 模型，这意味着在查询中使用递归（参见示例）。 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.

PostgreSQL ltree - 如何从用 ltree 构建的二叉树中获取 left/right 大多数路径和 children？

PostgreSQL ltree - How to get left/right most path and children from a Binary tree constructed with ltree?

sql

postgresql

hierarchical-data

ltree