持久化在关系数据库中的通用树

Daniel Aioanei

4.46/5 (20投票s)

2003年6月12日

11分钟阅读

205727

1925

通过快速路径查找能力在关系数据库中持久化通用树。

下载源代码 - 8.58 Kb

摘要

我们提出了一些可以在关系数据库中实现的通用树上进行计算的技术，这些树以广泛使用的子-父格式存储在自连接表中，并且我们证明了该技术在非常普遍的假设下是有效的。另一种，实际上要好得多的格式。

引言

关系数据库在持久化树的路径查找问题上近期没有取得多大进展。供应商特定的 SQL 扩展，例如 Oracle 中的 `CONNECT BY` 子句，是该领域的一个进一步发展。但普通开发者仍然发现其性能对于大多数现实情况来说是不可接受的，而且不建议将应用程序与供应商特定的数据库绑定。虽然为不同的数据库实现不同版本的存储过程或 SQL 是可以接受的，但当所有应用程序逻辑都基于仅由特定供应商提供的树功能时，将应用程序移植到其他数据库系统就会变得更加困难。而且，客户通常不会购买最昂贵的商业数据库系统。

我们提出了一些解决路径查找问题的方案，这些方案不依赖于特定数据库，同时仍能提供比某些支持树的特定数据库扩展更好的性能。

修改子-父格式以保留每个节点的完整路径

这部分是可选的。可以跳过这部分直接到“备选格式”部分。

数据库结构

读者应该注意到，本节提出的方法对于此类持久化树的只读访问尤其有效。写入操作的复杂性在本文中也有大致介绍。此外，备选格式很可能是您正在寻找的。

出于性能考虑，可以尝试为每个节点添加表示从树根到该节点路径的信息。实际上，我不知道有任何应用程序可以从中受益，如果我找不到这样的东西，我将删除这一部分。

我们在包含子到父链接的表中添加了一个名为 `Path` 的列。此列不应过大，因此我们将首先分析其空间复杂度。计算 `Path` 列值所需的时间不太重要，因为我们主要在此讨论只读树。

`Path` 列应该是一种位序列。例如，Oracle 中的 `RAW` 或 SQL Server 中的 `Binary`。我们递归地定义 `Path` 值（树是递归处理的，不是吗？）

Path(RootNode) = Null

对于根节点以外的节点，

Path(Node) = Path(Parent(Node)) + Index(Node, Parent(Node))

其中 + 表示位序列的连接，而 `Index` 是父节点子节点列表中子节点的序数。

请注意，`Path` 将唯一标识树中的每个节点。如果需要，可以在此列上创建唯一索引，以防单个树存储在表中。

给定级别的所有节点将在相同的位大小下表示 `Index`。令树中的节点数为 N，级别为 0, 1, ..., L，并且 `max(Index(i))` 为 C_i，其中 0 <= i <= L – 1。如果愿意，我们还可以定义 `max(Index(C_L)) = 0`，因为最高级别的节点没有子节点。很明显，级别 i 上的节点的 `Index` 的位大小等于 ceil(log₂(C_i))，其中 ceil 是一个整数值，等于大于或等于其数值参数的最小整数，而 log₂ 是指定数字的以 2 为底的对数。

有了这个 `Path` 格式，当我们给出子根时，我们可以轻松地选择一个完整的子树，搜索 `Path(Node).startsWith(Path(SubRoot))` 的节点，并且我们还可以从每个节点获取标识到根路径所需的信息。但是，`Path` 列必须多长才能包含这些丰富的信息？

如果树是真正静态的（只读的），那么 `Path` 大小是专门为它计算的。如果对没有必要更改树结构或修改列长度（尤其是在运行时）的操作有强大的保证，则可以使用此方法。另一种方法是首先计算给定树节点数的最大 `Path` 大小。即使第一种方法不需要知道具有 N 个节点的树的最大路径大小，但在数学上证明这两种方法都适用于实际使用仍然是必要的。

路径大小界限

对于任何给定的节点数 N，我们找出所需 `Path` 大小的最坏情况，并计算该最大 `Path` 大小值。如果我们为 `Path` 列分配最大大小，那么我们可以保证，无论具有 N 个或更少节点数的树“看起来”多么“奇怪”，它都会“适合”我们的表。

具有 N 个节点和 L 个级别的任何给定树 T_N 的路径大小等于

PathSize(T_N) = ceil(log₂(C₀)) + ... + ceil(log₂(C_{L - 1}))

请注意，C₀ + ... + C_{L - 1} <= N – 1，当树中的每个节点最多有一个子节点，并且该子节点本身有子节点时，等式成立。我们在上述不等式定义的域中找到了 PathSize(T_N) 的上限。

PathSize(T_N) <= L + log(C₀ * ... * C_{L - 1})

算术-几何平均不等式告诉我们

(C₀ * ... * C_{L - 1})^{1 / L} <= (C₀ + ... + C_{L - 1}) / L

我们推断

PathSize(T_N) <= L + L * log₂((C₀ + ... + C_{L - 1}) / L) 
             <= L + L * log₂((N - 1) / L).

令函数 F : 1..N-1 ---> N 为不等式右侧的部分。我们将找到该函数在其定义域上的全局最大值。我们需要的是导数

F'(L) = 1 + 1 * log₂((N - 1) / L) + 
     L * (1 – N) / L² * 1 / ((N – 1) / L * ln(2)),

其中 ln 表示指定数字的自然（以 E 为底）对数。

F'(L) = log₂(2 * (N – 1) / L) – 1 / ln(2) 
      = (ln(2 * (N – 1) / L) – 1) / ln(2).

F' 是一个递减函数，它有一个唯一的根 L₀ = 2(N – 1) / E，其中 E 是欧拉数，约等于 2.71（对于那些对高精度算术感兴趣的人，请参阅链接）。

因此 F 的最大值为

F(L₀) = F(2(N – 1) / E) 
      = 2(N – 1) / E + 2(N – 1) / E * log₂((N - 1) * E / 2 (N – 1)) 
      = 2(N – 1) / E * (1 + log₂(E / 2)) = 2(N – 1) / (E * ln(2)).

更新行为

为了优化更新行为，可以分配大于实际所需值的 `Path` 大小，但它应始终小于或等于为应用程序接受的最大节点数计算的最大 `Path` 大小，以减少空间浪费。`Path` 字段的格式不必完全是我们之前描述的。可以在字段之间插入空间，以允许某些级别增长。例如，如果插入更有可能出现在树的某些级别，那么应该为 `Path` 字段的那些部分分配更多可用空间。如果在一个级别插入一个节点，而父节点的 `Path` 字段无法容纳新的子节点计数，那么所有 `Path` 值都必须更改以容纳对应于父节点级别的新的位。

最重要的是要避免引起某些 `Path` 不再适合 `Path` 字段的节点插入。正如之前证明的，这可以通过根据公式 2(N – 1) / (E * ln(2)) 计算最大路径大小来避免。只要节点数小于或等于 N，此路径大小将容纳树的任何更新，无论是插入还是删除。

如果删除或插入一个节点，其子树的所有 `Path` 值都必须相应更新。因此，叶子节点可以始终以 O(1) 时间删除，而叶子节点只能在 `Path` 父节点级别部分可以容纳增量值的情况下以 O(1) 时间添加。否则，时间复杂度为 O(n)。

数值

如果 N = 10,000，则最大 `Path` 大小小于 1.3 Ko，而对于 N = 1,000,000，我们得到 130 Ko 的界限。

Oracle 在 `UTL_RAW` 包中提供位序列支持，而 SQL Server 似乎与之相关的功能更为有限。

为了执行查询，例如形式为 `WHERE Path starts With '11011'`，如果使用的数据库提供的位序列操作支持不足，可以先将 `Path` 转换为十六进制字符串，然后检查 `Path` 是否在 D8 和 DF 之间，按字典顺序。

进一步研究

首先，必须计算一些平均值，特别是 `Path` 大小的平均值。

从通用树 T 到具有该属性的二叉树 B 的一些变换是显而易见的：在 T 中，当 x 是 y 的子节点时，x 在 B 中仍然是 y 的后代。这些变换基于在树中添加新的、虚拟的节点，以便在节点有两个以上的子节点时使其成为二叉树。一些更复杂的变换可以尝试将虚拟节点分组到完整的二叉子树中。

一种方法是将 0 位关联到左边，将 1 位关联到右边。

另一个想法是将二叉树覆盖在 Stern-Brocot 树之上，并将分数 m/n 用作 `Path` 列（实际上，可以有两个整数列）。如果二叉树有 L 个级别，则 m 和 n 可以等于 F_L，其中 F 是斐波那契数列。此结构的优点之一是，如果有人想找到两个（已约分的）有理数之间的另一个有理数，只需“介于”它们之间即可。

如果想限制 m 和 n 的值，可以使用 Farey 序列。它实际上是 Stern-Brocot 树的一部分。研究初始树的更改如何反映在 Stern-Brocot 树中也可能很有趣。

备选格式

在关系数据库中表示树的另一种方法是为每个节点保留一个正整数索引。我们称该列为 `NodeIndex`。如果 N 是树的节点数，我们将节点命名为 0, 1, ..., N – 1。本节介绍的格式所依据的整个思想是，序列 0, 1, ..., N – 1 必须是树的深度优先遍历。但是，这些信息不足以唯一地识别 N 个节点的有标签树中的已排序标记树。为了解决这个不便，我们在树表中添加了第二列，名为 `RightChildIndex`，它实际上是当前节点最右边子节点的索引。对于叶子节点，`RightChildIndex` 等于 `NodeIndex`。

举个例子

NodeIndex	0	1	2	3	4	5	6
RightChildIndex	6	1	5	4	4	5	6

给定 `NodeIndex` `i`，可以轻松执行 Oracle SQL 中描述的以下操作。所有这些操作都已在著名的 `Employee` 表上进行了测试。

选择其子树

SELECT t1.*
FROM employee t1, employee t2
WHERE i <= t1.nodeindex
AND t1.nodeindex <= t2.rightchildindex
AND t2.nodeindex = i;

例如，给定节点 2，该选择将查找索引在 2 到 5（含）之间的所有节点。

如果根节点本身不需要返回，则不等式 `i <= T1.NodeIndex` 必须更改为严格不等式。

获取从根到给定节点的路径

SELECT t1.*
FROM employee t1, employee t2
WHERE t1.nodeindex <= i
AND t1.rightchildindex >= t2.rightchildindex
AND t2.nodeindex = i;

例如，给定节点 3，其中条件搜索 `NodeIndex <= 3` 和 `RightChildIndex >= 4` 的节点

获取给定节点的直接子节点

SELECT t1.*
FROM employee t1, employee t2
WHERE t1.nodeindex > i
AND t1.nodeindex <= t2.rightchildindex
AND t2.nodeindex = i
AND 0 = (SELECT COUNT (1)
FROM employee q
WHERE nodeindx < q.nodeindex
AND q.nodeindex < t1.nodeindex
AND t1.rightchildindex <= q.rightchildindex
AND q.rightchildindex <= t2.rightchildindex);

可以通过同时以备选格式和广泛使用的子-父格式保存树来提高此操作的性能。

将节点插入为 `i` 的子节点

UPDATE employee
SET employee.nodeindex = employee.nodeindex + 1
WHERE employee.nodeindex > parentnode;

UPDATE employee
SET employee.rightchildindex = employee.rightchildindex + 1
WHERE employee.rightchildindex >= parentnode;

INSERT INTO employee
(nodeindex, rightchildindex, NAME, comments)
VALUES (parentnode + 1, parentnode + 1, nodename, nodecomments);

删除具有 `NodeIndex i` 的节点

DELETE employee
WHERE employee.nodeindex = i;

UPDATE employee
SET employee.nodeindex = employee.nodeindex - 1
WHERE employee.nodeindex > i;

UPDATE employee
SET employee.rightchildindex = employee.rightchildindex - 1
WHERE employee.rightchildindex > i;

引用 `NodeIndex` 的外键 `RightChildIndex` 必须是延迟的，如果以这种方式实现删除操作的话。这意味着它必须仅在事务结束时强制执行，而在事务期间不强制执行。

进一步研究

我们还可能希望存储树的广度优先遍历，但我还没有找到任何有用的应用程序。

树存档或复合

在某些应用程序中，尤其是在提供树结构可追溯性的应用程序中，需要“存档”树结构。如果某个时间点的树版本不常被访问，那么可以使用较短的编码来存储在数据库中。我推荐 Prüfer-Like Codes。对于大多数这些代码，具有 N 个节点的树的结构在 *线性时间* 内编码为 N – 2 个整数。请注意，这些编码仅存储树的结构，而不存储节点中的信息。无论如何，这些信息必须单独保留。

文章附带了 An encoding scheme for labeled trees 中描述的算法的完整 C# 实现。我还制作了一个 Java 实现该算法。

看起来 .NET 框架中缺少一个通用的 `TreeNode` 类（Windows 窗体中的那个对我帮助不大），所以我创建了一个具有所需最少功能的类。

public class TreeNode { 
public void Add(TreeNode child)... 
public TreeNode Parent... 
public int ChildCount... 
public IList Children...
}

`TreeEncoder` 类必须用邻接列表表示形式的树进行初始化。唯一感兴趣的方法是

public int[] encode()...

它实际上将 n 个节点的树编码为长度为 n – 2 的整数数组。

`TreeDecoder` 类知道如何从其紧凑表示中解码树

public IList[] decode()...
public int diameter()...
public int radius()...

并可以直接从其代码计算树的直径和半径，而无需先将树重建成内存。

结论

使用仅基本的树遍历算法可以有效地实现大量的树操作。进一步研究已知的树编码如何在关系数据库中高效应用将很有趣。