针对树形结构优化的 SQL

Question

如何以最佳性能从数据库获取树形结构数据？例如，假设您在数据库中有一个文件夹层次结构。其中文件夹-数据库行具有 ID、Name 和 ParentID 列。

您会使用特殊算法一次性获取所有数据，最小化数据库调用的数量并在代码中处理吗？

还是会多次调用数据库并直接从数据库中完成结构？

也许基于 x 个数据库行、层次深度或其他因素，不同的答案。

编辑：我使用 Microsoft SQL Server，但其他角度的答案也很有趣。

- Seb Nilsson

---

你使用的是哪种关系型数据库管理系统？SQL Server？MySQL？Oracle？ - kͩeͣmͮpͥ ͩ

Answer 1

这取决于您将如何访问该树。

一个聪明的技巧是给每个节点分配一个字符串ID，其中父项的ID是子项的可预测子字符串。例如，父项可以是“01”，而子项可以是“0100”、“0101”、“0102”等。这样，您就可以使用以下方式一次从数据库中选择整个子树：

SELECT * FROM treedata WHERE id LIKE '0101%';

由于标准是初始子字符串，对ID列建立索引可以加速查询。

- Ned Batchelder

---

你只需要确保每个级别的数字数量（在这种情况下为2）* 级别数被允许在该CHAR列中。这施加了一些人为的（但可管理的）限制。 - S.Lott

@Ned Batchelder，我会尝试这种方法来构建我的表格结构。但是移动子树到另一个位置不是很困难吗？如果在层次结构中间插入新节点会怎么样？我需要保留parentId列吗？还是只需要id就足够处理结构了？谢谢。 - Ismail Yavuz

Answer 2

在所有将树形结构存储于关系型数据库中的方法中，最常见的是相邻列表(adjacency lists)和嵌套集合(nested sets). 嵌套集合优化了读取操作，能够在一次查询中检索整个树形结构；而相邻列表则优化了写入操作，可通过简单查询添加新节点。

对于相邻列表，每个节点都有一个指向其父节点或子节点(也可以使用其他链接)的列。通过这些信息，可以基于父子关系建立层次结构。不幸的是，除非限制树状结构的深度，否则无法在一次查询中检索整个结构，读取速度通常比更新慢。

而对于嵌套集合模型，情况正好相反。读取快而简单，但更新变得复杂，因为必须维护编号系统。嵌套集合模型通过使用基于先序遍历的编号系统对所有节点进行枚举，从而编码了父子关系和排序顺序。

我曾经使用过嵌套集合模型，并且尽管为了优化大型层次结构的读取而使得其较为复杂，但这确实是值得的。一旦你做了几个练习来绘制树并编号节点，你就能掌握它了。

我在这篇文章中开始研究这种方法: Managing Hierarchical Data in MySQL.

- Bernard Igiri

---

那篇文章很不错。是个好的补充！ - Quibblesome

Answer 3

在我所工作的产品中，我们在SQL Server中存储了一些树形结构，并使用上述技术将节点的层次结构存储在记录中。即：

tblTreeNode
TreeID = 1
TreeNodeID = 100
ParentTreeNodeID = 99
Hierarchy = ".33.59.99.100."
[...] (actual data payload for node)

当然，维护层次结构是棘手的，需要使用触发器。但是，在插入/删除/移动时生成它从不是递归的，因为父节点或子节点的层次结构包含了您所需的所有信息。

您可以这样获取节点的所有后代：

SELECT * FROM tblNode WHERE Hierarchy LIKE '%.100.%'

这是插入触发器的代码：

--Setup the top level if there is any
UPDATE T 
SET T.TreeNodeHierarchy = '.' + CONVERT(nvarchar(10), T.TreeNodeID) + '.'
FROM tblTreeNode AS T
    INNER JOIN inserted i ON T.TreeNodeID = i.TreeNodeID
WHERE (i.ParentTreeNodeID IS NULL) AND (i.TreeNodeHierarchy IS NULL)

WHILE EXISTS (SELECT * FROM tblTreeNode WHERE TreeNodeHierarchy IS NULL)
    BEGIN
        --Update those items that we have enough information to update - parent has text in Hierarchy
        UPDATE CHILD 
        SET CHILD.TreeNodeHierarchy = PARENT.TreeNodeHierarchy + CONVERT(nvarchar(10),CHILD.TreeNodeID) + '.'
        FROM tblTreeNode AS CHILD 
            INNER JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID
        WHERE (CHILD.TreeNodeHierarchy IS NULL) AND (PARENT.TreeNodeHierarchy IS NOT NULL)
    END

这里是更新触发器：

--Only want to do something if Parent IDs were changed
IF UPDATE(ParentTreeNodeID)
    BEGIN
        --Update the changed items to reflect their new parents
        UPDATE CHILD
        SET CHILD.TreeNodeHierarchy = CASE WHEN PARENT.TreeNodeID IS NULL THEN '.' + CONVERT(nvarchar,CHILD.TreeNodeID) + '.' ELSE PARENT.TreeNodeHierarchy + CONVERT(nvarchar, CHILD.TreeNodeID) + '.' END
        FROM tblTreeNode AS CHILD 
            INNER JOIN inserted AS I ON CHILD.TreeNodeID = I.TreeNodeID
            LEFT JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID

        --Now update any sub items of the changed rows if any exist
        IF EXISTS (
                SELECT * 
                FROM tblTreeNode 
                    INNER JOIN deleted ON tblTreeNode.ParentTreeNodeID = deleted.TreeNodeID
            )
            UPDATE CHILD 
            SET CHILD.TreeNodeHierarchy = NEWPARENT.TreeNodeHierarchy + RIGHT(CHILD.TreeNodeHierarchy, LEN(CHILD.TreeNodeHierarchy) - LEN(OLDPARENT.TreeNodeHierarchy))
            FROM tblTreeNode AS CHILD 
                INNER JOIN deleted AS OLDPARENT ON CHILD.TreeNodeHierarchy LIKE (OLDPARENT.TreeNodeHierarchy + '%')
                INNER JOIN tblTreeNode AS NEWPARENT ON OLDPARENT.TreeNodeID = NEWPARENT.TreeNodeID

    END

再加上一个位，一个检查约束来防止树节点中的循环引用：

ALTER TABLE [dbo].[tblTreeNode]  WITH NOCHECK ADD  CONSTRAINT [CK_tblTreeNode_TreeNodeHierarchy] CHECK  
((charindex(('.' + convert(nvarchar(10),[TreeNodeID]) + '.'),[TreeNodeHierarchy],(charindex(('.' + convert(nvarchar(10),[TreeNodeID]) + '.'),[TreeNodeHierarchy]) + 1)) = 0))

我建议您使用触发器来防止每棵树有超过一个根节点（null parent），以及使相关节点不属于不同的TreeIDs（但这些问题比上面那些问题要简单一些）。希望这个建议对您有所帮助！请注意，您需要针对您特定的情况检查此解决方案是否能够正常运作。

- James Orr

Answer 4

Celko在2000年写了这篇文章： http://www.dbmsmag.com/9603d06.html http://www.intelligententerprise.com/001020/celko1_1.jhtml;jsessionid=3DFR02341QLDEQSNDLRSKHSCJUNN2JVN?_requestid=32818

---

其他人提出了以下问题： 如何在Oracle树查询中连接其他表？ 如何使用SQL计算树中值的总和？ 如何在数据库中存储目录/层次结构/树形结构？ MYSQL中递归存储过程获取分层数据的性能如何？ 将平面表解析为树的最有效/优雅的方法是什么？

---

最后，您可以查看rails的“acts_as_tree”（读取密集型）和“acts_as_nested_set”（写入密集型）插件。我没有一个好的链接来比较它们。

- Gene T

Answer 5

有几种常见的针对层次结构的查询。其他大多数类型的查询都是这些查询的变体。

1. 从父节点查找所有子节点。 a. 到特定深度。例如，给定我的直接父节点，深度为1的所有子节点将是我的兄弟姐妹。 b. 到树的底部。

2. 从子节点查找所有父节点。 a. 到特定深度。例如，我的直接父节点是到深度为1的父节点。 b. 到无限深度。

(a) 情况（特定深度）在 SQL 中更容易处理。特殊情况（深度=1）在 SQL 中很简单。非零深度更难。有限但非零深度可以通过有限数量的连接完成。 (b) 情况，即深度不确定（到顶部，到底部），非常困难。

如果您的树很大（数百万个节点），则无论您尝试什么，都会遇到问题。

如果您的树小于一百万个节点，请将其全部加载到内存中并在其中进行操作。在面向对象的世界中，生活会更加简单。只需获取行并在返回行时构建树即可。

如果您有一个巨大的树，则有两个选择。

1. 递归游标用于处理无限获取。这意味着结构的维护是O(1)——只需更新一些节点即可完成。但是，获取是O(n*log(n))，因为您必须为每个具有子节点的节点打开一个游标。

2. 聪明的“堆编号”算法可以编码每个节点的父级关系。一旦每个节点正确编号，就可以使用简单的 SQL SELECT 处理所有四种类型的查询。但是，对树结构的更改需要重新编号节点，使更改的成本相对于检索的成本相当高。

- S.Lott

---

SQL CTE消除了递归游标的需要，并且对于连接折叠具有一定的优化 - 但仍然是一个昂贵的调用来枚举大型层次结构。 - stephbu

如果您有数百万个节点，可以创建树形结构。每棵树都作为BLOB存储在数据库中。您读取顶部树（具有数百万个叶子），其中每个叶子都有指向其子树的ID，该子树也有数百万个叶子。这样，您将拥有数十亿个叶子，并且如果查询的局部性不超过几个子树，则可以快速读取。 - The_Ghost

Answer 6

如果您的数据库中有许多树，并且您只会获取整个树，则应为数据库中的每个节点存储一个树ID（或根节点ID）和父节点ID，获取特定树ID的所有节点，并在内存中处理。

但是，如果您将获取子树，则只能获取特定父节点ID的子树，因此您需要存储每个节点的所有父节点以使用上述方法，或者在进入树时执行多个SQL查询（希望您的树中没有循环！），尽管您可以重用相同的预编译语句（假设节点都是相同类型并且都存储在单个表中）以防止重新编译SQL，因此它可能不会更慢，实际上，通过对查询应用数据库优化，它可能更可取。可能需要运行一些测试来找出。

如果您只存储一棵树，则您的问题变成仅查询子树，然后应用第二个答案。

- JeeBee

Answer 7

请在 Google 上搜索“物化路径”或“遗传树”...

- Thomas Hansen

Answer 8

在Oracle中，有SELECT ... CONNECT BY语句来检索树形结构。

- Dmitry Khalatov

Answer 9

我是一个简单方法存储ID与其父ID相关联的粉丝：

ID     ParentID
1      null
2      null
3      1
4      2
...    ...

它易于维护，且可扩展性非常强。

- Galwegian

---

当我最初回答时，它不在那里。 - Galwegian

实际上，这不可扩展。如果你经常使用深度为n的整个树形结构，你需要进行n次查询才能获取所有数据。对于高度较高且繁忙的树形结构（例如论坛），这可能会导致性能问题。 - staticsan

是的，认真点，删掉关于可扩展性的那一部分。随着树的大小增加，读取速度会变得越来越慢。这几乎是最糟糕的扩展选项，而它通常是最常见的用例（读取）。 - Quibblesome

Answer 10

不能适用于所有情况，但例如给定一个注释结构：

ID | ParentCommentID

你还可以存储TopCommentID，它代表了最顶层的评论：

ID | ParentCommentID | TopCommentID

当评论为顶级评论时，TopCommentID 和 ParentCommentID 均为 null 或 0。对于子评论，ParentCommentID 指向其上方的评论，而 TopCommentID 则指向最顶层的父评论。

- Tom Gullen