终于理解 MySQL 索引要用 B+tree ，而且还这么快-mysql教程-PHP中文网

mysql教程栏目介绍理解索引的B+tree。

免费推荐：mysql教程(视频)

前言

当你现在遇到了一条慢 SQL 需要进行优化时，你第一时间能想到的优化手段是什么？大部分人第一反应可能都是添加索引，在大多数情况下面，索引能够将一条 SQL 语句的查询效率提高几个数量级。索引的本质：用于快速查找记录的一种数据结构。索引的常用数据结构：

二叉树
红黑树
Hash 表
B-tree （B树，并不叫什么B减树）
B+tree

数据结构图形化网址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

索引查询

大家知道 select * from t where col = 88 这么一条 SQL 语句如果不走索引进行查找的话，正常地查就是全表扫描：从表的第一行记录开始逐行找，把每一行的 col 字段的值和 88 进行对比，这明显效率是很低的。

而如果走索引的话，查询的流程就完全不一样了（假设现在用一棵平衡二叉树数据结构存储我们的索引列）此时该二叉树的存储结构（Key - Value）：Key 就是索引字段的数据，Value 就是索引所在行的磁盘文件地址。当最后找到了 88 的时候，就可以把它的 Value 对应的磁盘文件地址拿出来，然后就直接去磁盘上去找这一行的数据，这时候的速度就会比全表扫描要快很多。

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

为什么不采用二叉树

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

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

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

为什么不采用 Hash 表

Hash 表：一个快速搜索的数据结构，搜索的时间复杂度 O(1) Hash 函数：将一个任意类型的 key，可以转换成一个 int 类型的下标

假设此时用 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 路搜索树。它可能是空树，或者满足以下特点：

除根节点和叶子节点外，其它每个节点至少有 $\lceil \dfrac{m}{2}\rceil$ 个子节点；

$\lceil \dfrac{m}{2}\rceil$ 为 m / 2 然后向上取整
每个非根节点所包含的关键字个数 j 满足： $\lceil \dfrac{m}{2}\rceil$ - 1 ≤ j ≤ m - 1；
节点的关键字从左到右递增排列，有 k 个关键字的非叶子节点正好有 (k + 1) 个子节点；
所有的叶子结点都位于同一层。

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

以下摘自维基百科

鲁道夫·拜尔（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 的名字。