5

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

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

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

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

我将如何：

  1. 查找作为给定节点的后代的所有节点？
  2. 查找给定节点下的所有节点到特定深度？

我想将这些中的每一个都作为一个 SQL（我希望它一定是递归的）或两个相互递归的查询来完成。

我在 ODBC 上下文中执行此操作，因此我不能依赖任何供应商特定的功能。

编辑

  • 还没有写表，所以添加额外的列/表是完全可以接受的。
  • 树可能会经常更新和添加；辅助数据结构/表/列是可能的，但需要保持最新。如果您有任何魔法书籍可以进行此类查询，我想知道。

非常感谢。

4

3 回答 3

4

此链接提供有关邻接列表模型（如问题中所述）和嵌套集模型的教程。它是作为 MySQL 文档的一部分编写的。

那篇文章中没有讨论的是插入/删除时间，以及这两种方法的维护成本。例如：

  • 使用嵌套集模型的动态生长树似乎需要一些维护来维护嵌套（例如重新编号所有左右集编号）
  • 删除邻接表模型中的节点需要至少更新另一行。
于 2009-01-19T12:38:34.970 回答
2

如果您有任何魔法书籍可以进行此类查询，我想知道。

Celko在 SQL 中的树和层次结构

于 2009-01-19T00:31:33.067 回答
1

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

现在要查找 5 的所有孩子，您只需选择路径包含 -5- 的记录

末尾的分隔符是必需的，因此当您使用 LIKE 时，您无需担心位于字段最左端或最右端的 ID。

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

于 2009-01-19T13:19:33.593 回答