sql - 针对树结构的优化 SQL

Question

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

你会使用一种特殊的算法来一次获取所有数据，最大限度地减少数据库调用的数量并在代码中处理它吗？

或者您会使用对数据库进行多次调用并直接从数据库中完成结构吗？

也许有基于 x 数量的数据库行、层次结构深度或其他什么的不同答案？

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

score 18 · Accepted Answer

这实际上取决于您将如何访问树。

一种巧妙的技术是给每个节点一个字符串 id，其中父节点的 id 是子节点的可预测子字符串。例如，父级可能是“01”，子级可能是“0100”、“0101”、“0102”等。这样您可以一次从数据库中选择整个子树：

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

因为条件是初始子字符串，ID 列上的索引会加快查询速度。

score 15 · Accepted Answer

在 RDMS 中存储树的所有方法中，最常见的是邻接表和嵌套集。嵌套集针对读取进行了优化，并且可以在单个查询中检索整个树。邻接列表针对写入进行了优化，可以在简单的查询中添加。

使用邻接列表，每个节点都具有引用父节点或子节点的列（其他链接也是可能的）。使用它，您可以基于父子关系构建层次结构。不幸的是，除非您限制树的深度，否则您无法在一个查询中提取整个内容，并且读取它通常比更新它要慢。

使用嵌套集模型，反之亦然，读取快速且容易，但更新变得复杂，因为您必须维护编号系统。嵌套集模型通过使用基于前序的编号系统枚举所有节点来对父系和排序顺序进行编码。

我使用了嵌套集模型，虽然它对于读取优化大型层次结构很复杂，但它是值得的。一旦你做了一些练习来绘制树并给节点编号，你应该掌握它的窍门。

我对这种方法的研究始于这篇文章：Managing Hierarchical Data in MySQL。

score 8 · Accepted Answer

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

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))

我还建议使用触发器来防止每棵树有多个根节点（空父节点），并防止相关节点属于不同的 TreeID（但这些比上面的要简单一些。）

您需要检查您的特定情况，以查看此解决方案是否可以接受。希望这可以帮助！

score 4 · Accepted Answer

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" (read-heavy) 和 "acts_as_nested_set" (write-heavy) 插件。我没有一个很好的链接来比较它们。

score 2 · Accepted Answer

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

从父母那里，找到所有孩子。

一个。到特定深度。例如，给定我的直系父母，深度为 1 的所有孩子都是我的兄弟姐妹。

湾。到树底。
从一个孩子，找到所有的父母。

一个。到特定深度。例如，我的直系父母是深度为 1 的父母。

湾。到无限的深度。

(a) 案例（特定深度）在 SQL 中更容易。特殊情况（深度=1）在 SQL 中是微不足道的。非零深度更难。可以通过有限数量的连接来完成有限但非零的深度。（b）的情况，深度不定（到顶部，到底部），真的很难。

如果您的树很大（数百万个节点），那么无论您尝试做什么，您都处于一个受伤的世界。

如果你的树有一百万个节点，只需将它全部提取到内存中并在那里处理它。在 OO 世界中，生活要简单得多。只需获取行并在返回行时构建树。

如果你有一棵巨大的树，你有两个选择。

用于处理无限获取的递归游标。这意味着结构的维护是 O(1) - 只需更新几个节点就可以了。但是获取是 O(n*log(n)) 因为您必须为每个具有子节点的节点打开一个游标。
聪明的“堆编号”算法可以对每个节点的父代进行编码。一旦每个节点都正确编号，一个简单的 SQL SELECT 就可以用于所有四种类型的查询。然而，对树结构的更改需要重新编号节点，与检索成本相比，更改成本相当高。

score 1 · Accepted Answer

如果数据库中有很多树，并且只能取出整棵树，我会为数据库中的每个节点存储一个树 ID（或根节点 ID）和父节点 ID，获取所有节点特定的树 ID，以及内存中的进程。

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

如果您只存储一棵树，您的问题将成为仅查询子树之一，并应用第二个答案。

score 1 · Accepted Answer

我喜欢存储与其 parentID 关联的 ID 的简单方法：

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

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

score 1 · Accepted Answer

1

谷歌“物化路径”或“遗传树”......

于 2008-11-25T13:40:08.867 回答

score 1 · Accepted Answer

1

在 Oracle 中有 SELECT ... CONNECT BY 语句来检索树。

于 2008-11-25T13:42:47.600 回答

score 0 · Accepted Answer

这篇文章很有趣，因为它展示了一些检索方法以及一种将沿袭存储为派生列的方法。沿袭提供了一种无需太多连接即可检索层次结构的快捷方法。

score 0 · Accepted Answer

不适用于所有情况，但例如给出评论结构：

ID | ParentCommentID

您还可以存储TopCommentID代表最多评论的内容：

ID | ParentCommentID | TopCommentID

TopCommentID和ParentCommentID在哪里null或0何时是最重要的评论。对于子评论，ParentCommentID指向其上方的评论，并TopCommentID指向最顶层的父评论。

sql - 针对树结构的优化 SQL

11 回答 11

Related

Reference