SQL 数据库中的树

• 下载示例 - 1 Kb

引言

迟早，在您的数据库项目中，您将需要存储分层信息。例如，企业结构、商品类别、产品目录或文档文件夹都是此类结构的良好候选。当然，使用自关联表很容易实现这种存储。当您需要回答分层问题时，问题就出现了。例如，如果我们有一个企业结构，需要知道有多少员工向经理“X”汇报？对此问题已经有一些解决方案。

参见

• https://codeproject.org.cn/cs/database/persisting_trees.asp

Joe Celko 的书籍和文章也涵盖了这一点。

上述技术在您只读取数据时效果很好，但当您需要修改树时，性能会大大降低。

我将介绍一种在读取时性能相似，但在修改树时性能更好的方法。

想法

假设我们有以下表

其中 NodeId 是主键，ParentId 是外键，NodeName 是一些额外字段。为了提供简单的示例，让我们假设 NodeName 上有唯一约束。

对于下面所有示例，我将使用以下树

让我们创建另一个表，它与 Node 表有两个关系

其中 NodeId 和 ParentId 都是引用 Node 表的外键。

Tree 表中的每条记录都表示 Tree.NodeId 指向的节点具有 Tree.ParentId 指向的祖先。我理解的祖先是节点到树根路径上的任何节点，即直接父节点、祖父节点或曾祖父节点等。

现在，让我们确保一个简单的不变式：Node 表中每个节点的**所有**祖先都在 Tree 表中列出。

例如，对于节点 4，它们将是 2 和 1。

这个不变式的直接结果是：从节点获取到树根的完整路径非常容易——只需从 Tree 表中选择与所查找节点相关的**所有**记录。让我们写下这个选择语句。假设我们需要查找从节点 7 到根的路径。

查询 1

select p.*
from Node n, Tree t, Node p
where n.NodeName=7
    and n.NodeId = t.NodeId
    and t.ParentId = p.NodeId

这是一个非常直接的选择，不是吗？

上述不变式的第二个结果是：我们可以选择节点的所有后代。这是因为我们在 Tree 表中为 Node 表中的每个节点列出了**所有**祖先，当然也包括所查找节点的**所有**祖先。为了选择整个子树，我们只需查询以所查找节点作为其祖先的所有节点。

查询 2

select c.*
from Node n, Tree t, Node c
where n.NodeName=2
    and n.NodeId = t.ParentId
    and t.NodeId = c.NodeId

就是这么简单。请注意，这两个查询在通过 Tree 表的方向上是相反的。

实现

在继续之前，请允许我做两点说明。

# 1：根据我的经验，在 Tree 表中再增加一个字段来表示 NodeId 和 ParentId 指向的节点之间的距离，换句话说，即祖先的级别，会非常方便。所以实际结构包含 Level 字段。

# 2：在大多数可能的情况下，我们需要节点的子树或从节点到根的路径，包括节点本身。因此，在 Tree 表中将节点本身作为其 0 级祖先会很有用。

可以通过存储过程或触发器来实现上述不变式。我个人更喜欢触发器。

让我们从 Node 表的插入触发器开始。我将使用 MS SQL server。

首先，触发器必须创建一个记录以满足 #2。这可以通过以下语句完成

    insert into Tree(NodeId, ParentId, Level)
    select NodeId, NodeId, 0
    from inserted

现在，我们准备好添加插入节点的**所有**祖先的列表。请注意，每个插入节点的父节点已经列出了他**所有**的祖先，所以我们可以以此为基础。但我们需要将父节点的 NodeId 替换为新节点的 id 并增加级别。

    insert into Tree(NodeId, ParentId, Level)
    select n.NodeId, t.ParentId, t.Level + 1
    from inserted n, Tree t
    where n.ParentId = t.NodeId

所以整个触发器将是

create trigger NodeInsert on Node for insert as
begin
    set nocount on

    insert into Tree(NodeId, ParentId, Level)
    select NodeId, NodeId, 0
    from inserted

    insert into Tree(NodeId, ParentId, Level)
    select n.NodeId, t.ParentId, t.Level + 1
    from inserted n, Tree t
    where n.ParentId = t.NodeId
end
go

现在是定义 update 触发器来处理节点父节点更改的时候了。update 触发器的目标是从 Tree 表中删除所有过时的记录并创建新的记录。为了最大限度地减少此触发器所做的更改，让我们像在 insert 触发器中所做的那样，重用 Tree 表中已存储的信息。更改节点的父节点不会受到什么影响？

显然，对于更新的节点本身，它只有一条满足 #2 的记录是持久的。对于后代，它们将是**所有**关于更新节点下方（包括该节点本身）的祖先的记录。而更新节点**上方**的任何祖先都将过时。

例如，如果我们更改节点 4 的父节点，那么对于节点 5、6 和 7，只有节点 4 上方的祖先，即 1 和 2，会发生变化。

第一步，我们将所有后代的节点备份到以下表中

    declare @child table(NodeId int, Level int)

我们插入所有后代的**主键**以及它们相对于更新节点的**级别**。条件 t.Level > 0 允许排除更新节点本身不被插入到 @child 表中。

    insert into @child(NodeId, Level)
    select t.NodeId, t.Level
    from inserted n, Tree t
    where n.NodeId = t.ParentId and t.Level > 0

第二步删除所有后代的所有过时行

    delete Tree
    where
        Tree.NodeId in(select NodeId from @child)
        and Tree.ParentId in(
            select t.ParentId
            from inserted n, Tree t
            where n.NodeId = t.NodeId and t.Level > 0
        )

条件 t.Level > 0 排除更新节点本身不被删除。

第三步删除更新节点的过时记录

    delete Tree
    where Tree.NodeId in(select NodeId from inserted)
        and Tree.Level > 0

在接下来的两个步骤中，我们将向 Tree 表中填充新信息。

所以第四步将是

    insert into Tree(NodeId, ParentId, Level)
    select n.NodeId, t.ParentId, t.Level + 1
    from inserted n, Tree t
    where n.ParentId = t.NodeId

这与我们在 insert 触发器中做的完全一样。

最后是第五步

    insert into Tree(NodeId, ParentId, Level)
    select c.NodeId, t.ParentId, t.Level + c.Level
    from inserted n, Tree t, @child c
    where n.NodeId = t.NodeId and t.Level > 0

在这个语句中没有与 @child 表进行任何连接，这可能看起来很奇怪。但这就是我们在这里真正需要的，因为我们将为每个子节点重复祖先信息。另外请注意，我们添加的是子节点的级别（存储在 @child 表中），而不是仅仅加 1。

整个触发器看起来是

create trigger NodeUpdate on Node for update as
if update(ParentId)
begin
    set nocount on

    declare @child table(NodeId int, Level int)

    insert into @child(NodeId, Level)
    select t.NodeId, t.Level
    from inserted n, Tree t
    where n.NodeId = t.ParentId and t.Level > 0

    delete Tree
    where
        Tree.NodeId in(select NodeId from @child)
        and Tree.ParentId in(
            select t.ParentId
            from inserted n, Tree t
            where n.NodeId = t.NodeId and t.Level > 0
        )

    delete Tree
    where Tree.NodeId in(select NodeId from inserted) and Tree.Level > 0

    insert into Tree(NodeId, ParentId, Level)
    select n.NodeId, t.ParentId, t.Level + 1
    from inserted n, Tree t
    where n.ParentId = t.NodeId

    insert into Tree(NodeId, ParentId, Level)
    select c.NodeId, t.ParentId, t.Level + c.Level
    from inserted n, Tree t, @child c
    where n.NodeId = t.NodeId and t.Level > 0
end
go

正如您所见，只有在 ParentId 被更新时它才会执行，而 Node 表的所有其他更新都将被第一个 if 语句过滤掉。

实现的限制

如果您要一次插入或更新多个 Node，请确保您只在一个树级别上进行此操作。从实际角度来看，这根本不是一个严格的限制。

剩余步骤

为了使功能完整，我们需要能够清除整个 Tree 表并从头开始填充它。为此创建一个存储过程可能是一个好主意，我不会剥夺您自己编写这样一个过程的乐趣。

示例

您可以在附件文件中找到用于创建两个表、两个触发器以及填充 Node 表的语句。它还包含查询 1 和查询 2 以及用于更改节点父节点的语句。