MySQL索引 B+tree

索引的常用 数据结构 ：

1. 二叉树
2. 红黑树
3. Hash 表
4. B-tree （B树，并不叫什么B减树）
5. B+tree

索引查询

大家知道 select * from t where col = 88 这么一条 SQL 语句如果不走索引进行查找的话，正常地查就是

全表扫描 ：从表的第一行记录开始逐行找，把每一行的 col 字段的值和 88 进行对比，这明显效率是很低的。

而如果走索引的话，查询的流程就完全不一样了（假设现在用一棵 平衡二叉树 数据结构存储我们的索引列）

此时该二叉树的存储结构（Key - Value）：Key 就是索引字段的数据，Value 就是索引所在行的磁盘文件地址。

当最后找到了 88 的时候，就可以把它的 Value

对应的磁盘文件地址拿出来，然后就直接去磁盘上去找这一行的数据，这时候的速度就会比全表扫描要快很多。

但 实际上 MySQL 底层并没有用 二叉树 来存储索引数据，是用的 B+tree（B+树） 。

1. 为什么不采用二叉树

假设此时用普通二叉树记录 id 索引列，我们在每插入一行记录的同时还要维护二叉树索引字段。

此时当我要找 id = 7 的那条数据时，它的查找过程如下：

此时找 id = 7 这一行记录时找了 7 次，和我们全表扫描也没什么很大区别。显而易见，二叉树对于这种 依次递增 的数据列其实是

不适合 作为索引的数据结构。

2. 为什么不采用 Hash 表

Hash 表：一个快速搜索的数据结构，搜索的时间复杂度 O(1)

Hash 函数：将一个任意类型的 key，可以转换成一个 int 类型的下标

假设此时用 Hash 表记录 id 索引列，我们在每插入一行记录的同时还要维护 Hash 表索引字段。

这时候开始查找 id = 7 的树节点仅找了 1 次，效率非常高了。

但 MySQL 的索引依然 不采用 能够精准定位的 Hash 表 。因为它 不适用 于 范围查询 。

3. 为什么不采用红黑树

红黑树是一种特化的 AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡；

若一棵二叉查找树是红黑树，则它的任一子树必为红黑树。

假设此时用红黑树记录 id 索引列，我们在每插入一行记录的同时还要维护红黑树索引字段。

插入过程中会发现它与普通二叉树不同的是当一棵树的左右子树高度差 > 1 时，它会进行 自旋 操作，保持树的平衡。

这时候开始查找 id = 7 的树节点只找了 3 次，比所谓的普通二叉树还是要更快的。

但 MySQL 的索引依然 不采用 能够精确定位和范围查询都优秀的 红黑树 。

因为当 MySQL

数据量很大的时候，索引的体积也会很大，可能内存放不下，所以需要从磁盘上进行相关读写，如果树的层级太高，则读写磁盘的次数（I/O交互）就会越多，性能就会越差。

4. B-tree

红黑树目前的唯一不足点就是树的高度不可控，所以现在我们的 切入点 就是 树的高度 。

目前一个节点是只分配了一个存储 1 个元素，如果要控制高度，我们就可以把一个节点分配的空间更大一点，让它 横向存储多个元素 ，这个时候高度就可控了。这么个改造过程，就变成了 B-tree。

B-tree 是一颗绝对平衡的多路树。它的结构中还有两个概念

度（Degree）：一个节点拥有的子节点（子树）的数量。（有的地方是以 度 来说明 B-tree 的，这里解释一下）

阶（order）：一个节点的子节点的最大个数。（通常用 m 表示）

关键字：数据索引。

一棵 m 阶 B-tree 是一棵平衡的 m 路搜索树。它可能是空树，或者满足以下特点：

1. 除根节点和叶子节点外，其它每个节点至少有 m/2个子节点；

为 m / 2 然后向上取整

1. 每个非根节点所包含的关键字个数 j 满足：m/2 - 1 ≤ j ≤ m - 1；
2. 节点的关键字从左到右递增排列，有 k 个关键字的非叶子节点正好有 (k + 1) 个子节点；
3. 所有的叶子结点都位于同一层。

4.1 查找

B-tree 的查找其实和二叉树很相似：

二叉树是每个节点上有一个关键字和两个分支，B-tree 上每个节点有 k 个关键字和 (k + 1) 个分支。

二叉树的查找只考虑向左还是向右走，而 B-tree 中需要由多个分支决定。

B-tree 的查找分两步：

1. 首先查找节点，由于 B-tree 通常是在磁盘上存储的所以这步需要进行 磁盘IO 操作；
2. 查找关键字，当找到某个节点后将该节点 读入内存 中然后通过顺序或者折半查找来查找关键字。若没有找到关键字，则需要判断大小来找到合适的分支继续查找。

操作流程

现在需要查找元素：88

第一次：磁盘IO

第二次：磁盘IO

第三次：磁盘IO

从查找过程中发现，B-tree 比对次数和磁盘IO的次数其实和二叉树相差不了多少，这么看来并没有什么优势。

但是仔细一看会发现，比对是在内存中完成中，不涉及到磁盘IO，耗时可以忽略不计。

另外 B-tree 中一个节点中可以存放很多的 关键字 （个数由阶决定），相同数量的 关键字 在 B-tree

中生成的节点要远远少于二叉树中的节点，相差的节点数量就等同于磁盘IO的次数。这样到达一定数量后，性能的差异就显现出来了。

4.2 插入

当 B-tree 要进行插入关键字时，都是直接找到叶子节点进行操作。

1. 根据要插入的 关键字 查找到待插入的叶子节点；
2. 因为一个节点的子节点的最大个数（阶）为 m，所以需要判断当前节点 关键字 的个数是否小于 (m - 1)。
3. * 是：直接插入
   • 否：发生 节点分裂 ，以节点的中间的关键字将该节点分为左右两部分，中间的关键字放到父节点中即可。

操作流程

比如我们现在需要在 Max Degree（阶）为 3 的 B-tree插入元素：72

1. 查找待插入的叶子节点
2. 节点分裂：本来应该和 70,88 在同一个磁盘块上，但是当一个节点有 3 个关键字的时候，它就有可能有 4 个子节点，就超过了我们所定义限制的最大度数 3，所以此时必须进行 分裂 ：以中间关键字为界将节点一分为二，产生一个新节点，并把中间关键字上移到父节点中。

Tip : 当中间关键字有两个时，通常将左关键字进行上移分裂。

4.3 删除

删除操作就会比查找和插入要麻烦一些，因为要被删除的关键字可能在叶子节点上，也可能不在，而且删除后还可能导致 B-tree

的不平衡，又要进行合并、旋转等操作去保持整棵树的平衡。

随便拿棵树（5 阶）举例子

情况一：直接删除叶子节点的元素

删除目标：50

1. 查找元素 50 位置
2. 在 36, 50, 63 节点移除 50 后，依然符合 B-tree 对节点内关键字的要求：

    ┌m/2┐ - 1 ≤ 关键字个数 ≤ m - 1

┌5/2┐ - 1 ≤ 3 - 1 ≤ 5 - 1

2 ≤ 2 ≤ 4 ✔

情况二：删除叶子节点的元素后合并+旋转

删除目标：11

1. 查找元素 11 位置
2. 在 10, 11 节点移除 11 后，违背 B-tree 对节点内关键字的要求：

    ┌m/2┐ - 1 ≤ 关键字个数 ≤ m - 1

┌5/2┐ - 1 ≤ 2 - 1 ≤ 5 - 1

2 ≤ 1 ≤ 4 ❌

1. 在它只剩1个关键字后，需要向兄弟节点借元素，这时候右兄弟有多的，它说：我愿意把14借给你

但不可能让11和14放一起，因为 14 > 12 ，这时候就要进行 旋转 ~

首先，将父节点的元素 12 移到该节点，然后 12 就让位给14

这整个过程就是删除叶子节点元素后的合并、旋转操作

下面再来道菜

接着删除 10

1. 在 10, 12 节点移除 10 后，违背 B-tree 对节点内关键字的要求
2. 在它只剩1个关键字后，需要向兄弟节点借元素，这时候没有兄弟有多的该怎么办呢

首先，将父节点的元素 8 移到该节点，这时候 3、6、8、12 都小于14，就先把它们放一起

结果又发现父节点只剩个14了，它又违背了 B-tree 对节点内关键字的要求，接着造！！！

首先，还是将父节点的元素 20 移到该节点，这时候根节点都直接没了，直接合并 14、20、26、72 关键字

在这整个过程包括删除叶子节点和非叶子节点的合并、旋转操作

情况三：删除非叶子节点的元素后合并+旋转

删除目标：12

1. 查找元素 12 位置
2. 移除 12 后，违背 B-tree 对节点内关键字的要求

对于非叶子节点元素的删除，我们需要用后继元素覆盖要被删除的元素，然后在后继元素所在的叶子中删除该后继元素。