B树

## 1 为什么要用 B 树、B+ 树索引

1. 常用的数据结构如二叉查找树（Binary Search Tree, BST）的**每个节点只能容纳一个数据**，导致树的高度很高，逻辑上挨着的节点的数据可能离得很远，如果在内存中操作数据的话，这样问题并不大，但是由于**读写磁盘的速度相比内存慢很多**，每次**读写磁盘的单位要比读写内存的最小单位大很多**。
2. 因此，对应的数据结构应该尽量的满足**局部性原理**，即**当一个数据被用到时，其附近的数据也通常会马上被使用**，因此，**逻辑上相邻的数据在物理上也尽量存储在一起**，这样才能**减少读写磁盘的数量**。
3. 因此，对比起一个节点只能存储一个数据的 BST 类数据结构来说，要求这种数据结构在形状上更**胖**，更加**扁平**，即**每个节点能容纳更多的数据**，**这样就能降低树的高度**，同时**让相邻的数据都能尽量的存储在物理上也相邻的硬盘空间上**，**减少磁盘读写**。
4. 以下图为例，图中从根节点出发，查找数据 14 的过程中，经过的第二节点中有键值 `[3,7,13]`，这三个值在逻辑上是相邻的，如果他们在磁盘上的存储也能做到在物理上相邻，那么只需要一次读操作就能把这个节点的数据从磁盘上加载到内存中进行数据比较，这样整个过程就只需要两次磁盘读操作，这种数据结构具有两个特点：
   
   1. **高扇出：** 临近键值的数据局部性更好。
   2. **低高度：** 遍历期间的寻道次数更少。
   
   ![](/media/202106/2021-06-16_222256.png)
5. B 树和 B+ 树就是两种利用磁盘局部性原理进行优化的树结构。
   
   > MySQL 为什么不使用跳表作为索引的数据结构？
   > 
   > 1. 数据库的**数据量比较大**，如果数据库索引使用了跳表，那么：
   >    1. **跳表的层数太高**，**数据存储不紧凑**，**产生大量的空间浪费**。
   >    2. **查询时会产生大量跨页 IO**，而且**磁盘磁头无法对链表进行预读**，**会产生大量的随机 IO**，**对磁盘的缓存不友好**，**查询效率较低**。

## 2 B 树

### 2.1 B 树的定义及性质

1. 在 B 树种，分为两种节点：
   
   1. **内部节点**（Internal Node）**：** 存储了**数据**以及**指向其子节点的指针**。
   2. **叶子节点**（Leaf Node）**：** 叶子节点**只存储数据**，**没有子节点**。
2. 一个**数据**，**既可能存在内部节点上**，**也可能存在叶子节点上**，这一点是与 B+ 树最大的不同，**B+ 树只会将数据存储在叶子节点上**。
3. 创建 B 树时，需要输入一个 degree 参数（以下简写为 $t$），该参数**决定了每个节点上数据量的多少**，即**节点的胖、瘦程度**，而节点的胖瘦程度又会影响整棵树的高度，因为**越胖的节点树的高度越矮**。
4. 为了维护 B 树的平衡性，需要满足以下的属性：
   
   1. **每个节点上的键值以递增顺序排列**。
   2. 一个节点上的键值**大于其左子树的所有键值**，**小于等于其右子树的所有键值**。
   3. 在**内部节点**中，**指向子节点的指针数量总是存储数据节点的数量 +1**。
   4. **所有叶子节点的高度一致**。
   5. **所有节点存储的键值数量在 $[t-1,2t-1]$ 之间**，如果数量不满足此条件，需要做重平衡操作：
      1. **小于 $ t - 1 $**，需要**借用或合并数据**。
      2. **大于 $ 2t - 1 $**，需要**分裂成两个节点**。
5. 如下图所示，该图中的 B 树，$t$ 参数的值为 2（需要特别说明的是，一棵树中每个存储数据的地方，应该既有键值（key），也有数据（value），本文中为了简单起见，存储的数据只有键值）：
   
   1. 由于 $t=2$，因此所有节点的键值数量在 $[1,3]$ 之间。
   2. 所有叶子节点的高度相同。
   3. 以左边的内部节点为例，第一个键值为 3，其左子树的键值为 $[1,2]$，都小于 3，而其右子树的键值为 $[4,5,6]$，都不小于 3。
   
   ![btree-example](/media/202106/2021-06-17_115227.png)

### 2.2 B 树算法原理

了解 B 树的性质之后，下面讨论 B 树中的两个核心操作：**插入**、**删除**，这两个操作的核心，都是在操作如果破坏 B 树的平衡性之后进行重新平衡以满足 B 树的性质。

#### 2.2.1 插入数据

1. B 树中插入数据的时候，首先要**查找插入新关键字的叶节点的位置**，但是，**不能简单的创建一个新的叶节点**，**然后将其插入**，因为这样得到的树将**不再是合法的 B 树**，相反，我们是**将新的关键字插入一个已经存在的叶节点上**。
2. 由于不能将关键字插入一个满的叶节点，因此引入一个操作，**将一个满的节点 $y$**（有 $ 2t-1 $ 个关键字）**按其中间关键字分裂为两个各含 $t-1$ 个关键字的节点**，**中间关键字被提升到 $y$ 的父节点**，以**标识两棵新树的划分点**，但是**如果 $y$ 的父节点也是满的**，就必须**在插入新的关键字之前将其分裂**，最终满节点的分裂会沿着树向上传播。
   
   ![](/media/202106/2021-06-17_113431.png)
   
   ![](/media/202106/2021-06-17_113548.png)
3. 我们并**不是等到找出插入过程中实际要分裂的满节点时才做分裂**，**而是当沿着树往下查找新的关键字所属位置时**，**就分裂沿途遇到的每个满节点**（**包括叶节点本身**），因此，每**当要分裂一个满节点 $y$ 时**，**就能确保他的父节点不是满的**。

![](/media/202106/2021-06-17_113651.png)

#### 2.2.1 删除数据

##### 2.2.1.1 所有删除的都是叶子节点

1. 首先，我们需要清楚第一个要点，**无论我们当前删除的元素是什么**，**最终都会落实到叶子节点上**，也就是说**所有的情况都可以转化成删除叶子节点的问题**。
2. 例如：
   
   1. 在下面这张图中，假如我们要删除元素 11，而 11 在根节点上，显然我们要删除的位置并不在根节点上。![](/media/202106/2021-06-17_145533.png)
   2. 为了避免删除非叶子节点的元素，我们可以先找到 11 的后继节点，这里的**后继节点**指的是**在这棵树上比当前元素大的最小的节点**，在这个图当中，11 的后继节点是 12，我们将 12 赋值给 11，递归往下调用，转变成删除 12。![](/media/202106/2021-06-17_145723.png)
   3. 当然，我们选出来的后继节点仍然可能并不是叶子节点，这没有关系，我们只需要重复执行以上操作即可，因为我们可以保证后继节点出现的位置在树上的深度只会比当前元素更大，不会更小，而树深是有限的，也就是说最多经过有限次转化，我们就可以把删除操作转嫁到叶子节点身上。

##### 2.2.1.2 直接删除叶节点

1. 假设叶子节点当中元素数量很多，我们删除一个仍然可以保证他是合法的，这种情况下直接删除即可。
2. 例如：
   1. 在下图当中 $t=2$，因此非叶节点的取值范围为 $[1,3]$，最多允许一个节点出现 4 个分支。
   2. 假如我们要删除的元素是 19，由于节点 3 当中元素众多，即使删除掉一个元素，依然符合节点的要求，那么就不做任何操作。
   3. 假如我们要删除的元素是 10，由于节点 10 只有一个元素，如果删除了，那么就会破坏节点的最小元素数量的限制，在这种情况下，只有一个办法，就是**先删除**，**再和其他节点借**。![](/media/202106/2021-06-17_155126.png)

##### 2.2.1.3 和兄弟节点借

1. 我们首先考虑和节点的兄弟节点借一个元素，以为兄弟节点和当前节点的父亲节点相同，可以很方便的转移节点并保证树的性质。
2. 对于一个叶子节点来说，他的兄弟节点最多只有两个，也就是他左侧的兄弟和右侧的兄弟，由于 B 树上的元素存在从左往右的递增性，我们认为右侧的是哥哥节点，左侧的是弟弟节点，借的顺序虽然会影响树的形状，但是并不会影响树的合法性，所以我们先和哥哥借，再和弟弟借，或者反过来都行 ，本文采取的是先哥哥后弟弟的顺序。
3. 例如：
   
   1. 假设我们要删除节点 10，节点 10 只有一个元素，删除了必然破坏合法性。
   2. 这个时候我们先看看哥哥的情况，哥哥节点当中有 3 个元素，即使借走一个仍然可以满足要求，那么我们就和哥哥借。![](/media/202106/2021-06-17_161601.png)
   3. 借的方法很简单，由于哥哥节点当中所有的元素都大于当前节点，为了保证元素的顺序我们会**借第一个元素**，也就是 13，但是 13 大于父节点中的 12，所以我们不能直接把 13 塞到原来 10 的位置，而是需要**先将父节点的 12 挪下来**，**放到 10 的位置**，**再将 13 填到 12 的位置上去**。
   4. 最后，达到的平衡态的样子如下：![](/media/202106/2021-06-17_162118.png)
   5. 同理，如果我们删除的是 23，由于他没有哥哥节点，只有弟弟节点，并且弟弟节点满足条件，那么我们就和弟弟节点借一个元素，逻辑和上面的一样，先从父节点要一个元素下来，再从弟弟节点接一个元素放回父节点，得到的结果如下：![](/media/202106/2021-06-17_162535.png)

##### 2.2.1.4 和父亲节点借

1. 如果兄弟节点自身也是勉强达到条件，显然是借不了的，这种时候没办法，只能还是和父亲节点要，如果**父亲节点**稍稍富裕，**给出了一个元素之后还是能满足条件**，那么就从父亲节点借出。
2. 但是需要注意的是，**父亲节点给出一个元素**，那么**他的子树数量也应该随之减少**，**不然**也**会不满足 B 树的特性**，为了达成这一点，可以通过**合并两个子树**来实现。
3. 例如：
   1. 在下图中，我们需要删除 10 节点。![](/media/202106/2021-06-17_163614.png)
   2. 删除之后，得到：
      ![](/media/202106/2021-06-17_163659.png)
   3. 这个图最大的问题是**他的根节点有两个元素**，**但是却有四棵子树**，**这违反了 B 树的性质**，这是**因为原本属于根节点的元素 9 被子树借走了**。
   4. 为了解决这个问题，我们需要**将邻近的两棵子树合并**，也就是将 $[6,7]$ 和 $[9]$ 子树合并，得到：
      
      ![](/media/202106/2021-06-17_164250.png)
   5. 如果我们**跟父节点借合并子树导致父节点中的元素减少而不满足条件**时，不可以跟子节点借，因为我们即使能找到富裕的子节点，也没办法让子树的数量随着也增加 1，我们应该做的是**递归借节点的操作**，让父节点去和他的兄弟以及父节点借元素就好了，在极端的情况下，这有可能导致树的高度发生变化，例如：
      
      1. 在下面的图中 $t=3$，如果我们删除 9，根据刚才的惯例，我们会跟父节点借元素 6，并且和 $[1,3]$ 子树合并，得到：
         
         ![](/media/202106/2021-06-17_165500.png)
      2. 但是这一借会导致父节点破坏了 B 树的最低要求，所以我们需要递归维护父节点，也就是让父节点重复借元素的步骤，我们可以发现对于节点 $[10]$ 来说，他没有富裕的兄弟节点，只能继续和父节点借，这一借会再次导致合并的发生，最终我们得到的结果如下：
         
         ![](/media/202106/2021-06-17_170332.png)
      3. 通过观察上面树结构的变化，我们发现**只要是和父亲节点借元素**，**必然伴随着和兄弟节点合并的情况**，而和**兄弟节点合并**，除了**需要维护两个节点当中的元素**之外，**还需要维护各自的子树**，尤其是如果我们在每个节点当中记录父亲节点以及在父亲节点当中的位置的话，这些都需要维护。

## 3 B+ 树

### 3.1 B+ 树的定义及性质

1. 各种资料上 B+ 树的定义各有不同，一种定义方式是**关键字个数和孩子节点个数相同**（百度百科），一种是**关键字个数比孩子结点个数小 1**（维基百科），这种方式是和 B 树基本等价的，本文采取的是维基百科上所定义的方式。
2. B+ 树包含两种类型的节点，分别是**内部节点**（也称索引节点）和**叶子节点**，根节点本身既可以是内部节点，也可以是叶子节点，**根节点的关键字个数最少可以只有 1 个**。
3. B+ 树与 B 树最大的不同是**内部节点不保存数据**，**只用于索引**，**所有数据**（或者说记录）**都保存在叶子节点中**。
4. $m$ 阶 B+ 树**除了根节点外每个节点包含关键字的个数的取值范围为 $[m/2,m-1]$**。
5. 对于**所有内部节点**，**子指针的数目总是比关键字的数目多一个**。
6. **内部节点中的 $key$ 都按照从小到大的顺序排列**，对于**内部节点中的一个 $key$**，**左子树中的所有 $key$ 都小于他**，**右子树中的 $key$ 都大于他**。
7. **所有叶子节点都在相同高度上**，**叶子节点中的记录也按照 $key$ 从小到大排列**。
8. **每个叶子节点都存有相邻叶子节点的指针**，**叶子节点本身按照关键字大小从小到大链接**。

![clip_image039](/media/202106/2021-06-18_110331.png)

### 2.2 B+ 树算法原理

#### 2.2.1 插入数据

下面的插入操作是以一棵 5 阶 B+ 树为例，其节点（除根节点外）的取值范围为 $[2,4]$。

1. 若为空树，**创建一个叶子节点**，然后**将记录插入其中**，此时这个**叶子节点也是根节点**，插入操作结束。![](/media/202106/2021-06-18_111721.png)
2. 针对叶子类型的节点：
   1. **根据 $key$ 值找到叶子节点**，**向这个叶子节点插入记录**。
   2. 插入后，若**当前节点 $key$ 的个数小于等于 $m-1$**，则**插入结束**。
   3. 否则，将这个叶子节点**分裂成左右两个叶子节点**，**左叶子节点包含前 $m/2$ 个记录**，**右节点包含剩下的记录**，**将第 $m/2+1$ 个记录的 $key$ 进位到父节点中**（父节点一定是索引类型节点），进位到父节点的 $key$ 的**左指针指向左子树**，**右指针指向右子树**，将**当前节点的指针指向父节点**，然后执行下一步。
      
      ![](/media/202106/2021-06-18_112719.png)
3. 针对索引类型节点：
   1. 若**当前节点 $key$ 的个数小于等于 $m-1$**，则**插入结束**。
   2. 否则，**将这个索引类型节点分裂成两个索引节点**，**将第 $m/2$ 个 $key$ 进位到父节点中**，**该节点左边的节点放到左索引节点中**，**右边的节点放到右索引节点中**，然后将进位到父节点的 $key$ 的**左指针指向左子树**，**右指针指向右子树**，然后将**当前节点的指针指向父节点**，然后重复第 3 步。
      
      ![](/media/202106/2021-06-18_114301.png)
      
      ![](/media/202106/2021-06-18_114338.png)
      
      ![](/media/202106/2021-06-18_114521.png)

#### 2.2.2 删除数据

下面的插入操作是以一棵 5 阶 B+ 树为例，其节点（除根节点外）的取值范围为 $[2,4]$。

1. 如果叶子节点中**没有相应的 $key$**，则**删除失败**，否则，执行下一步
2. 删除叶子节点对应的 $key$，如果**删除后节点的 $key$ 大于等于 $m/2$**，**删除操作结束**，否则，执行下一步。
   
   ![](/media/202106/2021-06-18_115435.png)
   
   ![](/media/202106/2021-06-18_115533.png)
3. 如果**兄弟节点的 $key$ 有富余**（借走一个后仍满足 B+ 树的相关要求），则**从兄弟节点借一个 $key$**，同时**用借到的 $key$ 替换父节点**（指当前节点和兄弟节点共同的父节点）**中的 $key$**，**删除结束**，否则，执行下一步。
   
   ![](/media/202106/2021-06-18_115936.png)
4. 若**兄弟节点没有富余的 $key$**，则**将当前节点和兄弟节点合并成一个新的叶子节点**，并**删除父节点中的 $key$**（父节点中的这个 $key$ 两边的孩子指针就变成了一个指针，正好指向这个新的叶子节点），将**当前节点指向父节点**（比为索引节点）：
   
   1. 若**索引节点的 $key$ 的个数大于等于 $m/2$**，则**删除操作结束**，否则，执行下一步。
   2. 若**兄弟节点有富余**，则**父节点 $key$ 下移**，**兄弟节点 $key$ 上移**，**删除结束**，否则，执行下一步。
   3. **将父节点的 $key$ 下移**，**和当前节点及其兄弟节点合并成一个新的节点**，然后将**当前节点指向父节点**，重复第 4 步。
   
   ![](/media/202106/2021-06-18_121434.png)
   
   ![](/media/202106/2021-06-18_121616.png)
5. 需要注意的是，**通过 B+ 树的删除操作后**，**索引节点存在的 $key$**，**不一定在叶子节点中存在相应记录**。

## 4 B+ 树的优点

> InnoDB 的索引使用的是 B+ 树实现的。

1. B+ 树**索引节点上只有索引而没有数据**，因此**能存储比 B 树更多的索引**，这样**树的高度就会更矮**，**磁盘寻道的次数就会越少**。
2. 因为**数据都集中在叶子节点**，而**所有叶子节点的高度相同**，那么**可以在叶子节点中增加前后指针**，**指向同一个父亲节点的相邻兄弟节点**，**给范围查询提供便利**，比如：
   
   1. 对于 SQL 语句 `select * from tbl where t > 10`，如果**使用 B+ 树存储数据**的话，可以首先**定位到数据为 10 的节点**，再**沿着他的 $next$ 指针一路找到所有在该叶子节点右边的叶子节点数据返回**。
   2. 而如果**使用 B 树结构**，由于**数据即可以存储在内部节点**，**也可以存储在叶子节点**，因此**范围查询会比较繁琐**。

## 参考文献

1. [B 树、B+ 树索引算法原理（上）](https://www.codedump.info/post/20200609-btree-1)。
2. 《算法导论（第三版）》
3. [万字长文——详细阐述 B-树中所有细节](https://zhuanlan.zhihu.com/p/111481284)。
4. [B 树、B+ 树索引算法原理（下）](https://www.codedump.info/post/20200615-btree-2)。
5. [B 树和 B+ 树的插入、删除图文详解](https://www.cnblogs.com/nullzx/p/8729425.html)。
6. [B+ 树](https://zh.wikipedia.org/wiki/B%2B%E6%A0%91)。
7. [为什么 MySQL 的索引结构，采用了 B+ 树，没有使用跳跃表呢？](https://segmentfault.com/q/1010000018633282)