最近，我一直在阅读优秀的《数据库内部》（Alex Petrov，2019）一书。本书的前半部分致力于数据库存储引擎的实现——DBMS中处理数据长期持久化的子系统。令人惊讶的是，这部分内容大量讨论了各种B树数据结构的实现和优化。

在我大学的数据结构与算法课程中，我们学习过B树，但当时我并没有理解为什么要使用它。在课程的讲解中，B树本质上是“更好的”二叉搜索树，并且含糊地提到在数据库应用程序中使用它可以提高性能。我记得需要记住一堆公式来确定M阶B树的容量，以及对B树查找/插入/删除操作的模糊理解，但除此之外就没有更多了。

这真是太可惜了！它们很有趣的结构。

我认为这部分是因为可视化不够，部分原因是缺乏激励性的例子。在可视化方面：我见过的B树可视化大多将它们描绘成n叉树，通常是3-5阶。这并没有错，但它掩盖了使用B树的真正原因（例如，在一个节点中并置数百个键）。

另一个问题，即缺乏激励性例子，可以通过提供以下提示来解决：当一组键值对不再适合内存时，您如何设计一个对磁盘友好的结构来存储它们？

[免责声明]本文并非旨在成为B树的全面指南（我建议阅读《数据库内部》以获得类似的内容）。相反，这是我现在如何解释为什么像B树这样的数据结构有用的原因：

**磁盘引起的约束**

假设我们试图将大量键值对存储在磁盘上。我们希望有一种简单的方法来读取它们，并且我们还希望能够轻松地查询特定键或键的范围。一旦引入磁盘IO，我们就会遇到一些内存中结构中没有的约束：

* **约束：整个数据集无法放入内存。**

* **影响：**数据需要以这样的方式布局，使得可以通过仅将结构的一部分加载到内存中来遍历结构。

* **约束：与内存访问相比，可以读/写到驱动器的最小存储单元很大（通常是整个页面而不是单个字节）。**

* **影响：**尽可能地将可能一起访问的数据并置在一起。

* **约束：磁盘I/O明显慢于内存查找。**

* **影响：**尽可能减少磁盘访问次数。

那么，我们该如何开始呢？Petrov从一个说明性的例子开始。考虑一个简单的方法，我们将键值对存储在二叉搜索树（BST）中，并将该BST存储在磁盘上：

如果我们想要在磁盘上维护一个BST，我们将面临几个问题。其中一个问题是局部性：由于元素是按随机顺序添加的，因此无法保证新创建的节点写入的位置靠近其父节点，这意味着节点子指针可能跨越多个磁盘页面。由于二叉树的扇出只有两个，高度是树中元素数量的二进制对数，我们必须执行O(log2 N)次查找以定位要搜索的元素，然后执行相同数量的磁盘传输。简单的磁盘BST实现将需要与比较次数一样多的磁盘查找，因为没有内置的局部性概念。（第28-29页，我的重点）

作为磁盘结构的BST会失败，因为键比较次数大致等于磁盘查找次数。

请注意，这里有两个重要的量：键比较次数和磁盘查找次数。查找条目所需的键比较次数会随着数据集的大小而变化，因此我们无法做太多事情来影响它。但是，我们可以影响每次磁盘查找启用的键比较次数。如何？通过将键在磁盘布局中并置在一起。如果，比如说，我们将一堆键彼此相邻地存储在磁盘上，以便通过一次查找，我们可以执行大量的键比较？是的——这就是我们使用B树得到的结果。换句话说，B树具有高扇出。

这就是为什么将B树描绘成3叉到5叉树具有误导性：我们实际上可以每个节点存储数百个键，这只会增加每次查找的比较扇出益处。

**槽页**

到目前为止，一切都很好。但是，在更深入地了解B树时，关于如何在磁盘上布局键以最大程度地提高局部性和键压缩的实际细节让我更加欣赏这种方法。退一步，让我们从“CS常识”中回顾持久存储的一些基本知识：

* 硬盘驱动器（HDD）包含旋转磁盘，这些磁盘由静止磁头读取和写入。这使得随机访问比顺序访问慢，因为每次想要查看驱动器的不同部分时，都需要等到磁盘旋转，直到想要访问的部分位于磁头下方。

* 固态硬盘（SSD）由一堆存储单元构成，构成页面、块和窗格的层次结构。它们没有活动部件，但每个单元在其变得永久无法访问之前可以执行有限数量的读/写操作。因此，存在设备和操作系统级别的软件来跨驱动器分配操作，以延长驱动器的使用寿命。此外，SSD并不像我之前的心理模型那样“只是巨大的慢速RAM库”。相反：

可以写入（编程）或读取的最小单元是页面。但是，我们只能对空存储单元（即在写入之前已擦除的存储单元）进行更改。最小的擦除实体不是页面，而是一个包含多个页面的块，这就是为什么它通常被称为擦除块。空块中的页面必须顺序写入。（第30页）

所有这一切都是为了说明，HDD和SSD都对它们可以读/写的最小单元具有硬件约束。操作系统将其抽象为“块设备接口”。

为什么我们需要关心这个？我们创建的任何磁盘结构都应该知道它们更改的块（也称为页面）的数量。在1000个不同的块中更改1000个字节将比在同一个块中更改1000个字节慢得多。读取操作也是如此。因此，我们希望数据结构的逻辑布局与块设备抽象很好地配合。

B树自然适合以页面形式布局：每个逻辑树节点都获得一个磁盘页面。我们可以调整树的参数（主要是每个节点的键数），以便将节点舒适地固定在一个磁盘页面内。

但是，B树是动态的。由于任何插入或删除操作，树节点都可能发生变化，并且键必须在节点内保持排序顺序。如何在不进行大量数据移动的情况下按排序顺序布局数据？答案：槽页。

槽页由三个部分组成：页眉（包含有关页面的元数据）、单元（用于存储数据的可变大小“槽”）和偏移指针（指向这些单元的指针数组）。

这种布局的好处是您可以存储可变大小的数据，因为单元可以是可变大小的，并且您不需要移动该数据以逻辑地重新排序它。重新排序指针数组中指针的位置就足够了。这很便宜，因为指针很小，并且位于页面开头的一个已知位置。换句话说，只要偏移指针按键排序顺序排序，键存储在页面的哪个位置就无关紧要。

这意味着您还可以在删除/插入数据时释放和重用单元。例如，SQLite使用freelist管理此操作。

**B树查找**

我还想讨论一些其他的优化，但在这样做之前，讨论B树如何执行查找将很有帮助。B树查找算法非常简单。它通常被描述为类似于以下内容：

1. 从根节点开始。

2. 查看当前节点中的分隔符键，以查找逻辑上包含要查找的搜索键的子节点。

3. 使用步骤2中的逻辑递归遍历树。

4. 如果您遇到包含要搜索的键的叶节点，则完成。

5. 如果您发现搜索键不存在叶节点（例如，您正在查找的范围没有叶节点），或者叶节点不包含所需的键，则报告该键不存在，并且您已完成。

但是，步骤2忽略了一些有趣的细节——这些细节在存储更多数据的更高阶树中变得更加相关。首先：在大多数实现中，当遍历树时，您会在节点内的键上执行二分查找。这就是为什么在节点内按排序顺序存储键如此重要的原因。其次：除了实际存储数据的叶节点外，分隔符键的完整值并不重要——它只是充当节点之间的分区。只要分隔符键准确地表示每个子节点负责的键范围之间的分区，它就可以是任何具有该分区属性的值。使用实际数据库键之一作为分区键只是选择分区键的一种便捷方法。

**分隔符键截断**

利用上述见解，我们可以决定使用“更好”的分区键来提高B树的存储效率：

我们可以通过不存储整个键而是缩写它来节省页面空间。尤其是在树的内部页面中，键只需要提供足够的信息来充当键范围之间的边界。（设计数据密集型应用程序，Martin Kleppmann）

为了说明这一点，假设您试图存储以下键：

0xAAAAAA

0xBBBBBB

0xCCCCCC

0xDDDDDD

0xEEEEEE

0xFFFFFF

… 并且我们的插入算法已决定将这些键存储在两个树节点中：

# 节点1

0xAAAAAA

0xBBBBBB

0xCCCCCC

# 节点2

0xDDDDDD

0xEEEEEE

0xFFFFFF

节点1和节点2的父节点应该使用什么作为它们之间的分隔符键？简单的实现将使用0xDDDDDD。小于0xDDDDDD的所有内容都在节点1中，大于或等于0xDDDDDD的所有内容都在节点2中。但是，请注意，0xCCCCCC和0xDDDDDD之间存在很大的差距。我们可以使用更不细粒度的分隔符，并且仍然保持正确的分区。例如，如果我们将前缀“键”0xD*作为分隔符存储，则这告诉我们同样多的信息，但需要存储的字节更少。

回想一下，键长度可以（有效地）无限，因此此技术可以在病态情况下节省大量空间。这又是可视化的失败：大多数图表（为简单起见）显示较小的键——选择单个数字或字符。但是，在真实的数据库系统中，键可能非平凡地大——SQLite的默认最大键大小为1MB。

**溢出页**

使用分隔符键截断，我们能够通过截断键将更多键打包到内部（非叶）节点中。有时，我们可能会在叶节点中遇到相反的问题：我们的（物理）页面太小，无法容纳我们应该在（逻辑）节点中拥有的键数。

在这种情况下，一些B树实现转向溢出页。存储引擎为溢出数据分配一个新页面，并更新第一个页面的页眉以指示溢出。我的最初直觉是，您只需在溢出页面中分配额外的单元，并将整个内容视为“更多单元空间”。但是，您可以通过使用分隔符键截断的相同见解变得更聪明一些：大多数数据库操作都在键范围内，因此快速访问键前缀可能比访问整个键更重要。

因此，实际上拆分键可能效率更高——将前缀存储在原始页面中，并将其余部分溢出到溢出页面：

# 非常长的键：

AAABBBCCCDDDEEEFFFGGGHHH

| 存储在主页面中 | 存储在溢出页面中 |

----------------------------------------------------

| AAABBBCC | CDDDEEEFFFGGGHHH |

这样，如果我们正在检查键是否存在或执行范围查询，则更有可能不需要查询溢出页面——因为在许多情况下，键前缀足以回答查询。

**兄弟指针**

我认为什么特别有趣的最后一个优化是簿记的额外一点：

* 一些实现存储前向和后向链接，分别指向左侧和右侧兄弟页面。这些链接有助于定位相邻节点，而无需返回到父节点。（数据库内部，第62页）

这些兄弟指针使范围查询的性能更高：

* 在范围扫描期间，迭代从找到的最接近的键值对开始，并通过跟随兄弟指针继续，直到范围结束或范围谓词用尽。（第38页）

首先：在每个级别上，兄弟节点始终具有不重叠的严格递增的键范围。这意味着遍历到节点的右侧兄弟节点保证（在该级别）包含键空间的逻辑“下一个”块。其次：在更深的树中，拥有兄弟指针可能意味着避免可能多次“反向遍历”返回父节点。

为了证明这一点，请考虑以下图表（使用二叉树，为简单起见）。每个节点的第一行表示存储在节点中的键，第二行表示该节点中可以存在的有效键：

从K8移动到K9只需一个兄弟指针，而不是六次跳跃遍历树的上部和下部。因此，当查询一系列值时，额外的兄弟指针簿记可以避免许多不必要的回溯。

**B树变体**

最后：除了我一直在讨论的主要内容B⁺树之外，B树还有一些变体和优化，可以在某些情况下提供优化：“延迟B树”，如WiredTiger和Lazy-Adaptive Tree可以通过缓冲写入来提高性能。FD树以对SSD的物理特性更友好的方式构建B树数据。Bw树（有趣的是，“Buzzword trees”）为高并发和内存中的树访问提供了进一步的优化。

**结论**

如果其中任何一个让你觉得有趣，我再次强烈建议通读《数据库内部》。

我认为我最大的收获是，数据结构作为一个抽象的数学概念（“B⁺树”）和具体的实现（“SQLite的数据库格式”）之间存在显着差异。对具体实现的优化不会提高数据结构的BigO特性，但会对数据库的性能和可用性产生重大的“现实世界”影响。

此外，所有这些都仅仅开始了一个关于特定存储系统更细粒度优化的更长讨论。正如我从Raft中了解到的那样，魔鬼在于细节。“需要一些额外的簿记”是对令人抓狂的错误和非平凡复杂性的现成邀请。

最后一点：由于我一直在抱怨树的可视化，我确实找到了一张我认为可以更好地理解实践中树结构的B树图。这来自Martin Kleppman的《设计数据密集型应用程序》：

这种方法非常类似于内存分配器。

B⁺树仅在叶节点中存储数据。其他B树变体可以在内部节点中存储数据（例如，与键关联的值）。

来源