65.9K
CodeProject 正在变化。 阅读更多。
Home

计算 Microsoft SQL Server 中的树成本

mihirj
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.56/5 (4投票s)

2014年1月2日

CPOL

4分钟阅读

viewsIcon

20830

downloadIcon

195

本文介绍了一种用于存储树结构的数据库模式设计以及一种计算其成本的算法。

引言

树结构是当今世界最流行的数据结构之一。它们不仅能有效地组织数据，而且还提供高效的查找。使用 C、C++、Java、C#.NET 等编程语言实现树并不罕见。然而，在数据库中实现树状结构并不普及。在这里，我将首先展示一种简单的数据库模式设计，用于存储具有 N 个子节点的树（通常称为 N 叉树）。然后，我将解释一种计算树成本的技术。读者可以根据自己的需求，通过实现各种属性来扩展此结构。我希望您觉得它有所帮助。

背景

树是一种层次结构，它源自一个称为根节点的单个节点。每个节点（叶节点除外）最多可以有 N 个子节点（在 N 叉树中）。没有子节点的节点称为叶节点。在本教程中，我们假设一棵树，其中每个节点都关联着一个权重。树中的每条链接都关联着一个链接权重，节点的“成本”由下式确定：

Node cost j = Node weight j + Sum of(Link weight of child i * Node weight of child i)

设计模式

数据库模式由两个表组成：Nodes 和 Links。Nodes 表的设计如下所示：

每个节点包含 NodeWeight，用于计算其父节点的成本。成本使用上述公式计算。

Links 表的设计如下：

LinkWeight 定义了连接节点与其父节点的链接成本。上图所示的 Links 表包含两个树结构。为简洁起见，我在下图为该树结构提供了图示表示。

动机

如上所述的树结构在数据库中存储层次化数据非常有用。此类模式的一个非常流行的应用是物料清单。但是，为了避免将此应用刻板印象化为物料清单，我将解释一个非常通用的设计。此类数据库结构也可以使用通用表表达式（CTE）进行遍历，然而，在大数据库上，CTE 可能会产生高计算成本。本文所述的模式非常轻量级，因为它使用 Stack 作为遍历树的数据结构。

Using the Code

下面用于计算树成本的算法可以分为两部分。该过程接受节点 ID 作为输入，并计算该节点的成本。传递根节点 ID 将给出其子树的成本；例如，传递 F 的 ID 将生成以 F 为根的子树的成本。让我们开始创建临时表来存储中间数据。

提取有根树

CREATE PROCEDURE GetTreeCost
(
    @NodeID INT
)
AS
BEGIN
CREATE TABLE #TREE
(
    RecordID INT IDENTITY(1,1),
    ParentNodeID INT,
    NodeID INT,
    NodeWeight DECIMAL(18,2),
    LinkWeight INT,
    LevelID INT,
    ProcessingComplete BIT
)

CREATE TABLE #STACK
(
    ParentNodeID INT,
    NodeID INT,
    LevelID INT
)

第一部分可以标记为“树形成”。给定一个节点 ID，我们首先在一个临时表 #TREE 中提取以该节点为根的树结构。

INSERT INTO #STACK
SELECT -1, @NodeID, NodeWeight FROM Nodes WHERE NodeID = @NodeID

INSERT INTO #TREE 
SELECT -1, @NodeID, NodeWeight, 1, 0, 0 FROM Nodes WHERE NodeID = @NodeID

WHILE((SELECT COUNT(*) FROM #STACK) > 0)
BEGIN
    SELECT TOP 1 @CurrentNodeID = NodeID, _
    @CurrentParentID = ParentNodeID, @CurrentLevelID = LevelID FROM #STACK    

    DELETE FROM #STACK WHERE NodeID = @CurrentNodeID AND _
    ParentNodeID = @CurrentParentID AND LevelID = @CurrentLevelID

    IF ((SELECT COUNT(*) FROM Links L WHERE L.ParentNodeID = @CurrentNodeID) > 0)
    BEGIN
        INSERT INTO #STACK
        SELECT @CurrentNodeID, L.NodeID, @CurrentLevelID + 1
        FROM Links L WHERE L.ParentNodeID = @CurrentNodeID
    
        INSERT INTO #TREE(ParentNodeID, NodeID, _
        NodeWeight, LinkWeight, LevelID, ProcessingComplete)
        SELECT @CurrentNodeID, L.NodeID, P.NodeWeight, _
        L.LinkWeight, @CurrentLevelID + 1, 0 FROM Links L 
        INNER JOIN Nodes P ON L.NodeID = P.NodeID WHERE L.ParentNodeID = @CurrentNodeID
    END
END

为了提取给定节点 ID 的树结构，我们使用一个基于 Stack 抽象的简单逻辑。最初，我们将传入的节点 ID 添加到堆栈中。由于此节点不是任何节点的子节点，因此其父 ID 保持为 -1。最后，为树节点维护一个级别，对于堆栈中的根节点以及树中的根节点，级别为 0。

现在，我们进行迭代，直到 Stack 中还有元素。提取树的算法可以表述如下：

  1. 从堆栈中弹出顶部节点（select 和 delete）
  2. 使用 Links 表检查选定的节点是否为父节点
  3. 如果不是，则继续
  4. 否则，将节点的子节点添加到 Tree 中，并将它们推送到 Stack，其 LevelID = CurrentLevelID + 1
  5. Continue

提取树后，#TEMP 的外观如下面的图所示：

ProcessingComplete 字段在成本计算阶段使用。

计算树成本

在 #TREE 临时表中准备好树后，我们现在可以继续计算树的成本。建议读者参考上面给出的计算树成本的公式。成本计算的代码起初看起来有些复杂，但最终是一个简单的算法。

-- read from tree starting from leaf
WHILE((SELECT COUNT(*) FROM #TREE WHERE ProcessingComplete = 0) > 0)
BEGIN
    DECLARE @MaxLevelID INT
    DECLARE @RecordID INT
    DECLARE @CurrentNodeWeight DECIMAL(18,2)
    DECLARE @UpLinkWeight INT
    
    SELECT @MaxLevelID = MAX(LevelID) FROM #TREE WHERE ProcessingComplete = 0
    
    SELECT @RecordID = RecordID, @CurrentNodeID = NodeID, _
    @CurrentParentID = ParentNodeID, @CurrentNodeWeight = NodeWeight, 
    @UpLinkWeight = LinkWeight FROM #TREE WHERE LevelID = @MaxLevelID AND ProcessingComplete = 0
    
    IF @CurrentParentID <> -1 -- this is not the top level Node
    BEGIN
        UPDATE #TREE SET NodeWeight = NodeWeight + @CurrentNodeWeight * @UpLinkWeight
        WHERE NodeID = @CurrentParentID
    END
    
    UPDATE #TREE SET ProcessingComplete = 1 WHERE RecordID = @RecordID
END

当一行被处理时，ProcessingComplete 字段将被标记。该算法以自底向上的方式进行，并逐级处理节点。我们首先处理叶节点（树中级别最低的节点，即具有最高级别 ID 的节点）。由于它们位于叶级别，因此它们没有任何子节点。我们可以使用上面给出的公式计算其父节点的成本。成本更新在以下行完成：

UPDATE #TREE SET NodeWeight = NodeWeight + @CurrentNodeWeight * @CurrentQuantity
WHERE NodeID = @CurrentParentID
将节点成本添加到其父节点后，我们将该节点标记为 Processed。我们一直这样做，直到树中的所有节点都被处理。由于我们以自底向上的方式计算成本，因此成本计算会在其下方级别的所有节点都被“处理”时到达中间节点。

最后，我们得到一个完全计算的树结构，如下面的图所示：

在上面的图中，节点 5 (E) 的最终成本可以看到为 106.69，这是从其子节点计算得出的。

关注点

树结构设计起来非常简单，存储数据也很高效。此类树结构的一个流行应用是物料清单。使用 CTE 方法处理此类结构很流行，然而，这种手工遍历结构使其轻量级且具有成本效益。

历史

  • v1.0.0 | 初始版本
© . All rights reserved.