B树：比我想象中更想了解的知识
最近，我在阅读那本非常棒的《数据库内部原理》（作者：Alex Petrov, 2019年）。这本书的前半部分专注于数据库存储引擎的实现——这是数据库管理系统（DBMS）中负责数据长期保存的部分。令人惊讶的是，这部分内容大量讨论了各种B树数据结构的实现和优化。
在我的大学数据结构与算法课程中，我们确实学过B树，但我当时并没有真正理解为什么我会选择使用它。按照当时的讲解，B树基本上是“更好”的二叉搜索树，在数据库应用中性能有所提升。我记得需要记住一堆公式来计算M阶B树的容量，并对B树的查找、插入和删除有一个模糊的理解，但仅此而已。这真是可惜！它们其实是非常有趣的结构。
我认为这种理解上的不足部分是因为缺乏可视化手段，部分是因为没有提供足够的动机示例。关于可视化：大多数我见过的B树可视化都把它们描绘成n叉树，通常为3到5阶。这并没有错，但它掩盖了你实际使用B树的原因（例如，部分原因是可以在单个节点中放置数百个键）。
提供动机示例
另一个问题是缺乏动机示例。这个问题可以通过提出以下问题来解决：当一组键值对不再适合内存时，你想设计一种磁盘友好的结构来存储它们，你会怎么做？
注意：这篇文章并不是要全面介绍B树（我推荐《数据库内部原理》这本书来深入学习）。相反，这里是我现在会如何解释像B树这样的数据结构为何有用：
磁盘带来的约束
假设我们要在磁盘上存储大量的键值对。我们希望有一种简单的方法将它们读回，并且能够轻松查询特定的键或键范围。一旦引入磁盘I/O操作，我们会遇到一些不同于内存结构的约束：
-
约束：整个数据集无法全部放入内存。
- 影响：数据需要以某种方式布局，使得遍历结构只需要加载结构的一部分到内存中。
-
约束：从驱动器读取或写入的最小存储单位比内存访问大得多（通常是整个页面而不是单个字节）。
- 影响：尽量将可能一起访问的数据放在一起。
-
约束：磁盘I/O比内存查找慢得多。
- 影响：尽量减少磁盘访问次数。
为什么B树有用？
如果我们想要在磁盘上维护一个二叉搜索树（BST），我们会面临几个问题。其中一个问题是局部性：由于元素是以随机顺序添加的，新创建的节点不一定写在靠近其父节点的位置，这意味着子节点指针可能会跨越多个磁盘页面。
由于二叉树的分支因子仅为2，树的高度是对数级别的，我们需要进行O(log₂N)次查找才能定位到所需的元素，然后执行相同数量的磁盘传输。
一个简单的磁盘BST实现每次查找都需要进行一次磁盘查找，因为没有内置的局部性概念。
BST作为磁盘上的结构表现不佳，因为键比较的次数大致等于磁盘查找的次数。
这里有两个重要的量：键比较的次数和磁盘查找的次数。键比较的次数随着数据集的大小而增加，所以我们对此无能为力。然而，我们可以影响每次磁盘查找所能进行的键比较次数。怎么做呢？通过在磁盘布局中将键放在一起。如果我们将许多键相邻存储在一个页面中，那么一次查找就可以进行大量的键比较。这就是B树的作用。换句话说，B树具有较高的分支因子。
这就是为什么将B树描绘成3到5阶的树是误导性的：实际上我们可以每个节点存储数百个键，这进一步增加了每次查找的键比较收益。
分页技术
到目前为止，一切顺利。然而，当我们深入了解B树时，关于如何在磁盘上布局键以最大化局部性和键压缩的细节让我更加欣赏这种方法。让我们回顾一下“计算机科学常识”中关于持久存储的一些基础知识：
-
硬盘驱动器（HDD） 包含旋转的磁盘，由静态磁头读取和写入。这使得随机访问比顺序访问慢，因为每次你想查看驱动器的不同部分时，都需要等待磁盘旋转到所需部分位于磁头下方。
-
固态硬盘（SSD） 由许多内存单元组成，形成层次结构的页面、块和面板。它们没有移动部件，但每个单元只能进行有限次数的读写操作后就会永久失效。因此，设备和操作系统层面的软件会分配操作以延长驱动器的使用寿命。此外，SSD不仅仅是“较慢的大容量RAM”，就像我之前的思维模型一样。事实上：
- 可以写入或读取的最小单位是页面。但是，我们只能更改空闲的内存单元（即在写入之前已被擦除的单元）。最小的擦除实体不是页面，而是包含多个页面的块，这就是为什么它通常被称为擦除块。空块中的页面必须按顺序写入。
所有这些都表明，无论是HDD还是SSD，都有硬件限制，决定了它们可以读写的最小单位。操作系统将这些抽象为“块设备接口”。为什么我们需要关心
