终于理解 MySQL 索引要用 B+tree ，而且还这么快

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

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

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

为什么不采用红黑树

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

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

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

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

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

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

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

B-tree

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

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

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

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

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

关键字：数据索引。

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

1. 除根节点和叶子节点外，其它每个节点至少有 $?{\displaystyle \frac{m}{2}}?$?2m? 个子节点；

   $?{\displaystyle \frac{m}{2}}?$?2m? 为 m / 2 然后向上取整

2. 每个非根节点所包含的关键字个数 j 满足：$?{\displaystyle \frac{m}{2}}?$?2m? - 1 ≤ j ≤ m - 1；

3. 节点的关键字从左到右递增排列，有 k 个关键字的非叶子节点正好有 (k + 1) 个子节点；

4. 所有的叶子结点都位于同一层。

名字取义（题外话，放松一下）

以下摘自维基百科

鲁道夫·拜尔（Rudolf Bayer）和 艾华·M·麦克雷（Ed M. McCreight）于1972年在波音研究实验室（Boeing Research Labs）工作时发明了 B-tree，但是他们没有解释 B 代表什么意义（如果有的话）。

道格拉斯·科默尔（Douglas Comer）解释说：两位作者从来都没解释过 B-tree 的原始意义。我们可能觉得 balanced, broad 或 bushy 可能适合。其他人建议字母 B 代表 Boeing。源自于他的赞助，不过，看起来把 B-tree 当作 Bayer 树更合适些。

高德纳（Donald Knuth）在他1980年5月发表的题为 "CS144C classroom lecture about disk storage and B-trees" 的论文中推测了 B-tree 的名字取义，提出 B 可能意味 Boeing 或者 Bayer 的名字。

查找

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

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

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

B-tree 的查找分两步：

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

操作流程

现在需要查找元素：88

第一次：磁盘IO

第二次：磁盘IO

第三次：磁盘IO

然后这有一次内存比对，分别跟 70 与 88 比对，最后找到 88。

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

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

另外 B-tree 中一个节点中可以存放很多的关键字（个数由阶决定），相同数量的关键字在 B-tree 中生成的节点要远远少于二叉树中的节点，相差的节点数量就等同于磁盘IO的次数。这样到达一定数量后，性能的差异就显现出来了。

插入

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

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

操作流程

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

1. 查找待插入的叶子节点

   

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

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

删除

删除操作就会比查找和插入要麻烦一些，因为要被删除的关键字可能在叶子节点上，也可能不在，而且删除后还可能导致 B-tree 的不平衡，又要进行合并、旋转等操作去保持整棵树的平衡。

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