当前位置：文江博客话题详情

针对树结构优化 SQL

发布于 2024-07-09 13:09:29 字数 341 浏览 8 评论 0原文

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

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

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

也许根据数据库行数、层次结构深度或其他因素有不同的答案？

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

紫﹏色ふ单纯 2024-07-16 13:09:30

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

ID | ParentCommentID

您还可以存储代表最上面评论的 TopCommentID：

ID | ParentCommentID | TopCommentID

其中 TopCommentID 和 ParentCommentID当它是最上面的评论时， 为 null 或 0。对于子评论，ParentCommentID 指向其上方的评论，TopCommentID 指向最上面的父评论。

Not going to work for all situations, but for example given a comment structure:

ID | ParentCommentID

You could also store TopCommentID which represents the top most comment:

ID | ParentCommentID | TopCommentID

Where the TopCommentID and ParentCommentID are null or 0 when it's the topmost comment. For child comments, ParentCommentID points to the comment above it, and TopCommentID points to the topmost parent.

回复收藏 0 原文

救赎№ 2024-07-16 13:09:30

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

回复收藏 0 原文

白昼 2024-07-16 13:09:30

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

回复收藏 0 原文

赤濁 2024-07-16 13:09:30

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

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

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

I am a fan of the simple method of storing an ID associated with its parentID:

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

It is easy to maintain, and very scalable.

回复收藏 0 原文

高冷爸爸 2024-07-16 13:09:29

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

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

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

回复收藏 0 原文

凉城 2024-07-16 13:09:29

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

从父项中找到所有子项。
a. 到特定的深度。例如，给定我的直系父母，所有深度为 1 的孩子都将是我的兄弟姐妹。
b. 到树的底部。
从孩子开始，找到所有父母。
a. 到特定的深度。例如，我的直接父母是深度为 1 的父母。
b. 无限深度。

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

如果你的树巨大（数百万个节点），那么无论你尝试做什么，你都会陷入一个受伤的世界。

如果您的树少于一百万个节点，只需将其全部提取到内存中并在那里进行处理即可。在面向对象的世界中，生活要简单得多。只需获取行并在返回行时构建树即可。

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

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

回复收藏 0 原文

美人迟暮 2024-07-16 13:09:29

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

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

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

因为标准是初始子字符串，ID 列上的索引将加快查询速度。

It really depends on how you are going to access the tree.

One clever technique is to give every node a string id, where the parent's id is a predictable substring of the child. For example, the parent could be '01', and the children would be '0100', '0101', '0102', etc. This way you can select an entire subtree from the database at once with:

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

Because the criterion is an initial substring, an index on the ID column would speed the query.

回复收藏 0 原文

很糊涂小朋友 2024-07-16 13:09:29

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

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

对于嵌套集合模型，情况正好相反，读取快速且简单，但更新变得复杂，因为您必须维护编号系统。嵌套集模型通过使用基于预序的编号系统枚举所有节点来对起源和排序顺序进行编码。

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

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

回复收藏 0 原文

请恋爱 2024-07-16 13:09:29

在我开发的产品中，我们在 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))

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

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

In the product I work on we have some tree structures stored in SQL Server and use the technique mentioned above to store a node's hierarchy in the record. i.e.

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

Maintaining the the hierarchy is the tricky bit of course and makes use of triggers. But generating it on an insert/delete/move is never recursive, because the parent or child's hierarchy has all the information you need.

you can get all of node's descendants thusly:

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

Here's the insert trigger:

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

and here's the update trigger:

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

one more bit, a check constraint to prevent a circular reference in tree nodes:

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

I would also recommend triggers to prevent more than one root node (null parent) per tree, and to keep related nodes from belonging to different TreeIDs (but those are a little more trivial than the above.)

You'll want to check for your particular case to see if this solution performs acceptably. Hope this helps!

回复收藏 0 原文