数据结构与算法分析 —— C 语言描述：B 树

2022-04-07 本文已影响0人 Sun东辉

虽然我们常看到的查找树都是二叉树，但是还有一种常用的查找树不是二叉树。这种树叫做 B 树（B-tree）。

阶为 M 的 B 树是一棵具有下列结果特性的树：

树的根或者是一片树叶，或者其儿子数在 2 和 M 之间。
除根外，所有非树叶节点的儿子数在 [M/2] 和 M 之间。
所有的树叶都在相同的深度上。

所有的数据都存储在树叶上。在每一个内部节点上皆含有指向该节点各儿子的指针 $P_1,P_2,P_3,...,P_M$ 和分别代表在子树 $P_2,P_3,...,P_M$ 中发现的最小关键字的值为 $k_1,k_2,...,k_{M-1}$ 。当然，可能有些指针是 NULL，而其对应的 $k_i$ 则是未定义的。对于每一个节点，其子树 $P_1$ 中所有的关键字都小于子树 $P_2$ 的关键字，等等。树叶包含所有实际数据，这些数据或者是关键字本身，或者是指向含有这些关键字的记录的指针。我们本次只讨论前者。B 树有多种定义，这些定义在一些次要的细节有所不同，不过，我们只讨论最流行的结构，即所有实际数据只存储在树叶上。（另一种流行的结构允许实际数据存储在树叶上，也可以存储在内部节点上）这里还需要限制，在非根树叶中关键字的个数也在 [M/2] 和 M 之间。

4 阶 B 树更流行的称呼是 2-3-4 树，而 3 阶 B 树叫做 2-3 树。我们将通过 2-3 树的特殊情形来描述 B 树的操作。

为了执行一次 Find ，我们需要从根开始并根据要查找的关键字与存储在节点上的两个（很可能是一个）值之间的关键确定（最多）三个方向中的一个方向。

为了对尚未见过的关键字 X 执行一次 Insert，我们需要首先按照执行 Find 的步骤进行，当到达一片树叶时，我们就找到了插入 X 的正确的位置。

由于一片树叶只能容纳两个或者三个关键字，因此上面的做法不总是可行的。如果我们现在试图把一个关键字插入到已经容纳了 3 个关键字的节点上，将是不被允许的，解决办法是，构造两个节点，每个节点有两个关键字，同时调整它们父节点的信息。

然而，这个想法也不总是行得通，因为可能造成父节点关键字的溢出，但是我们可以在通向根的路径上一直这么分下去，直到或者到达根节点，或者找到一个只有两个儿子的节点。

还要注意，当插入一个关键字的时候，只有在访问路径上的那些内部节点才有可能发生变化，这些变化与这条路径的长度成比例；但要注意，由于需要处理的情况相当多，因此很容易发生错误。

对于一个节点的儿子太多的情况还有一些其他处理办法，而我们刚才描述的方法恐怕是最简单的情况。当试图将第四个关键字添加到一片树叶上的时候，我们可以首先查找只有两个关键字的兄弟，而不是把这个节点分裂成两个。这个策略也可以用到内部节点上并尽量使更多的节点具有足够的关键字。这种方法使得例程的编制稍微有些复杂，但是浪费的空间较少。

我们可以通过查找要删除的关键字并将其除去而完成删除操作。如果这个关键字是一个节点仅有的两个关键字中的一个，那么将它除去后就只剩一个关键字了。此时我们可以通过把这个节点与它的一个兄弟合并来进行调整。如果这个兄弟已有 3 个关键字，那么我们可以从中取出一个使得两个节点各自有两个关键字。如果这个兄弟只有两个关键字，那我们就将这两个节点合并成一个具有 3 个关键字的节点。现在这个节点的父亲则失去了一个儿子，因此我们还须向上检查直到顶部。如果根节点失去了它的第二个儿子，那么这个根也要删除，而树则减少了一层。当合并节点的时候，我们必须记住要更新保存在这些内部节点上的信息。

对于一般的 M 阶 B 树，当插入一个关键字时，唯一的困难发生在接收该关键字的节点已经具有 M 个关键字的时候。插入这个关键字使得该节点具有 M+1 个关键字，我们可以把它分裂成两个节点，它们分别具有 [(M+1)/2] 个关键字和 [(M+1)/2] 个关键字。由于这使得父节点多出一个儿子，因此我们必须检查这个节点是否可被父节点接受，如果父节点已经具有 M 个儿子，那么这个父节点就要被分裂成两个节点。我们重复这个过程直到一个具有少于 M 个儿子的父节点。如果分裂根节点，那么我们就要创建一个新的根，这个根有两个儿子。

B 树的深度最多是 [ $\log{\frac{M}2}{N}$ ]。在路径上的每个节点，我们执行 $O(\log M)$ 的工作量以确定选择哪个分支（使用折半查找），但是 Insert 和 Delete 可能需要 $O(M)$ 的工作量来调整该节点上的所有信息。因此，对于每一个 Insert 和 Delete 运算，最坏情形的运行时间为 $O(M \log_M N)$ = $O((M/\log M)\log N)$ ，不过一次 Find 只花费 $O(\log N)$ 时间。经验之处，从运行时间考虑，M 的最好（合法的）选择是 M=3 或 M=4；这与上面的界一致，它指出，当 M 再增大时插入和删除的时间就会增加。如果我们只关心主存的速度，则更高阶的 B 树就没什么优势了。

B 树实际用于数据库系统，在那里树被存储在物理的磁盘上而不是主存中。一般来说，对磁盘的访问要比任何主存操作慢几个数量级。如果我们使用 M 阶 B 树，那么磁盘访问次数是 $O(\log_M N)$ 。虽然每次磁盘访问花费 $O(\log_M)$ 来确定分支的方向，但是执行该操作的时间一般要比读存储器的区块（block）所花费的时间少得多，因此可以视为无足轻重的（只要 M 选择得合理）。即使在每个节点执行更新要花费 $O(M)$ 操作时间，这些花费一般还不是很大。此时 M 的值选择为使得一个内部节点仍然能够装入一个磁盘区块的最大值，那么一般说来 32≤ M ≤ 256。选择存储在一片树叶上的元素最大个数时，要使得如果树叶是满的那么就装满一个区块。这意味着，一个记录总是可以在很少的磁盘访问中找到，因为典型的 B 树的深度只有 2 或 3，而根（很可能只有一层）可以放在主存中。

分析指出，一棵 B 树将被占满 $\ln 2 = 69\%$ 。当一棵树得到它的第 (M+1)项时，例程不是总去分裂节点，而是搜索能够接纳新儿子的兄弟，此时我们就能够更好地利用空间。

数据结构与算法分析 —— C 语言描述：B 树

猜你喜欢

热点阅读