数据结构之B树

一、B树的基本概念

B树是一种多叉树，被广泛应用于数据库索引中。它也是一种特殊的搜索树，和搜索树最大的不同在于它的每个节点都包含了n个关键字和n+1个指向子节点的指针。它的表现形式为：

B树的特点：

1. 假设x.key为当前节点中的关键字，x.child.key是子节点中的关键字，那么它们之间存在以下关系：
   x.child.key <= x.key1 <= x.child2.key <= x.key2 <= x.child3.key <= ... <= x.keyn
2. 每个节点的关键字个数都有上界和下界，上下界用B树的最小度数t ≥ 2来表示。
3. 除了根节点以外，每个节点必须有t - 1个关键字，除了根节点以外，每个节点都有t个孩子。
4. 每个节点最多有2t - 1个关键字，最多有2t个孩子。当一个节点恰好有2t - 1个关键字时，称该节点是满的。
5. t = 2的时候B树最简单，每个内部节点有2、3或者3个孩子，也被称作2-3-4树。
6. t值越大，B的高度就越小。

为什么B树广泛应用于索引中

因为磁盘读取的最小单位是扇区，每个扇区是512字节。操作系统读取磁盘的最小单位是块，一个块包含了若干个扇区（一般一个块是4096字节，包含8个扇区）。如果和红黑树或其他二叉搜索树一样，每个节点只保存一个数据，那么磁盘读取的效率就相当低了。如果需要读取多个数据，就要执行多次磁盘IO操作才能完成任务了，而磁盘IO在系统中属于较为耗时的操作，因此多次IO势必导致效率大大降低。

B树就是为了改进这一问题而衍生出来的，B树的节点一般设置为磁盘的块大小，也就是4K，里面包含了多个数据节点的内容，这样一次IO就能读到多个数据内容。并且由于B树也具有搜索树的性质，因此很快就能定位到数据内容。

二、B树操作

B树的主要操作有两个：分裂和合并。因为B树的每个节点包含关键字的数量为[t - 1, 2t - 1]，当节点的关键字数量超出后，就要对节点进行分裂操作，分裂操作会导致B树高度增加。当节点关键字被删除，数量不满足条件时就要合并两个节点，合并节点会导致B树高度下降。

3.1 增加节点

以一个度为4的B树为例，插入S后，B树节点的关键字数量变成了7，需要进行分裂。

此时对节点的分裂过程为：

1. 新生成节点，将S右边的关键字和子节点移到新节点中。
2. S左边的关键字和子节点保存在当前节点。
3. S节点往上提，放到父节点中的合适位置。
4. 如果S节点上提导致父节点的数量也超出了，还需要继续对父节点进行分裂。

注意：每次上提到父亲节点的关键字都是被分裂节点的中间关键字。

分裂示例

以下是度为3的B树分裂的过程，每个节点最多有5个关键字，最少2个关键字。

初始时的B树：

插入B，这只是一个简单的对叶节点插入的过程，插入后不会影响其他节点，B树的条件也还满足，直接插入就行：

插入Q，因为插入Q后会导致RSTUV节点关键字超出，因此要分裂这个节点。T节点作为中间节点放到父节点中（也可以把S提到父节点，T放在UV节点）：

插入L，它被放到JK节点之后，也是一个简单的叶节点插入。但是因为根节点的关键字满了，所以对根节点分裂，此时将P提出来作为根节点，树的高度加1：

插入F，放在ABCDE节点之后，插入后将导致节点分裂，节点C提到父节点：

2.3 删除节点

在B树中删除节点，将会引发节点的合并。相对于增加节点来说，删除节点的远比增加节点要复杂。

以上面的B树为例，初始状态为：

删除关键字F，作为叶子节点，删除F后并没有影响到B树的性质，直接删除即可。得到以下B树：

删除关键字M，因为M所处的节点是内部节点，删除M后会导致NO关键字所在的节点没有父节点。此时需要把M的前驱关键字L替换掉M，然后删掉L：

也可以把M的后继关键字N替换上来，但是M替换后会导致子节点不满足关键字数量条件。

删除关键字G，G所处的节点也是内部节点，删除后会导致DE或者JK所处的节点没有父节点，此时也需要和上面删除M一样在子节点中找到前驱或者后继替换上来。但是这里不同的是，两个子节点都是只有t - 1个关键字，再从中拿掉一个关键字后会导致子节点关键字数量不满足。此时就需要合并两个子节点，然后直接删除G节点：

删除关键字D，D所处的节点是叶子节点，可以和删除节点F一样，直接删除。但是这里也有一个不同的点是，父节点和父节点的兄弟节点此时都只有t - 1个节点，此时除了删除节点D以外，还要合并父亲节点，此时树的高度减一：

删除关键字B，B所在的节点关键字数量是t - 1，删除B后会导致节点的最小关键字数量不满足条件。因此要从父节点或者兄弟节点借一个关键字。此时就分为两种情况：

1. 如果兄弟节点的关键字个数也是t - 1，那么直接和兄弟节点合并，从父节点提取一个关键字下来（下面删除C时候的场景）。
2. 如果兄弟节点的关键字个数大于t - 1（目前就是这个情况，兄弟节点有3个关键字），此时就从父节点借一个关键字C替换掉B，借掉C后，就相当于删除了一个内置节点的元素，所以父亲节点要从它后继节点中找一个关键字补上，也就是E。最终的结果就是用C覆盖B，再用E覆盖原来C的位置，再删除E。

删除节点C，此时的情况就是上面的第一种情况了，兄弟节点的关键字个数是t - 1，要合并两个节点，得到：