SQL中的树深度

Question

假设有一个名为tree_node的表，它具有名为id的主键，并且有一个名为parent_id的可为空的列，表中嵌入了树结构（或森林），如何计算一个树的深度在SQL中有效的方式在树/森林节点？

Answer 1

您将需要递归功能。使用递归查询，这将是：

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; 

其他选项都在做递归存储过程，在做应用程序的递归和递归限制的数量和使用大量的联接。 （最后一个选项对于非平凡的深度来说效率并不高）

Answer 2

如果深度是无限的，那么问题是递归的，并且没有真正的简单高效的解决方案。 （可能有简单的XOR高效解决方案。）如果您有模式控制权，并且需要定期访问这类数据，那么您可以将表重构为嵌套集，并为每个元素左右包含边界。这将允许你来计算节点的深度与基本条件，一个单一的查询，约为：

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

Answer 3

一种常见的方法来处理树木，除了KEY和家长的定期专栏，你也有一个PATH类型的列，它包含一个字符串值，包含组成路径的节点的键，从根节点到节点本身，由不允许成为键的一部分的字符分隔本身。

让我给你举个例子：

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* 

这主要与不改变太多，像部门层次结构或类似的树木中。

我知道这样的字符串并不完全遵循规范化理论，因为它似乎使多个规则（多键，多值字段等）无效，但它在许多情况下非常有用，包括你要求的一个。

在你的情况下，你只需要检索有问题的节点的TREE值，根据最简单的方法，或者计算分隔符的数量，或者用替换函数删除它们，然后计算长度。

这里的SQL给你的节点上面的列表，它们的深度：

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

注意，这种方法不需要通过递归SQL数据库引擎的任何特殊语法或支持，使其非常很好地索引。