如何在递归SQL查询中查找子树中的所有节点？

Question

我有一个定义节点之间的父子关系的表：

CREATE TABLE node (       ' pseudo code alert 
    id  INTEGER PRIMARY KEY, 
    parentID INTEGER, ' should be a valid id. 
) 

如果parentID总是指向一个有效现有节点，那么这自然会定义一个树状结构。

如果parentID是NULL那么我们可以假设该节点是根节点。

我怎么会：

1. 找到所有这些都是给定节点的decendents的节点？
2. 查找给定节点下的所有节点到特定深度？

我想做的每个这些作为单个SQL（我期望它必然是递归）或两个相互递归查询。

我在ODBC上下文中这样做，所以我不能依赖任何供应商特定的功能。

编辑

• 没有表写呢，因此增加额外的列/表是完全可以接受的。
• 该树将潜在地更新并添加到相当频繁;辅助数据结构/表格/列将是可能的，尽管需要保持最新。 如果您有任何有关这类查询的魔法书，我想知道。

非常感谢。

Answer 1

This link提供两个邻接表模型（如问题所述），和嵌套集模型的教程。它是作为MySQL文档的一部分编写的。

那篇文章中没有讨论的是这两种方法的插入/取消时间和维护成本。例如：

• 使用嵌套集模型似乎需要一些维护，以保持嵌套动态成长树（例如重新编号所有左，右集数）的邻接表模型
• 移除节点至少需要更新另一行。

Answer 2

一些方法进行了本文前面介绍：

SQL - how to store and navigate hierarchies

Answer 3

如果您有任何魔法书你达到了这种查询的，我想知道。

Celko的树木和层次结构在SQL for Smarties一

Answer 4

将根节点ID中的整个“路径”存储在一个单独的列中，确保在开始和结束时也使用分隔符。例如。假设1是5的父亲，它是17的父亲，并且您的分隔符是破折号，您可以将值-1-5-17-存储在路径列中。

我们找到5所有的孩子，你可以简单地选择记录中，其中路径包括-5-

在两端的隔离是必要的，所以你并不需要担心的ID是在最左边或最当您使用LIKE时，该字段的最右端。

至于你的深度问题，如果你添加一个深度列到表指示当前嵌套深度，这容易为好。您查找起始节点的深度，然后向其中添加x，其中x是要搜索的深度级别数，并且筛选出的记录深度大于此深度。