12.6. B 树¶
12.6.1. B 树¶
本模块介绍 B 树。 B 树通常归于 R. Bayer 和 E. McCreight 名下，他们在 1972 年的论文中描述了 B 树。到 1979 年，除哈希之外，B 树几乎取代了所有其他大型文件访问方法。 B 树或其某种变体， 就是 那些需要插入、删除和键范围查询 的应用的标准文件组织方式。大多数现代文件系统都用它实现。 B 树有效解决了实现基于磁盘的搜索树时遇到的所有主要问题：
B 树很浅，一部分原因是树始终高度平衡（所有叶结点都在同一 层），另一部分原因是分支因子相当大。因此到达某条给定记录只需访问少量磁盘块。
更新和查找操作只影响从根到包含目标记录的叶结点路径上的那些 磁盘块。一次操作影响的磁盘块越少，所需的磁盘 I/O 就越少。
B 树把相关记录（即键值相近的记录）放在同一磁盘块上， 这有助于把范围查询的磁盘 I/O 降到最低。
B 树保证树中每个结点至少填满到某个最低百分比。 这既提高了空间效率，又减少了查找或更新操作通常所需的磁盘读取次数。
\(m\) 阶 B 树定义为具有以下形状性质：
根要么是叶结点，要么至少有两个子结点。
除根之外的每个内部结点，其子结点数介于 \(\lceil m/2 \rceil\) 与 \(m\) 之间。
所有叶结点都在树的同一层，因此树始终高度平衡。
B 树是 2-3 树的推广。换句话说，2-3 树就是三阶 B 树。通常，B 树中结点的大小会选为一个磁盘块的大小。B 树的一种结点实现通常允许 100 个或更多的子结点。因此，B 树的结点就相当于一个磁盘块，树中存储的“指针”值实际上是包含子结点的块的编号（通常解释为相对于相应磁盘文件起始位置的偏移量）。在典型应用中，B 树对磁盘文件的访问将借助 缓冲池（buffer pool） 和诸如 LRU 这样的块替换方案来管理。
图 12.6.1 展示了一棵四阶 B 树。每个结点最多包含三个键，内部结点最多有四个子结点。
B 树中的查找是 2-3 树查找的推广。它是从 B 树根结点开始的两步交替过程。
在当前结点的记录上执行二分查找。 如果找到了带查找键的记录，则返回该记录。如果当前结点是叶结点且未找到键，则报告查找失败。
否则，沿正确的分支前进，重复该过程。
例如，考虑在图 12.6.1 的树中查找键值为 47 的记录。检查根结点并走第二个（右）分支。检查完第 1 层的结点后，走第三个分支到达下一层，到达包含键值 47 的记录的叶结点。
B 树插入是 2-3 树插入的推广。第一步是找到（在空间允许的情况下）应当包含待插入键的叶结点。如果该结点还有空间，则插入键。如果没有，则把结点一分为二，并把中间键提升到父结点。如果父结点因此变满，则它同样被分裂，其中间键被提升。
注意，这一插入过程保证所有结点至少半满。例如，当我们要向四阶 B 树的一个已满的内部结点插入时，现在有五个子结点需要处理。该结点被分裂成各含两个键的两个结点，从而保持 B 树的性质。五个子结点中居中的那个被提升到父结点。
12.6.1.1. B+ 树¶
上一节提到，B 树被普遍用于实现大规模的基于磁盘的系统。实际上，上一节描述的 B 树几乎从不被直接实现。最常见的实现是 B 树的一种变体，称为 \(\mathrm{B}^+\) 树。当需要更高效率时，会使用一种更复杂的变体，称为 \(\mathrm{B}^*\) 树。
再次考虑 线性索引 。当记录集合不会发生变化时，线性索引提供了一种极其高效的查找方式。问题在于如何处理那些恼人的插入和删除操作。我们可以保留“存储有序的基于数组的线性表”这一核心思想，但把线性表拆分成便于管理、也更易更新的块，使它更加灵活。该怎么做呢？首先，我们需要确定块应该多大。由于数据存放在磁盘上，把块的大小设为一个磁盘块或磁盘块大小的一个小倍数似乎是合理的。如果要插入的下一条记录属于一个尚未填满其磁盘块的块，我们就可以直接把它插入那里。这可能会导致该块中其他记录在数组中略微移动，但并不重要，因为只要在块内移动数据，就不会引发额外的磁盘访问。但如果这个块填满了包含它的整个磁盘块呢？我们可以把它一分为二。如果要删除一条记录呢？我们可以直接把被删除的记录从块中取出，但可能不希望留下太多接近空的块。因此，如果相邻块之间只有少量数据，我们可以把它们合并；或者在合计数据更多的相邻块之间重新分配数据。最大的问题在于：处理带给定键的记录时，如何找到所需的块。也许可以用某种树状结构来定位相应的块。这些想法正是 \(\mathrm{B}^+\) 树的动机所在。 \(\mathrm{B}^+\) 树本质上就是管理“有序的基于数组的线性表”的一种机制，其中线性表被拆分成块。
\(\mathrm{B}^+\) 树与 BST 或标准 B 树最显著的区别是： \(\mathrm{B}^+\) 树只在叶结点存储记录。内部结点存储键值，但这些值仅作为引导查找的占位符。这意味着内部结点在结构上与叶结点差异显著。内部结点存储引导查找的键，把每个键与指向子 \(\mathrm{B}^+\) 树结点的指针关联。叶结点存储实际记录；如果 \(\mathrm{B}^+\) 树纯粹用作索引，则存储键以及指向单独磁盘文件中实际记录的指针。与键大小相比，根据记录大小的不同， \(m\) 阶 \(\mathrm{B}^+\) 树的叶结点能存储的记录数可能多于或少于 \(m\) 条。要求只是叶结点存储足够多的记录，以保持至少半满。 \(\mathrm{B}^+\) 树的叶结点通常链接在一起构成双向链表。这样，只要访问链表上的所有叶结点，就可以按有序顺序遍历全部记录。下面是 \(\mathrm{B}^+\) 树结点接口的类 Java 伪代码表示。叶结点和内部结点的子类会实现这个接口。
/** Interface for B+ Tree nodes */
public interface BPNode<Key,E> {
public boolean isLeaf();
public int numrecs();
public Key[] keys();
}
有一个重要的实现细节需要注意：虽然图 12.6.1 显示内部结点包含三个键和四个指针，但 BPNode 类稍有不同——它存储的是键/指针对。图 12.6.1 按传统画法展示 \(\mathrm{B}^+\) 树。为简化实际实现，结点确实把一个键与每个指针关联。应当假定每个内部结点在最左侧位置还持有一个额外的键，它小于等于该结点最左侧子树中任何可能出现的键值。 \(\mathrm{B}^+\) 树的实现通常还会在最左侧叶结点中存储一条额外的哑记录，其键值小于任何合法的键值。
让我们较详细地看看最简单的 \(\mathrm{B}^+\) 树如何工作。这就是"\(2-3^+\) 树"，即三阶 \(\mathrm{B}^+\) 树。
接下来看如何查找。
最后看一个从 \(2-3^+\) 树中删除的例子
现在，把这些思想扩展到更高阶的 \(\mathrm{B}^+\) 树。
\(\mathrm{B}^+\) 树对范围查询格外出色。一旦找到区间内的第一条记录，其余键落在区间内的记录就可以这样访问：顺序处理第一个结点中剩余的记录，然后沿叶结点链表继续向下，直到需要为止。下面用几个例子说明 \(\mathrm{B}^+\) 树。
\(\mathrm{B}^+\) 树中的查找与普通 B 树几乎一样，只是查找必须始终进行到正确的叶结点。即使查找键值出现在内部结点中，那也只是一个占位符，并不能据此访问实际记录。下面是 \(\mathrm{B}^+\) 树查找算法的伪代码梗概。
private E findhelp(BPNode<Key,E> rt, Key k) {
int currec = binaryle(rt.keys(), rt.numrecs(), k);
if (rt.isLeaf()) {
if ((((BPLeaf<Key,E>)rt).keys())[currec] == k) {
return ((BPLeaf<Key,E>)rt).recs(currec);
}
else { return null; }
}
else{
return findhelp(((BPInternal<Key,E>)rt).pointers(currec), k);
}
}
\(\mathrm{B}^+\) 树插入与 B 树插入类似。首先找到应当包含该记录的叶结点 \(L\)。如果 \(L\) 未满，则加入新记录，其他 \(\mathrm{B}^+\) 树结点不受影响。如果 \(L\) 已满，则把它一分为二（把记录平分到两个结点），并提升新形成的右侧结点中最小键的一个副本。与 2-3 树一样，提升可能导致父结点接连分裂，或许最终导致根分裂，使 \(\mathrm{B}^+\) 树增加一层。 \(\mathrm{B}^+\) 树插入使所有叶结点保持相同深度。下面通过几个例子说明插入过程。
下面是 \(\mathrm{B}^+\) 树插入算法的类 Java 伪代码梗概。
private BPNode<Key,E> inserthelp(BPNode<Key,E> rt,
Key k, E e) {
BPNode<Key,E> retval;
if (rt.isLeaf()) { // At leaf node: insert here
return ((BPLeaf<Key,E>)rt).add(k, e);
}
// Add to internal node
int currec = binaryle(rt.keys(), rt.numrecs(), k);
BPNode<Key,E> temp = inserthelp(
((BPInternal<Key,E>)root).pointers(currec), k, e);
if (temp != ((BPInternal<Key,E>)rt).pointers(currec)) {
return ((BPInternal<Key,E>)rt).
add((BPInternal<Key,E>)temp);
}
else{
return rt;
}
}
这里有一个练习，用来检验你是否理解了 \(\mathrm{B}^+\) 树插入的基本思想。
要从 \(\mathrm{B}^+\) 树中删除记录 \(R\)，先定位包含 \(R\) 的叶结点 \(L\)。如果 \(L\) 的填充程度超过一半，那么只需移除 \(R\)， \(L\) 仍保持至少半满。下面的图演示了这种情况。
如果删除记录使结点中的记录数低于最小阈值（称为 下溢），就必须采取行动让结点保持足够的填充度。第一选择是查看该结点的相邻兄弟结点，判断它们是否有可以用来填补空缺的富余记录。如果有，就从兄弟结点转移足够的记录，使两个结点的记录数大致相同。这样做的目的是尽可能推迟下次删除再次使该结点下溢的时间。这个过程可能要求修改父结点的占位键值，以反映每个结点真实的第一个键值。
如果两个兄弟结点都无法借给下溢结点（记为 \(N\)）一条记录，那么 \(N\) 必须把它的记录交给一个兄弟结点，并从树中移除。空间肯定够，因为兄弟结点至多半满（记住，它刚才没有富余记录可以贡献），而 \(N\) 因为下溢已经不足半满。这一合并过程合并了父结点的两棵子树，可能反过来使父结点下溢。如果根的最后两个子结点合并在一起，树就少了一层。
下面是 \(\mathrm{B}^+\) 树删除算法的类 Java 伪代码。
/** Delete a record with the given key value, and
return true if the root underflows */
private boolean removehelp(BPNode<Key,E> rt, Key k) {
int currec = binaryle(rt.keys(), rt.numrecs(), k);
if (rt.isLeaf()) {
if (((BPLeaf<Key,E>)rt).keys()[currec] == k) {
return ((BPLeaf<Key,E>)rt).delete(currec);
}
else { return false; }
}
else{ // Process internal node
if (removehelp(((BPInternal<Key,E>)rt).pointers(currec),
k)) {
// Child will merge if necessary
return ((BPInternal<Key,E>)rt).underflow(currec);
}
else { return false; }
}
}
\(\mathrm{B}^+\) 树要求所有结点至少半满（根除外）。因此空间利用率至少是 50%。这对许多实现来说已经可以接受，但请注意，让结点更满既能减少所需空间（因为磁盘文件中的空余空间更少），又能带来更高的处理效率（平均读入内存的块更少，因为每块包含的信息量更大）。由于 B 树如此流行，许多算法设计者都尝试改进 B 树的性能。一种方法是使用称为 \(\mathrm{B}^*\) 树的 \(\mathrm{B}^+\) 树变体。 \(\mathrm{B}^*\) 树与 \(\mathrm{B}^+\) 树相同，只是分裂与合并结点的规则不同。结点溢出时，\(\mathrm{B}^*\) 树并不把它对半分裂，而是在可能的情况下把一些记录交给相邻的兄弟结点。如果兄弟结点也已满，则这两个结点分裂成三个。类似地，结点下溢时，它与两个兄弟结点合并，总量再缩减为两个结点。这样，结点始终保持至少三分之二满。[1]
最后，这里有一个构建五阶 B+ 树的例子。你可以把它与上面用相同记录构建四阶树的例子进行比较。
点击这里 是一个可视化，可以让你构建并与 \(\mathrm{B}^+\) 树交互。该可视化由旧金山大学的 David Galles 编写，是他的 数据结构可视化 套件的一部分。
12.6.1.2. B 树分析¶
在 B 树、\(\mathrm{B}^+\) 树和 \(\mathrm{B}^*\) 树中查找、插入、删除记录的渐近成本是 \(\Theta(\log n)\)，其中 \(n\) 是树中的记录总数。但对数的底是树的（平均）分支因子。典型的数据库应用使用极高的分支因子，也许 100 甚至更多。因此实践中 B 树及其变体极其浅。
举例说明：考虑一棵 100 阶的 \(\mathrm{B}^+\) 树，叶结点最多包含 100 条记录。高度为一的 B-\(\mathrm{B}^+\) 树（即只有一个叶结点）最多有 100 条记录。高度为二的 \(\mathrm{B}^+\) 树（一个根内部结点，其子结点是叶结点）必须至少有 100 条记录（2 个叶结点、每个 50 条记录）。它最多有 10,000 条记录（100 个叶结点、每个 100 条记录）。高度为三的 \(\mathrm{B}^+\) 树必须至少有 5000 条记录（两个第二层结点，各有 50 个子结点、每个含 50 条记录），至多有一百万条记录（100 个第二层结点、每个有 100 个全满的子结点）。高度为四的 \(\mathrm{B}^+\) 树必须至少有 250,000 条记录，至多有一亿条记录。因此，需要 极其 庞大的数据库才会产生高度超过四的 \(\mathrm{B}^+\) 树。
\(\mathrm{B}^+\) 树的分裂与插入规则保证每个结点 （根除外）至少半满。 所以它们平均约为四分之三满。 但内部结点是纯粹的空间开销，因为其中存储的键只被树用来 引导查找，并不存储实际数据。 这些空间开销是否构成显著的空间占用？ 不是。树结构的高扇出同样意味着结点中的绝大多数都是叶结点。 K 叉树 中内部结点约占 \(1/K\)。 这意味着，虽然满二叉树的结点有一半是内部结点， 但 100 阶 \(\mathrm{B}^+\) 树中内部结点可能只占约 \(1/75\)。 也就是说，与内部结点相关的空间开销非常低。
我们还可以用以下方法进一步减少 B 树所需的磁盘读取次数。第一，树的上面几层可以始终存放在内存中。由于树的分支增长极快，最上面两层（第 0 层和第 1 层）所需的空间相当少。如果 B 树只有四层高，那么到达任何给定记录的指针至多需要两次磁盘读取（第二层的内部结点和第三层的叶结点）。
可以用缓冲池来管理 B 树的结点。通常内存中会同时存在树的若干结点。最直接的做法是用 LRU 这类标准方法做结点替换。但有时最好把某些结点（比如根）"锁"在缓冲池里。一般而言，只要缓冲池有适度的规模（比如至少是树深的两倍），就不需要任何特殊的结点替换技术，因为上层的结点自然会被频繁访问。
