B-树

外部内存概述

在 w 位字长的随机访问内存（word-RAM）模型中，隐含假设是计算机拥有足够大的随机访问内存来存储数据结构中的所有数据。但在某些情况下，这一假设并不成立。存在一些数据集合大到没有任何计算机能够将其全部存储在内存中。在这种情况下，应用程序必须将数据存储在外部存储介质上，例如硬盘、固态硬盘，甚至网络文件服务器（其本身也具备外部存储能力）。

从外部存储访问一个数据项的速度极其缓慢。本文所用计算机连接的硬盘平均访问时间为 19 毫秒，而连接的固态硬盘平均访问时间为 0.3 毫秒。相比之下，计算机的随机访问内存平均访问时间小于 0.000113 毫秒。访问 RAM 的速度比访问固态硬盘快超过 2,500 倍，比访问硬盘快超过 160,000 倍。

这些速度差异具有代表性：从 RAM 中随机访问一个字节的速度比从硬盘或固态硬盘中随机访问一个字节快数千倍。然而，访问时间并不能完全说明问题。当我们从硬盘或固态硬盘中访问一个字节时，整个磁盘块都会被读取。计算机所连接的每种驱动器的块大小均为 4,096 字节；每次读取一个字节时，驱动器会返回包含 4,096 个字节的一个完整块。如果我们合理组织数据结构，这意味着每次磁盘访问可以获取 4,096 字节的数据，这些数据对完成当前操作非常有用。

在外部内存模型中，访问外部内存中的某个元素 $x$ 需要将包含 $x$ 的整个块读入内存。

这就是外部内存计算模型的核心思想，如上图所示。在此模型中，计算机可以访问一个大型外部内存，其中存放了所有数据。该内存被划分为多个内存块，每个块包含 $B$ 个字。计算机还拥有有限的内部内存，用于执行计算。在内部内存与外部内存之间传输一个块所需的时间是常数。在内部内存中进行的计算是免费的，不消耗任何时间。虽然内部内存计算免费这一点看似奇怪，但它强调了外部内存相对于 RAM 的巨大性能差距。

在完整的外部内存模型中，内部内存的大小也是一个参数。但对于基于块的数据结构而言，只需拥有大小为 $O(B + \log_B n)$ 的内部内存即可。也就是说，内存需要能够存储常数量的块以及高度为 $O(\log_B n)$ 的递归栈。在大多数情况下，$O(B)$ 项主导了内存需求。例如，即使使用相对较小的 $B = 32$，对于所有 $n \leq 2^{160}$，都有 $B \geq \log_B n$。以十进制表示，当

$$n \leq 1 461 501 637 330 902 918 203 684 832 716 283 019 655 932 542 976$$

时，也有 $B \geq \log_B n$。

块存储

外部内存的概念涵盖了大量不同类型的设备，每种设备都有自己特定的块大小，并通过不同的系统调用进行访问。为了简化阐述，使我们能专注于共性思想，我们引入一个名为 BlockStore 的对象来封装外部内存设备。BlockStore 存储一组大小为 B 的内存块。每个块由唯一的整数索引标识。BlockStore 支持以下操作：

• readBlock(i)：返回索引为 i 的块的内容。
• writeBlock(i, b)：将内容 b 写入索引为 i 的块。
• placeBlock(b)：返回一个新的索引，并将 b 的内容存储在该索引处。
• freeBlock(i)：释放索引为 i 的块。这表示该块的内容不再使用，因此该块所占用的外部内存可被重新利用。

最直观的理解方式是将 BlockStore 想象成将一个文件存储在磁盘上，并按块划分，每个块包含 $B$ 字节。在这种方式下，readBlock(i) 和 writeBlock(i, b) 分别读写该文件的第 $iB$ 到 $(i+1)B - 1$ 字节。此外，一个简单的 BlockStore 可以维护一个可用块的空闲列表。通过 freeBlock(i) 释放的块会被加入空闲列表。因此，placeBlock(b) 可以从空闲列表中选取一个块，或者如果无可用块，则在文件末尾追加一个新块。

在本模块中，我们将讨论一种广义的二叉树结构——B 树，它在外部内存模型中非常高效。另外，B 树也可以看作是 2-4 树的自然推广。（2-4 树是 B 树的一个特例，当设置 $B = 2$ 时即可得到。）

B 树的结构

对于任意整数 $B \geq 2$，B 树是一种所有叶子节点深度相同的树，且每个非根内部节点 u 至少有 $B$ 个子节点，最多有 $2B$ 个子节点。u 的子节点存储在一个数组 u.children 中。根节点的子节点数量要求较为宽松，可以有 2 到 $2B$ 个子节点。

如果 B 树的高度为 $h$，则其叶子节点数量 $l$ 满足：

$$2B^{h−1} \leq l \leq 2(2B)^{h−1}$$

对第一个不等式取对数并整理得：

$$\begin{split} h & \leq \frac{\log l − 1}{\log B}+1 \\ & \leq \frac{\log l}{\log B}+1 \\ & = \log_B l+1 \end{split}$$

即，B 树的高度与叶子节点数量的以 $B$ 为底的对数成正比。

B 树中的每个节点 u 存储一个键数组 u.keys[0], ..., u.keys[2B−1]。如果 u 是一个有 k 个子节点的内部节点，则 u 中存储的键的数量恰好为 $k−1$，并存放在 u.keys[0], ..., u.keys[k−2] 中。其余 $2B − k + 1$ 个数组位置设为 null。如果 u 是非根的叶子节点，则其包含的键数量在 $B−1$ 到 $2B−1$ 之间。B 树中的键遵循类似于二叉搜索树的顺序关系。对于存储 $k−1$ 个键的任意节点 u，

$$\text{u.keys}[0] < \text{u.keys}[1] < \cdots < \text{u.keys}[k − 2]$$

如果 u 是内部节点，则对每个 $i \in \{0, ..., k − 2\}$，u.keys[i] 大于存储在以 u.children[i] 为根的子树中的所有键，但小于存储在以 u.children[i + 1] 为根的子树中的所有键。非正式地表达为：

$$\text{u.children}[i] \prec \text{u.keys}[i] \prec \text{u.children}[i + 1]$$

B 树的可视化演示

下图展示了一个 $B = 2$ 的 B 树示例：

注意，B 树节点中存储的数据大小为 $O(B)$。因此，在外部内存环境中，B 树中的 $B$ 值被选择为使得一个节点恰好能放入一个外部内存块中。这样，B 树操作在外部内存模型中的执行时间就与操作所访问（读取或写入）的节点数量成正比。

例如，若键为 4 字节整数，节点索引也为 4 字节，则设置 $B = 256$ 意味着每个节点存储：

$$(4 + 4) \times 2B = 8 \times 512 = 4096$$

字节的数据。这个 $B$ 值正好适用于硬盘或固态硬盘，因为它们的块大小也是 4096 字节。

BTree 类实现了 B 树，它包含一个 BlockStore bs，用于存储 BTree 节点，以及根节点的索引 ri。像往常一样，用一个整数 n 来记录数据结构中元素的总数：

1class BTree(BaseSet):
2    class Node(object):
3        def __init__(self, btree):
4            self.btree = btree
5            self.keys = new_array(self.btree.b)
6            self.children = new_int_array(self.btree.b+1, -1)
7            self.id = self.btree.bs.place_block(self)
8    
9    def __init__(self, b):
10        self._initialize(b)
11        
12    def _initialize(self, b):
13        self.b = b | 1
14        self.B = self.b // 2
15        self.bs = BlockStore()
16        self.ri = self.new_node().id
17        self.n = 0