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

Question

我有一张表格，它定义了节点之间的父子关系：

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

如果parentID始终指向有效的现有节点，则自然会定义树形结构。

如果parentID为NULL，则可以假定该节点是根节点。

如何做到以下两点：

1.查找给定节点的所有后代节点？

2.查找给定节点下特定深度的所有节点？

我希望每个查询都能用单个SQL完成（我认为这必须是递归的），或者使用两个相互递归的查询。

我在ODBC环境中进行此操作，因此无法依赖于任何特定于供应商的功能。

编辑：

1.尚未编写任何表格，因此可以接受添加额外的列/表格。

2.树可能经常更新和添加；辅助数据结构/表/列是可能的，但需要保持最新状态。

如果你有任何魔法书籍可以解决这种查询问题，我想知道。

非常感谢。

- jamesh

---

本文先前已经涵盖了一些方法：SQL - 如何存储和导航层次结构。 - Turnkey

Answer 1

此链接提供了关于邻接表模型（如问题所述）和嵌套集模型的教程。它是MySQL文档的一部分。

该文章未讨论两种方法的插入/删除时间和维护成本。例如：

• 使用嵌套集模型动态增长的树似乎需要一些维护来维护嵌套（例如重新编号所有左右设置数字）
• 在邻接表模型中删除节点将需要更新至少另一行。

- jamesh

---

Oracle似乎对MySQL的网站链接进行了不当处理，现在还有可能找到教程吗？ - martinthenext

Answer 2

如果你有任何可以用于这种查询的魔法书，我想知道。

Celko的SQL智者之树与层次结构

- ChrisW

Answer 3

将从根节点的ID到整个“路径”存储在单独的列中，确保在开头和结尾使用分隔符。例如，假设1是5的父级，5是17的父级，并且您的分隔符字符为破折号，则会将值-1-5-17-存储在路径列中。

现在要查找所有5的子项，只需选择路径包括-5-的记录即可。

末尾的分隔符是必要的，这样您就不必担心在使用LIKE时位于字段最左侧或最右侧的ID。

至于深度问题，如果您向表中添加一个深度列来指示当前嵌套深度，这也变得很容易。您查找起始节点的深度，然后将x添加到其中，其中x是您想要搜索的层数，过滤掉深度大于该深度的记录。

- Bork Blatt

---

这个应该如何更新？例如，如果您用50替换5，那么您需要为5的每个子代更改路径字符串。我理解的对吗？ - jamesh

是的，但由于您可以轻松找到5的所有依赖项，并且可以使用简单的字符串替换将-5-替换为-50-，因此仍然有效。这似乎不太“整洁”，但大多数优化都是如此。 - Bork Blatt