数据库中的 B 树与 B+ 树
参考资料：
1. 主要内容
B 树与 B+ 树是一类非常重要的数据结构，它们被广泛应用于各种数据库中。为了更好地理解这类数据结构，我们将逐一讨论以下内容：
- 磁盘结构
- 数据是如何存储在磁盘上的
- 什么是索引
- 什么是多级索引
- 多路查找树
- B 树
- B 树中的插入与删除
- B+ 树
2. 磁盘结构
我们来看一下 磁盘 (disk) 的结构：一个典型的磁盘驱动器由一个或多个 盘片 (platter) 组成，它们以一个固定的速度围绕一个共同的 主轴 (spindle) 旋转。每个盘片表面覆盖着一层可磁化的物质。驱动器通过 磁臂 (arm) 末尾的 磁头 (head) 来读/写盘片。
盘片在 逻辑上 (而非物理上) 被划分为一系列的同心环状区域，数据就存储在这样的同心圆环上面，这些同心圆环被称为 磁道 (track)。每个盘面可以划分多个磁道，最外圈的磁道是 0 号磁道，向圆心增长依次为 1 号磁道、2 号磁道……磁盘的数据存放就是从最外圈开始的。
根据硬盘的规格不同，磁道数可以从几百到成千上万不等。每个磁道可以存储几个 Kb 的数据，但是计算机不必要每次都读写这么多数据。因此，再把每个磁道划分为若干个弧段，每个弧段就是一个 扇区 (sector)。
一个盘片被划分为许多磁道和扇区，一个磁道和一个扇区相交的区域称为一个 块 (block)。因此，磁盘上的任意一个块都可以通过其对应的磁道编号和扇区编号来寻址，也就是说，磁盘上的块地址格式由磁道编号和扇区编号组成：
块是硬盘上存储的物理单位。出于稳定性考虑，通常一个块存储 512 字节的数据，但是实际上其容量可以是任意大小，具体取决于磁盘制造商和磁盘型号。
这里，我们假设每个块的容量为 512 字节。当我们从磁盘上读取或写入数据时，我们总是以块为单位进行读/写。如果现在我们读取一个 512 字节的块，假设其中第一个字节的地址为 0，最后一个字节的地址为 511，那么其中每个字节都有其各自的地址，我们称之为 偏移量 (offset)。
假设磁盘上的每个块的第一个和最后一个字节的偏移量都分别为 0 和 511。因此，我们只需要知道 磁道编号、扇区编号 和 偏移量 这三个信息就可以定位到磁盘上的任意一个字节：首先，利用磁道编号和扇区编号定位到该字节所在的块；然后，在块内通过偏移量定位到该字节。
正常情况下，我们可以通过盘片的旋转来选择扇区，通过磁头的轴向移动来选择磁道，也就是说，我们可以通过旋转盘片和移动磁头来定位到某个块，而数据总是以块的形式存储在磁盘上的。
现在，让我们来看一下内存，或者说 RAM (注：RAM 是一种存储技术，其类型为主存)，我们所有的程序都运行在内存中。假设我们的程序需要访问磁盘上的数据，我们需要将这些数据从磁盘上读取到内存中，然后我们的程序才能对其进行访问，而一旦我们的程序得到了某些结果，我们再将这些结果写入到磁盘。所以，数据处理无法直接在磁盘上进行，数据需要被读入内存中然后才能被程序访问。
内存中的数据可以被程序直接访问，我们将其称为 数据结构 (data structure)。而在磁盘上高效组织数据使得其能够以一种简单方式被利用的系统被称为 数据库管理系统 (DBMS)。
3. 数据是如何存储在磁盘上的
现在，我们来看一下磁盘上的数据是如何以数据库的形式被组织起来的。
例子：这里我们有一个数据库表，其中包含一些 列 (columns) 和 行 (rows)，假设这里我们有 100 行数据。表的结构如左图所示，一共有 5 列属性，总的大小为 128 字节，即表中的每一行大小为 128 字节。
现在我们希望将该表存储在磁盘上，每个块中可以存储的记录条数为：
\[\text{number of records/block} = \dfrac{512}{128}=4\]那么存储总共 100 条记录需要的块的数量为：
\[\text{number of blocks for database table} = \dfrac{100}{4}=25\]所以，在磁盘上存储该数据库表总共需要 25 个块。
现在，假设我们已经将该数据库表存储在了磁盘上的 25 个块中。想象一下，现在我们希望写一条查询语句来查询其中某条特定记录，所需要的搜索次数是多少？因为所查询的记录可能在表中的任意位置，所以我们可能需要搜索整个数据库表，总共需要访问磁盘上最多 25 个块。我们当然可以一个块一个块地逐一访问并检查其中是否包含所查询的记录，但这样可能需要访问多达 25 个块。
4. 索引
我们可以缩减这种查询的时间开销吗？
答案是可以。现在我们将为该数据库表构建 索引 (index)。在索引中，我们将存储一个 键 (key)，即员工 id，以及一个指向相应记录的 指针 (pointer)。因此，对于磁盘上的块中的每条记录，我们都有一个指向该记录的指针，我们称之为 记录指针 (record pointer)。每条记录在索引中都有一个对应的 条目 (entry)，我们将这种索引称为 密集索引 (tense index)。
那么，索引存储在哪里呢？
同样，我们将索引也存储在磁盘上。我们假设每个 id 大小为 10 个字节，每个指针大小为 6 个字节，因此索引中的每个条目大小为 16 字节。所以，每个块可存储的索引条目数量为：
\[\text{number of entries/block} = \dfrac{512}{16}=32\]那么，存储 100 条记录的索引所需要的块的数量为：
\[\text{number of blocks for index} = \dfrac{100}{32}=3.125\]所以我们总共需要 4 个块来存储这 100 条记录的索引。
现在，当我们需要搜索任意一条记录时，我们可以直接在索引中搜索，因此查找该记录对应的索引条目最多需要访问 4 个块。当我们在索引中找到该记录的 key 后，我们就可以直接访问其记录所在的块。所以，现在查询任意一条记录最多需要访问 4 个索引块加上 1 个数据库表块，总共只需要访问 5 个块。这就是构建索引的好处。
5. 多级索引
现在，假设我们的记录不是 100 条，而是 1000 条，这意味着数据库表的存储需要 250 个块，而相应地，索引存储需要 32 个块。这样一来，索引内的搜索开销也就大大增加了。
那么，我们可以在索引之上再构建一层索引吗？
答案是可以。我们应该如何构建二级索引的条目呢？仍然和之前一样为一级索引的每一个条目构建一条索引吗？并不是，我们知道对于一级索引，每个块可以存储 32 个条目，所以我们可以每隔 32 条记录构建一个二级索引条目，我们将这种索引称为 稀疏索引 (sparse index)。
我们知道索引中的每个条目大小为 16 字节，每个块可存储的索引条目数量为 32。而二级索引一共的条目数量为：
\[\text{number of entries for 2nd index} = \dfrac{1000}{32}=31.25\]所以，二级索引的条目数量为 32，存储所需的块数量为：
\[\text{number of blocks for 2nd index} = \dfrac{32}{32}=1\]所以，二级索引的存储只需要 1 个块。
因此，整个数据库表存储需要 250 个块，一级索引存储需要 32 个块，二级索引存储仅需 1 个块。所以现在查询任意一条记录总共需要访问 1 个二级索引块，加上 1 个一级索引块，加上一个数据库表存储块，总共只需要访问 3 个块。所以，通过增加一级索引，我们大大减少了块访问的次数，这也是 B 树和 B+ 树的基本思想起源。
假设我们的数据量很大，我们需要构建多级索引以减少磁盘上的块访问次数：
我们可以将上面的结构旋转一下会发现其类似树形结构：
那么，多级索引的要求是什么呢？我们应该手动添加索引吗？我们应该检查数据库大小的增长然后一级一级增加索引吗？
不是。我们希望这些高层级的索引可以被自动地添加或者删除：当有大量数据插入使得数据库表越来越大时，我们希望索引级数可以自动增加；而当我们删除大量记录使得数据库表减小后，我们希望索引级数可以自动减少。简而言之，我们希望自动管理那些高层级索引，即我们希望能够实现自我管理功能的多级索引，这也为 B 树和 B+ 树提供了思路。实际上，B 树和 B+ 树来源于多路查找树，所以接下来我们将讨论多路查找树，然后再讨论 B 树和 B+ 树。
6. 多路查找树
在讨论多路查找树之前，我们先回忆一下二叉查找树：
二叉查找树 (Binary search tree, BST) 是指一棵空树或者具有下列性质的二叉树：
- 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若任意结点的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
- 任意结点的左、右子树也分别为二叉查找树。
在二叉查找树中，当我们想要在二叉查找树中查找任何元素时，我们将从根结点出发，如果查找目标比当前结点值小，则继续沿着其左子树进行查找；如果查找目标比当前结点值大，则继续沿着其右子树进行查找。
在二叉查找树中，每个结点只有 $1$ 个 key，并且最多只有 $2$ 个子结点。那么，我们可以构造一棵树使得每个结点有多个 key 和多个子结点吗？答案是可以，我们可以构造一棵下图所示的树：
显然，这样一棵树的查找效率要高于普通的二叉查找树，但是其搜索方式和普通的二叉查找树是相同的，我们称之为 多路查找树 (multi-way search tree, $M$-way ST)。在上图的例子中，每个结点有 $2$ 个 key，并且最多可以有 $3$ 个子结点，所以这是一棵 3 路查找树。对于一个 $M$ 路查找树，每个结点最多可以有 $M$ 个子结点，并且每个结点包含 $M-1$ 个 key。所以，$M$ 路查找树是二叉查找树的一种扩展，或者说二叉查找树是 $M$ 路查找树的一个特例。
现在我们来看一下 $M$ 路查找树的结点。对于一棵二叉查找树，其结点结构如下：
对于一棵 $M$ 路查找树，这里以 $4$ 路查找树为例，每个结点可以包含 $3$ 个 key 和最多 $4$ 个子结点，其结构如下：
下面我们尝试利用 $M$ 路查找树的结点结构来构建索引，回忆一下，索引结构如下：
结合 $M$ 路查找树的特点，我们可以构建以下结点结构：
对于多级索引结构，我们可以为其构建一棵 $M$ 路查找树，其中结点结构如上图所示：每个 key 后面紧跟一个指向对应的数据库记录的指针。
现在思考一下，如果我们只是像这样简单地利用 $M$ 路查找树构建索引，会存在什么问题？我们来看一下在 $M$ 路查找树中，新数据的插入操作是如何完成的，以及它存在什么问题。
我们以 $10$ 路查找树为例，即每个结点可以有最多 $10$ 个子结点，并且每个结点中包含 $9$ 个 key。假设现在我们需要对一棵空树插入一些新的 key。
Keys: $10, 20, 30$
首先是 $10$，我们先创建一个根结点，并且将 $10$ 插入其中：
然后，对于根结点，我们还可以在其中插入最多 $8$ 个 key。但是，对于 $20$，我们这里选择创建一个新的子结点，并将其插入其中：
然后，对于 $30$，我们这里还是选择创建一个新的子结点，并将其插入其中：
因此，我们可以按照上面的方式完成三个 key 的插入，但这显然是有问题的。我们应该先填满一个结点，然后再创建下一个结点。但是，$M$ 路查找树并没有任何机制可以保证这点，我们可以以任意方式完成插入操作。这意味着，如果我们一共有 $n$ 个待插入的 key，那么 $M$ 路查找树的高度可能会达到 $n$，这会使得 $M$ 路查找树的时间复杂度退化为线性时间复杂度 $O(n)$，这就是 $M$ 路查找树存在的主要问题：树的创建过程不可控，可能会退化为效率低下的线性查找。
7. B 树
所以，我们需要在 $M$ 路查找树的创建过程中引入一些机制来防止上述情况的发生，这就是 B 树。实际上，B 树就是附加了一些规则的 $M$ 路查找树。我们来看一下 B 树具体引入了哪些规则：
- 每个结点必须填满至少一半的 key。对于 M 路查找树，每个结点要至少包含 $\lceil m/2 \rceil$ 个 key。例如，对于 $10$ 路查找树，每个结点至少需要包含 $5$ 个 key，然后我们才会考虑创建新的结点。这条规则可以帮助我们控制树的高度。
- 根结点可以有至少 $2$ 个子结点。
- 所有的叶子结点必须在同一层。
- 树的创建过程是由底向上的。
当我们按照以上规则构建 $M$ 路查找树时，我们实际上构建的就是 B 树。
下面我们以一些 key 为例来由底向上地构建 B 树：
- $M=4$
- Keys: $10, 20, 40, 50$
首先，我们创建一个根结点，并将 $10$ 插入其中：
它可以有最少 $2$ 个子结点。并且，在之前的多级索引中我们提到过，每个 key 后面可以有一个记录指针。然后，我们在根结点中插入 $20$：
然后我们在根结点中继续插入 $40$：
接下来是 $50$，但是根结点已经满了，没有剩余空间留给这个 key 了。所以，我们需要分裂该结点，在新结点中插入 $50$，并将 $40$ 取出并上升一层，将其放入新的根结点中：
所以，当某个结点已经装满 key 时，如果此时有新的 key 需要插入，我们将创建一个新的结点并将新的 key 插入其中。同时对满 key 结点进行分裂，取出其中的一个 key 并将其放进新的根结点中。这就是在 B 树创建过程中的结点分裂过程，可以看到，这种方式将由底向上地构建 B 树。
B 树非常适合用于实现多级索引结构，它可以根据 key 的数量自动构建高层级的索引。对于上面的例子，我们可以继续插入一些新的 key，来观察 B 树是如何自动构建多级索引的。
Keys: $10, 20, 40, 50, 60 ,70, 80, 30, 35, 5, 15$
继续插入 $60$：
继续插入 $70$：
继续插入 $80$，由于右子结点已满，我们需要分裂右子结点，在新结点中插入 $80$，并将 $70$ 取出并放入根结点中：
继续插入 $30$：
继续插入 $35$，由于左子结点已满，我们需要分裂左子结点，在新结点中插入 $35$，并将 $30$ 取出并放入根结点中：
所以，每当有结点被填满时，我们将分裂该结点，并将其中一个 key 取出并放入其父结点中。
继续插入 $5$：
继续插入 $15$，由于左子结点已满，我们需要分裂左子结点，将 $20$ 放入新结点中，并将 $15$ 放入根结点中。然而，由于根结点也已经满了，所以我们继续分裂根结点，将 $70$ 放入新结点中，并将 $40$ 取出并提升一层，将其放入新的根结点中：
注意，这里我们在每次分裂结点时总是保证取出 key 的左侧结点拥有更多的 key，实际上，我们也可以让右侧的 key 更多，这取决于我们自己的习惯。可以看到，现在我们已经构建了一个具有三级索引的 B 树，这就是多级索引的构建过程。现在，树的生成过程是可控的，所有的叶子结点都在同一层级，这使得 B 树与多级索引在结构上更加相似。
现在，我们来看一下 B 树在数据库中是如何使用的。这里有一个常重要的细节，正如我们前面所讨论的，每个 key 后面都可以存放一个记录指针，它直接指向数据库中的某条特定记录：
所以，B 树中的结点包含 key、子结点指针和记录指针。
8. B+ 树
在 B+ 树中，除了叶子结点，其余非叶子结点中不再包含记录指针，非叶子结点中的所有 key 都将在叶子结点中保存一份拷贝，即 B+ 树中的所有 key 都可以在叶子结点中找到，并且叶子结点之间采用类似链表的方式连接：
B+ 树的这种结构与我们之前讨论的多级索引结构完全一样。B+ 树与 B 树的主要区别在于：
- B+ 树中，叶子结点中保存了所有的 key，其中有些 key 在非叶子结点中也进行了冗余存储。
- B+ 树中，非叶子结点不再包含记录指针，所有的记录指针都保存在叶子结点中。
- B+ 树中，所有的叶子结点构成了一个链表。因此，叶子结点所在的层实际上构成了一层密集索引，而非叶子结点所在的层构成了稀疏索引。
因此，与 B 树相比，B+ 树的结构更加符合多级索引。
9. 总结
我们首先讨论了磁盘的物理结构以及数据是如何存储在磁盘上的，然后我们介绍了关于索引和多级索引的概念，之后我们介绍了 $M$ 路查找树及其存在的问题，最后我们介绍了基于 $M$ 路查找树的高级数据结构 B 树和 B+ 树，二者的差异以及它们与多级索引之间的联系。
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。 欢迎转载，并请注明来自：YEY 的博客 同时保持文章内容的完整和以上声明信息！