聊聊 MySQL 索引数据结构

温馨提示：

本文最后更新于 2021-8-19，已超过半年没有更新，若内容或图片失效，请留言反馈。

前言

当你遇到了一条慢 SQL 需要进行优化时，你第一时间能想到的优化手段是什么？

大部分人第一反应可能都是添加索引，在大多数情况下面，索引能够将一条 SQL 语句的查询效率提高几个数量级。

索引的本质：用于快速查找记录的一种 数据结构

索引的常用数据结构:

二叉树

红黑树

Hash 表

B-TREE (B树，并不叫什么B减树)

B+TREE

数据结构图形化: 点击查阅

索引数据结构

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

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

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

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

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

为什么不采用二叉树

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

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

为什么不采用 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交互）就会越多，性能就会越差。

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

B-TREE 和 B+TREE

BTREE 是一颗多路平衡查找树 定义如下

每个节点最多有m-1个关键字（可以存有的键值对）

根节点最少可以只有1个关键字

非根节点至少有m/2个关键字

每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它

所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同

每个节点都存有索引和数据，也就是对应的 Key 和 Value

根节点的关键字数量范围：1 <= k <= m-1，非根节点的关键字数量范围：m/2 <= k <= m-1

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

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

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

B-TREE 的查找分两步

首先查找节点，由于 B-TREE 通常是在磁盘上存储的所以这步需要进行磁盘IO操作

查找关键字，当找到某个节点后将该节点读入内存中然后通过顺序或者折半查找来查找关键字。若没有找到关键字，则需要判断大小来找到合适的分支继续查找

B-TREE 和 B+TREE 的相同点

根节点至少一个元素, 根节点至少有两个节点

每个中间节点都包含k-1个元素和k个孩子，其中m/2<=k<=m

每一个叶子节点都包含k-1个元素，其中m/2<=k<=m

所有的叶子节点都位于同一层

每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分

B+TREE 是 BTREE 的变种, 拥有新特性

有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点

所有的叶子节点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接

所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素

B+TREE 比 BTREE 的优势

单一节点存储更多的元素，使得查询的IO次数减少

所有查询都要查找到叶子节点，查询性能稳定

所有叶子节点形成有序链表，便于范围查询

我们具体来看一下B+树结构

我们可以直观地看出节点之间含有重复元素，叶子节点还用指针连在了一起，注意: 叶子节点其实还是个双向指针, 图中未体现右到左的指针而已。每个父节点中的元素都出现在了子节点中，是子节点中的最大（或最小）元素

如上图，根节点中元素8是子节点2，5，8的最大元素，也是叶子节点6，8的最大元素，根节点元素15是子节点11，15的最大元素，也是叶子节点13，15的最大元素。需要注意的是，根节点的最大元素（此处是15）等同于整个B+树的最大元素。无论插入或删除多少元素，始终要保持最大元素在根节点当中。至于叶子节点，由于父节点的元素都出现在了子节点，所以叶子节点包含了全部元素信息。并且每个叶子节点都带有指向下一个节点的指针，形成了一个有序链表