代码之家 › 专栏 › 技术社区 › Marian

SQL中的树深度

query-optimization optimization sql

Marian · 技术社区 · 15 年前

tree_node ,它的主键为 id 并且有一个名为 parent_id

3 回复 | 直到 15 年前

Ants Aasma 15 年前

您将需要递归功能。使用递归查询,这将是:

WITH RECURSIVE node_ancestors(node_id, parent_id) AS (
        SELECT id, id FROM tree_node WHERE id IN (1, 2, 3)
    UNION ALL
        SELECT na.node_id, tree_node.parent_id
            FROM node_ancestors AS na, tree_node
            WHERE tree_node.id = na.parent_id AND tree_node.parent_id IS NOT NULL
)
SELECT node_id, COUNT(parent_id) AS depth FROM node_ancestors GROUP BY node_id;

其他选项包括在存储过程中执行递归、在应用程序中执行递归、限制递归量以及使用大量连接。(最后一个选项对于非平凡深度而言并不真正有效)

Thom Smith 15 年前

如果深度是无限的,那么问题是递归的,没有一个简单有效的解决方案。(可能有简单的xor高效解决方案。)如果您可以控制模式,并且需要定期访问这类数据,那么您可以将表重构为一个嵌套集,每个元素都有左右包含边界。这将允许您使用基本条件计算单个查询中节点的深度,大约:

select count(*) from tree_node
    where left < myLeft
    and right > myRight

Lasse V. Karlsen 15 年前

让我举个例子:

KEY        PARENT         PATH
1          -              *1*
  2        1              *1*2*
  3        1              *1*3*
    4      3              *1*3*4*
  5        1              *1*5*
    6      5              *1*5*6*

这主要用于变化不大的树,如部门层次结构或类似结构。

我知道这样的字符串并不完全遵循规范化理论,因为它似乎会使多个规则(多键、多值字段等)无效,但它在许多场景中都非常有用,包括您要求的场景。

在您的情况下,只需检索相关节点的树值,根据最简单的方法,计算分隔符的数量,或者使用替换函数删除它们,并计算长度差异。

下面是SQL以提供上述节点列表及其深度:

select KEY, PARENT, LEN(PATH)-LEN(REPLACE(PATH, '*', ''))-1 as DEPTH
from NODES

-1

Tal Joffe 5 年前

这不是一个非常聪明的解决方案,但在没有任何附加列和递归功能的情况下可以工作。

可以按如下方式进行左连接:

select  p10.ParentId as parent10_id,
        p9.ParentId as parent9_id,
        p8.ParentId as parent8_id,
        p7.ParentId as parent7_id,
        p6.ParentId as parent6_id,          
        p5.ParentId as parent5_id,
        p4.ParentId as parent4_id,
        p3.ParentId as parent3_id,
        p2.ParentId as parent2_id,
        p1.ParentId as ParentId,
        p1.id as id
from        tree_node p1
left join   tree_node p2 on p2.id = p1.ParentId 
left join   tree_node p3 on p3.id = p2.ParentId 
left join   tree_node p4 on p4.id = p3.ParentId  
left join   tree_node p5 on p5.id = p4.ParentId  
left join   tree_node p6 on p6.id = p5.ParentId
left join   tree_node p7 on p7.id = p6.ParentId
left join   tree_node p8 on p8.id = p7.ParentId
left join   tree_node p9 on p9.id = p8.ParentId
left join   tree_node p10 on p10.id = p9.ParentId
order       by 1, 2, 3, 4, 5, 6, 7, 8, 9, 10;

这绝对不是一个优雅的解决方案,但应该适用于所有数据库。