树结构的优化SQL

Question

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

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

或者你会使用多次调用数据库并直接从数据库中获取结构？

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

编辑:我使用Microsoft SQL Server,但其他观点的答案也很有趣.

Answer 1

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

一种聪明的技术是为每个节点提供一个字符串id,其中父节点的id是子节点的可预测子字符串.例如,父级可以是"01",子级可以是"0100","0101","0102"等.这样,您可以一次从数据库中选择整个子树:

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

因为标准是初始子字符串,所以ID列上的索引会加快查询速度.

Answer 2

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

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

使用嵌套集模型,反之亦然,读取快速简便,但更新变得复杂,因为您必须维护编号系统.嵌套集模型通过使用基于预订单的编号系统枚举所有节点来编码父级和排序顺序.

我已经使用了嵌套集模型,虽然读取优化大型层次结构很复杂但值得.一旦你做了几个练习来绘制树和编号节点,你应该得到它的悬念.

我对这种方法的研究始于本文:在MySQL中管理分层数据.

Answer 3

查看嵌套集层次结构模型.它很酷很有用.

Answer 4

在我工作的产品中,我们在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父节点),并保持相关节点不属于不同的TreeID(但这些节点比上面的更简单.)

您需要检查特定情况,看看此解决方案是否可以接受.希望这可以帮助!

Answer 5

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

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

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