B-Tree

在《AlgoDS-Notes》一节中我们介绍了 B-Tree 的基本概念与实现，这里我们继续来分析下为何 B-Tree 相较于红黑树等二叉查找树会更适合于作为数据库索引的实现。一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘 IO 消耗，相对于内存存取，IO 存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘 IO 操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘 IO 的存取次数。

根据 B-Tree 的定义，可知检索一次最多需要访问 h 个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次 IO 就可以完全载入。每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次 IO。而检索的时候，一次检索最多需要 h-1 次 IO（根节点常驻内存），其渐进复杂度为 $O(h)=O(log_dN)O(h)=O(log_dN)$，实际应用中，出度 d 是非常大的数字，通常超过 100，因此 h 非常小（通常不超过 3）。而红黑树这种结构，h 明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的 IO 渐进复杂度也为 O(h)，效率明显比 B-Tree 差很多。

B+Tree

B+Tree 是 B-Tree 的变种，有着比 B-Tree 更高的查询性能，其相较于 B-Tree 有了如下的变化：

• 有 m 个子树的节点包含有 m 个元素（B-Tree 中是 m-1）。
• 根节点和分支节点中不保存数据，只用于索引，所有数据都保存在叶子节点中。
• 所有分支节点和根节点都同时存在于子节点中，在子节点元素中是最大或者最小的元素。
• 叶子节点会包含所有的关键字，以及指向数据记录的指针，并且叶子节点本身是根据关键字的大小从小到大顺序链接。

一般在数据库系统或文件系统中使用的 B+Tree 结构都在经典 B+Tree 的基础上进行了优化，增加了顺序访问指针：

如上图所示，在 B+Tree 的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的 B+Tree。做这个优化的目的是为了提高区间访问的性能，例如下图中如果要查询 key 为从 3 到 8 的所有数据记录，当找到 3 后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

B+ 树

刚才讨论的日志结构索引正处在逐渐被接受的阶段，但它们并不是最常见的索引类型。使用最广泛的索引结构在 1970 年被引入，不到 10 年后变得“无处不在”，B 树经受了时间的考验。在几乎所有的关系数据库中，它们仍然是标准的索引实现，许多非关系数据库也使用它们。

像 SSTables 一样，B 树保持按键排序的键值对，这允许高效的键值查找和范围查询。但这就是相似之处的结尾：B 树有着非常不同的设计理念。我们前面看到的日志结构索引将数据库分解为可变大小的段，通常是几兆字节或更大的大小，并且总是按顺序编写段。相比之下，B 树将数据库分解成固定大小的块或页面，传统上大小为 4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为磁盘也被安排在固定大小的块中。

每个页面都可以使用地址或位置来标识，这允许一个页面引用另一个页面：类似于指针，但在磁盘而不是在内存中。我们可以使用这些页面引用来构建一个页面树：

一个页面会被指定为 B 树的根；在索引中查找一个键时，就从这里开始。该页面包含几个键和对子页面的引用。每个子页面负责一段连续范围的键，引用之间的键，指明了引用子页面的键范围。譬如在上例中，我们正在寻找关键字 251，所以我们知道我们需要遵循边界 200 和 300 之间的页面引用。这将我们带到一个类似的页面，进一步打破了 200 - 300 到子范围。最后，我们可以看到包含单个键（叶页）的页面，该页面包含每个键的内联值，或者包含对可以找到值的页面的引用。

在 B 树的一个页面中对子页面的引用的数量称为分支因子。例如上例中分支因子是 6。在实践中，分支因子取决于存储页面参考和范围边界所需的空间量，但通常是几百个。如果要更新 B 树中现有键的值，则搜索包含该键的叶页，更改该页中的值，并将该页写回到磁盘（对该页的任何引用保持有效）。如果你想添加一个新的键，你需要找到其范围包含新键的页面，并将其添加到该页面。如果页面中没有足够的可用空间容纳新键，则将其分成两个半满页面，并更新父页面以解释键范围的新分区，如下图所示：

该算法确保树保持平衡：具有 n 个键的 B 树总是具有 $O(log n)$ 的深度。大多数数据库可以放入一个三到四层的 B 树，所以你不需要遵追踪多页面引用来找到你正在查找的页面，这里分支因子为 500 的 4KB 页面的四级树可以存储多达 256TB。

日志

B 树的基本底层写操作是用新数据覆盖磁盘上的页面。假定覆盖不改变页面的位置;即，当页面被覆盖时，对该页面的所有引用保持完整。这与日志结构索引（如 LSM 树）形成鲜明对比，后者只附加到文件（并最终删除过时的文件），但从不修改文件。

您可以考虑将硬盘上的页面覆盖为实际的硬件操作。在磁性硬盘驱动器上，这意味着将磁头移动到正确的位置，等待旋转盘上的正确位置出现，然后用新的数据覆盖适当的扇区。在固态硬盘上，由于 SSD 必须一次擦除和重写相当大的存储芯片块，所以会发生更复杂的事情。

而且，一些操作需要覆盖几个不同的页面。例如，如果因为插入导致页面过度而拆分页面，则需要编写已拆分的两个页面，并覆盖其父页面以更新对两个子页面的引用。这是一个危险的操作，因为如果数据库在仅有一些页面被写入后崩溃，那么最终将导致一个损坏的索引（例如，可能有一个孤儿页面不是任何父项的子项）。

为了使数据库对崩溃具有韧性，B 树实现通常会带有一个额外的磁盘数据结构：预写式日志（WAL, write-ahead-log）（也称为重做日志（Redo Log））。这是一个仅追加的文件，每个 B 树修改都可以应用到树本身的页面上。当数据库在崩溃后恢复时，这个日志被用来使 B 树恢复到一致的状态。

更新页面的一个额外的复杂情况是，如果多个线程要同时访问 B 树，则需要仔细的并发控制：否则线程可能会看到树处于不一致的状态。这通常通过使用锁存器（latches）（轻量级锁）保护树的数据结构来完成。日志结构化的方法在这方面更简单，因为它们在后台进行所有的合并，而不会干扰传入的查询，并且不时地将旧的分段原子交换为新的分段。

B 树优化

由于 B 树已经存在了这么久，许多优化已经发展了多年，这并不奇怪。仅举几例：

• 一些数据库（如 LMDB）使用写时复制方案，而不是覆盖页面并维护 WAL 进行崩溃恢复。修改的页面被写入到不同的位置，并且树中的父页面的新版本被创建，指向新的位置。这种方法对于并发控制也很有用。
• 我们可以通过不存储整个键来节省页面空间，但可以缩小它的大小。特别是在树内部的页面上，键只需要提供足够的信息来充当键范围之间的边界。在页面中包含更多的键允许树具有更高的分支因子，因此更少的层次
• 通常，页面可以放置在磁盘上的任何位置；没有什么要求附近的键范围页面附近的磁盘上。如果查询需要按照排序顺序扫描大部分关键字范围，那么每个页面的布局可能会非常不方便，因为每个读取的页面都可能需要磁盘查找。因此，许多 B 树实现尝试布局树，使得叶子页面按顺序出现在磁盘上。但是，随着树的增长，维持这个顺序是很困难的。相比之下，由于 LSM 树在合并过程中一次又一次地重写存储的大部分，所以它们更容易使顺序键在磁盘上彼此靠近。
• 额外的指针已添加到树中。例如，每个叶子页面可以在左边和右边具有对其兄弟页面的引用，这允许不跳回父页面就能顺序扫描。
• B 树的变体如分形树借用一些日志结构的思想来减少磁盘寻道（而且它们与分形无关）。

B+ 树与 LSM 树的比较

尽管 B 树实现通常比 LSM 树实现更成熟，但 LSM 树由于其性能特点也非常有趣。根据经验，通常 LSM 树的写入速度更快，而 B 树的读取速度更快 LSM 树上的读取通常比较慢，因为它们必须在压缩的不同阶段检查几个不同的数据结构和 SSTables。

LSM 树的优点

B 树索引必须至少两次写入每一段数据：一次写入预先写入日志，一次写入树页面本身（也许再次分页）。即使在该页面中只有几个字节发生了变化，也需要一次编写整个页面的开销。有些存储引擎甚至会覆盖同一个页面两次，以免在电源故障的情况下导致页面部分更新。

由于反复压缩和合并 SSTables，日志结构索引也会重写数据。这种影响：在数据库的生命周期中写入数据库导致对磁盘的多次写入：被称为写放大（write amplification）。需要特别注意的是固态硬盘，固态硬盘的闪存寿命在覆写有限次数后就会耗尽。在写入繁重的应用程序中，性能瓶颈可能是数据库可以写入磁盘的速度。在这种情况下，写放大会导致直接的性能代价：存储引擎写入磁盘的次数越多，可用磁盘带宽内的每秒写入次数越少。

而且，LSM 树通常能够比 B 树支持更高的写入吞吐量，部分原因是它们有时具有较低的写放大（尽管这取决于存储引擎配置和工作负载），部分是因为它们顺序地写入紧凑的 SSTable 文件而不是必须覆盖树中的几个页面。这种差异在磁性硬盘驱动器上尤其重要，顺序写入比随机写入快得多。

LSM 树可以被压缩得更好，因此经常比 B 树在磁盘上产生更小的文件 B 树存储引擎会由于分割而留下一些未使用的磁盘空间：当页面被拆分或某行不能放入现有页面时，页面中的某些空间仍未被使用。由于 LSM 树不是面向页面的，并且定期重写 SSTables 以去除碎片，所以它们具有较低的存储开销，特别是当使用平坦压缩时。

在许多固态硬盘上，固件内部使用日志结构化算法，将随机写入转变为顺序写入底层存储芯片，因此存储引擎写入模式的影响不太明显。但是，较低的写入放大率和减少的碎片对 SSD 仍然有利：更紧凑地表示数据可在可用的 I/O 带宽内提供更多的读取和写入请求。

LSM 树的缺点

日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作。尽管存储引擎尝试逐步执行压缩而不影响并发访问，但是磁盘资源有限，所以很容易发生请求需要等待而磁盘完成昂贵的压缩操作。对吞吐量和平均响应时间的影响通常很小，但是在更高百分比的情况下，对日志结构化存储引擎的查询响应时间有时会相当长，而 B 树的行为则相对更具可预测性。

压缩的另一个问题出现在高写入吞吐量：磁盘的有限写入带宽需要在初始写入（记录和刷新内存表到磁盘）和在后台运行的压缩线程之间共享。写入空数据库时，可以使用全磁盘带宽进行初始写入，但数据库越大，压缩所需的磁盘带宽就越多。

如果写入吞吐量很高，并且压缩没有仔细配置，压缩跟不上写入速率。在这种情况下，磁盘上未合并段的数量不断增加，直到磁盘空间用完，读取速度也会减慢，因为它们需要检查更多段文件。通常情况下，即使压缩无法跟上，基于 SSTable 的存储引擎也不会限制传入写入的速率，所以您需要进行明确的监控来检测这种情况。

B 树的一个优点是每个键只存在于索引中的一个位置，而日志结构化的存储引擎可能在不同的段中有相同键的多个副本。这个方面使得 B 树在想要提供强大的事务语义的数据库中很有吸引力：在许多关系数据库中，事务隔离是通过在键范围上使用锁来实现的，在 B 树索引中，这些锁可以直接连接到树。在第 7 章中，我们将更详细地讨论这一点。

B 树在数据库体系结构中是非常根深蒂固的，为许多工作负载提供始终如一的良好性能，所以它们不可能很快就会消失。在新的数据存储中，日志结构化索引变得越来越流行。没有快速和容易的规则来确定哪种类型的存储引擎对你的场景更好，所以值得进行一些经验上的测试