MySQL——索引与EXPLAIN

前言

本文内容主要参考自《高性能MySQL》第5章以及《MySQL DBA 修炼之道》书中的第三章，算是原书的实践与补充。 上次主要讲了MySQL的基本操作，这次来谈谈索引与EXPLAIN。

I. 什么是索引？

想要深入的学习MySQL相关技术，而不仅仅停留在简单CURD，能够写出百万数据中分分钟查出需要数据的SQL，首先就需要掌握索引技术。那么什么是索引呢？

要理解MySQL中索引是如何工作的，最简单的方法就是去看看一本书的“索引”部分：如果想在一本书中找到某个特定主题，一般会先看书的“索引”，找到对应的页码。所以当数据表中的数据越来越多时，挨个查找记录将会越来越慢，我们需要像查“字典”一样建立一种“目录”，来帮我们仍然能够快速的查找想要的记录。这种“目录”一样的存在便是索引。在MySQL中，存储引擎用类似的方法使用索引，其先在索引中找到对应值，然后根据匹配的索引记录找到数据库表中对应的数据行。

索引，在MySQL中也叫做“键(key)”，是存储引擎用于快速找到记录的一种数据结构。为什么是数据结构？因为本身索引是为了解决查找问题，查找排序在算法中是经常遇到的，实现查找我们通常有一些对应的算法，遍历、二分、二叉搜索树、红黑树、散列表等（详细可以看橙色的那本《算法》书）。而一些快速的查找算法都有其对应的数据结构来实现，索引就是存储引擎实现的一种数据结构能够快速用于查找数据库中记录。后面我们会知道数据结构具体可能是 B-Tree、哈希索引、R-Tree、全文索引等。

索引优化应该是对查询性能优化最有效的手段了。索引能够轻易将查询性能提高几个数量级，“最优”的索引有时比一个“好的”索引性能要好两个数量级。创建一个真正“最优”的索引经常需要重写查询。

同一个表，可以创建多个索引。就像新华字典的索引，不仅仅只有拼音，还有笔画、偏旁部首等。除了允许不同的字段添加索引之外，还可以将字段组合添加索引，组合的先后顺序也影响到查询速度。甚至其实MySQL允许同一个字段上重复创建索引，但这并不可取。

II. 索引类型

对于数据库索引相关问题来说，有许多计算机操作系统底层的名词需要了解并通晓其含义，下面将本文需要提前了解的概念列出如下：

• CPU密集型：CPU密集型也叫计算密集型，指的是系统的硬盘、内存性能相对CPU要好很多，此时，系统运作大部分的状况是CPU Loading 100%，CPU要读/写I/O(硬盘/内存)，I/O在很短的时间就可以完成，而CPU还有许多运算要处理，CPU Loading很高。

• IO密集型：IO密集型指的是系统的CPU性能相对硬盘、内存要好很多，此时，系统运作，大部分的状况是CPU在等I/O (硬盘/内存) 的读/写操作，没有充分利用处理器能力。

• 操纵系统页：磁盘的读写速度比主存慢很多，所以为了提高效率，要尽量减少磁盘I/O，减少读写操作。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存，这样做的理论依据是计算机科学中著名的局部性原理。预读的长度一般为页(page)的整倍数，页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页(在许多操作系统中，页得大小通常为4k)，主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

• 数据库页：数据库文件存储是页为存储单元，一个页可以存放N行数据。我们常用的页类型就是数据页和索引页。以InnoDB引擎为例，其逻辑存储结构如下图所示。所有数据都被逻辑地存放在一个称之为表空间 (tablespace)的空间中。表空间又由段(segment) 、区(extent) 、页(page) 组成。表空间是由各个段组成的，常见的段有数据段、索引段、回滚段等。InnoDB存储引擎表是索引组织的，因此数据即索引，索引即数据。那么数据段即为B+树的叶子节点 (leaf node segment)，索引段即为B+树的非叶子节点 (non-leaf node segment)。区是由64个连续的页组成的，每个页大小为16KB，即每个区的大小为1MB。页是InnoDB磁盘管理的最小单位。InnoDB存储引擎是面向行的，也就是说数据的存放按行进行存放。每个页存放的行记录数目也是有硬性定义的，最多允许存放 16KB/2-200 行的记录，即7992行记录。
  

• 顺序IO：每次访问磁盘的一个目标块时，磁臂就需移动到正确的磁道上，耗费的这段时间为寻址时间；然后盘片就需旋转到正确的扇区上，这段时间又为旋转时延。很明显总共耗费的时间依赖于磁头的初使位置，还有要访问的扇区的位置。如果目标块刚好就在磁头下方，那不需要等待；如果刚刚经过磁头，那就不得不等上一个周期时间。 找到上一个目标块后，下一个目标块就在刚才访问的那一个磁盘块的后面，磁头能立刻遇到，不需等待，这种IO就叫顺序IO。

• 随机IO：如果下一个目标块在磁盘的另一个地方，访问它会有同样的寻道和旋转时延，我们就把这种方式的IO叫做随机IO。数据库的很多设计也都是尽量充分利用顺序IO，传统的数据库架构对随机IO几乎没有还手之力，随机IO几乎令所有DBA谈虎色变，MySQL InnoDB则利用事务日志把随机I/O转成顺序I/O。

• 主存存取过程：从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的内存地址。当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。这里可以看出，主存存取的时间仅与存取次数有关，和存取的数据的位置没什么关系，因为读写数据相当于直接根据地址定位坐标。

• 磁盘存取过程：当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。这个过程耗费的时间包括寻道和旋转时间。由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分之一，因此为了提高效率，要尽量减少磁盘I/O。

索引是一中数据结构，那么索引类型自然是指不同类型的数据结构。索引有很多种类型，可以为不同的场景提供更好的性能。在MySQL中，索引是在存储引擎层而不是服务器层实现的。所以，并没有统一的索引标准：不同存储引擎的索引的工作方式并不一样，也不是所有的存储引擎都支持所有类型的索引。即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。我们主要来研究MySQL支持的索引类型。

B-Tree索引

当谈索引的时候，如果没有特别指明类型，那多半说的是B-Tree索引，它使用B-Tree数据结构来存储数据。那么首先我们先来了解B-Tree数据结构。

① B树，B-树，B+树

首先需要明确的是，B树就是B-(减)树，本文中凡是出现的B-Tree，都是B横杠Tree，而非减号，如果想要表示B减树则直接用汉字减或用B树代表相同含义。

B树

二叉查找树是非平衡树，极端情况下查找性能可能非常低，所以才有了红黑树这类平衡二叉树。B树也是一种平衡树，相比于红黑树之类的2-3平衡树而言，B树的阶，或者说是节点的最大出度不仅仅局限于2或3。从查找效率来说，一般阶大于等于3，用 m 表示。假设一个非空的B树，满足以下性质：

• 根结点至少有两个子女；
• 每个中间节点都包含 k-1 个元素和 k 个孩子，k 属于 [ceil(m/2)，m]；
• 每个叶子节点都包含 k-1 个元素，k 属于 [ceil(m/2)，m]；
• 所有的叶子节点都位于同一层（平衡树）；
• 每个节点中的元素从小到大排列，节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域划分；
• 每个节点包含了 k-1 个元素，以及 k 个孩子的指针。

一个标准的B树如下图：

可以看出当我们查找某一个元素时，最多需要读取 h (B树的高度) 次数即可。如果需要插入一条数据，B树为了维护上面的性质，需要对树的结构做一些调整。如果插入元素后某一节点的元素数目大于 m，则在插入前需要进行分裂。同样，如果删除一条数据，删除后节点的元素数目小于 ceil(m/2)，也要进行相应的合并操作。

利用B树的数据结构来进行存储数据，我们可以将数据与对应的索引信息定义为一个组合[key, data]，key是data的索引。那么一个简单的B树可以表示为：

每个节点中包含了 k-1 个索引值、 k-1 个对应的数据 (除去了索引值之外的数据)以及 k 个指针指向子节点。

B+树

B+树其实是B树的一种变种，MySQL普遍使用B+Tree的数据结构来实现索引，当然包括主要存储引擎MyISAM和InnoDB。B+树与B树相比，主要有以下不同：

• 每个中间节点都包含 k 个元素和 k 个孩子，相当于指针数目也是 k；
• 非叶子节点不存储数据data，只存储key；
• 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

如下是一个B+树的示意图，可以看到完全满足上面的三条性质。

带有顺序访问指针的B+树

一般在数据库系统或文件系统中使用的B+树结构都在经典B+树的基础上进行了优化，增加了顺序访问指针。下图所示的带有顺序访问指针的B+树就是我们经常看到的B+树模样。

对比上一幅图，主要区别在于每个叶子节点增加一个指向相邻叶子节点的指针，这样就形成了带有顺序访问指针的B+树。这样优化的目的是为了提高区间访问的性能，如果要查询key为某个范围内的所有数据记录，当找到第一个数据后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

② 数据库为什么使用B+树？

数据库的索引数据量也是很大的，所以它存储在磁盘中，而非内存。那么当进行增删改查数据时，需要读取索引内容，就进行了磁盘I/O。通过前面的相关概念介绍，磁盘I/O的耗时操作越少越好，所以磁盘I/O次数可以评价索引数据结构的优劣。

先从二叉查找树以及红黑树说起，这两种树本身的阶数是固定的，每个节点的子节点数很小，导致了如果存在很多索引时，树的深度非常深，对应查找需要比较的次数也会非常多，性能必然受到严重影响。

再说B树，因为它的阶数是 m，可以设置的较大，这样可以使的决定查询比较次数的因素——树的深度可以很浅。根据B树的定义，可知检索一次最多需要访问 h 个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将树的每个节点的大小设为等于一个页，这样每个节点只需要一次磁盘I/O就可以完全载入。为了达到这个目的，在实际实现B树时还需要使用如下技巧：

• 每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次磁盘I/O；
• B树中一次查询最多需要 h-1 次磁盘I/O，因为根节点常驻于内存，渐进复杂度为 $O(h)=O(lo{g}_{d}N)$。一般实际应用中，出度 d 是非常大的数字，通常超过100，因此 h 非常小 (通常不超过3，3已经是$10^6$级别数据量)。

所以用B树作为数据库的索引效率远远高于红黑树等。

然而，MySQL的MyISAM和InnoDB都采用的是带有顺序访问指针的B+树去实现索引 ，这又是为何呢？比较B+树和B树的区别，除了叶子节点有顺序访问指针帮助范围查询之外，主要就是非叶子节点上B+树只存有索引(key)，没有额外再存(data)。之前我们已经说过，一般树的每个节点的大小等于一个页的大小，容量固定的情况下，由于B树需要保存数据记录所以一个节点能包含的索引数目比B+树要小。也就是说，一个非叶子节点的出度 d，上限取决于节点内 key 和 data 的大小。具体的公式如下：

$d_{max}$