2

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

我的二叉树示例

在此处输入图像描述

我的表格内容示例

在此处输入图像描述

样本输入和预期输出：

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

输出 - 1, 1.L2, 1.L2.L3,... （仅最左边最外层的孩子）

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

请帮我解决这个问题。

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

4

1 回答 1

5

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

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

根据规范化规则，您应该避免包含可以从其他列派生的数据的列。请注意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<>小提琴。

于 2020-10-25T19:22:30.713 回答