MySQL索引原理

一直想总结写一篇关于MySQL索引原理，趁着最近有点时间，把以前的知识总结归纳一下。

MySQL很多企业很多项目都在用，平常面试问SQL执行慢，第一想到的就是加索引，那这个索引加了之后查询为什么会变快？索引的工作原理如何？本文将循序渐进的带大家了解一下MySQL索引的原理。

查询算法

在讲解MySQL的索引原理之前，先讲讲查询算法，为后面索引的查询方式做个简单的铺垫。

二分查找

查询算法有很多，这里只讲二分查找法，因为索引的查询过程就跟二分查找法十分相似。

二分查找的前提是对一个有序的集合进行查询，如果集合是无序的，我们需要将无序集合进行排序，转成有序集合。

假如我们有一个有序数组：[1,2,3,4,5,6,7]，要求查找3在数组中的位置。

查找过程

1. 数组最大下标是7，最小是0（数组的下标是从0开始），中间下标就是：(7+0)/2 = 3.5 ，向下取整就是3（数组的下标都是整数）。定位到下标为3的数组元素是4
   
2. 4比3大，舍弃下标为3之后的元素，重新计算中间值：(0+(3-1))/2 = 1，其中最小下标还是0，最大下标是(3-1)=2 （因为要舍弃下标为3之后的元素）。定位到下标为1的元素为2
   
3. 2比3小，舍弃下标1之前的元素，重新计算中间值：((1+1) + 2) / 2 = 2，其中最大下标还是2，最小下标是（1+1) = 2 （因为要舍弃下标为1之前的元素）。定位到下标为2的元素为3
   

至此，已经定位到了我们需要元素的下标。

二分查找就是不断的折半找中间值的过程。

二分查找的效率虽然比较高，但是对于插入的时候效率就没那么高了。如果往中间插入一个元素，为了保证数组的有序性，需要将插入位置后面的所有元素都往后挪动一位。当数组很长的时候，挪动的元素就多了，效率自然就降下来了。而且每次查找都要重新计算中间位置，那能不能提前把中间位置计算好，查询的时候直接拿中间位置的元素做比较呢？

这就引出了二分查找二叉树的数据结构

数据结构

二叉树

还是拿数组[1,2,3,4,5,6,7]举例，我们将每一个中间值提取出来，用指针连接：

转成一棵二叉树之后，再回头看查找方法就变得简单了。还是查找3：

1. 3比4小往左走
   
2. 3又比2大往右走
   
3. 最后到达3=3，查询到结构之间返回
   
   按照我们构建的二叉查找树，查找会变得很快。当有新元素加入时，不需要移动元素，只需要在对应位置添加指针即可，大大提高了元素插入的效率。

二叉查找树有几个特点：

• 子节点最多有两个
• 比节点大的在右边，比节点小的在左边
• 是一个跳跃的结构，整体上看是无序的，但是看某一条完整的线路是有序的

但是也有一个弊端，由于插入的时候，比节点大的在右边，如果插入的数一直比上一个数大，就会变成瘸子：

可以看到，由于二叉查找的树的特性，比节点大的数一直在右边，不断的添加比上一个节点大的数会导致树变成仅有一条很长的路径。这会导致查询效率又大大折扣，回到了原始的一个个遍历。

自平衡二叉树

自平衡二叉树可以解决二叉查找树退化成为链表的问题。

自平衡二叉树在每次插入的时候，都会移动，保持左右子树的高度差不超过1：

可以看到，每次当左右子树的高度差超过1时，会调整树的结构，避免树退化成单链表的结构。

但是也有问题，当插入的元素越来越多的时候，整个自平衡二叉树的高度就很高，如：

插入了31个元素的时候，整颗树就变成了5层的结构，随着插入的元素更多，树的高度更高，查询时间也就更久。

如果我们把一次查询的比作一次磁盘IO，当我们需要检索最底层元素的时候就要进行5次IO，以检索元素17为例：

那为了减少树的高度，我们可以增加子节点的数量，二叉树之所以叫二叉树是因为限制了子节点只能有两个。那如果添加子节点的数量，就能把树的高度降低。

B树

B树其实就是一个多路树，可以有M个节点，每个节点可以存(M-1)个元素，M称为这个数的阶。当超出M个节点时或节点存储的元素超过(M-1)，就会自平衡二叉树一样自动进行平衡，分裂出新的节点。这里以M=3，3个子节点为例：

可以看到，当节点上的元素超过2个时就会自动分裂出新的子节点，当子节点的个数超过3个时，也会分裂出新的子节点。按照之前的构造一个含有31个元素的3阶B树：

可以看到，树的高度只有4层，如果M越大，层数越小，磁盘IO的次数也就越少，因为节点上的元素存储变多了，也就是说一次IO可以读取多个元素出来。假如需要检索15：

但是B树不太查询的速度不太稳定，如果是查根节点上的数据，只用一次磁盘IO就可以，但是如果查询叶子节点上的元素，则需要更多次的IO。

B+树

B+树就是MySQL现在常用的索引树。

B+树其实就是B树的升级版，原理也是根B树一样，也是一棵多路树，也是可以有M个节点，节点上有(M-1)个元素。

不同的是B+树把数据都放在了叶子节点上，非叶子节点上只存索引值，叶子节点上会通过指针相连。

整体结构如下：

B+树有几个特点：

• 所有索引都会在叶子节点中出现
• 叶子节点之间构成一个双向链表
• 叶子节点存放的是数据的地址引用
• 非叶子节点上存放的是索引值和指针

假设现在有一3阶的棵B+树：

需要索引为10的数据：

这颗3阶的B+树根节点就是10，但检索10的数据是需要一层一层往下查找，直到叶子节点上，因为只有在叶子节点上才存有数据。

B树与B+树对比

查询

B树的查询不稳定，如果根节点上或非叶子节点上检索到数据就可以直接返回，如果在叶子节点上才检索到耗时会长一些。

B+树的所有数据都在叶子节点上，检索数据时需要检索到叶子节点上才能返回数据，这就使得B+树的查询时间相对来说会比较稳定。

删除

B+树有大量的冗余节点，当删除节点时可以减少树的复杂变形。

假如需要删除B+树的根节点：

B树删除非叶子节点，会进行复杂的树变形。会导致删除的时间变长。

假如需要删除B树根节点：

范围查找

首先B树和B+树都是有序的。

B树的叶子节点上没有指针，当需要进行范围查找时，如查找某个时间范围的数据，尽管B树是有序的，但是也只能通过树的遍历来完成，这可能会引发多次IO。

B+树的叶子节点上是有双向指针的，只需要查找到最小值的叶子节点，通过指针就可以一直获取到其他叶子节点的数据，直到到大最大值的叶子节点为止。

MySQL中的B+树

MySQL中比较常用的存储引擎是InnoDB和MyISAM，MyISAM的使用会比较少。

平常在MySQL中，建表的时候都会确定表的主键，而我们也会建一些其他的索引。建表的时候确定主键之后，会为该表创建一个主键索引，而我们建的其他索引称为辅助索引。

索引类型分为非聚集索引和聚集索引：

聚集索引：聚集索引就是以主键创建的索引，在叶子节点存储的是表中的数据，而辅助索引叶子节点存的则是主键索引的值。当需要通过辅助检索数据的时候，使用辅助索引检索到叶子节点上的主键值，再根据主键值去主键索引中检索到对应的叶子节点。只有主键索引的叶子节点才存储数据的地址引用。

非聚集索引：非聚集索引就是主键索引和辅助索引的叶子节点都存储数据的引用地址，当使用辅助索引检索数据的时候，不需要依赖主键索引，再辅助索引的叶子节点上就有数据的地址引用。

MyISAM的索引

MyISAM中的使用的索引为非聚集索引。

由非聚集索引的特性来看，MyISAM并不适合频繁修改表数据，因为当修改表数据的时候，既要修改主键索引的叶子节点的地址引用，又要修改辅助索引的叶子节点的地址引用。

但是对应数据查询来说，MyISAM的查询速度会比较快，因为不需要依靠主键索引再进行一次检索获取到地址引用。

非聚集索引查询过程：

InnoDB的索引

InnoDB使用的是聚集索引。

聚集索引更适合表数据的修改，因为只需要修改主键索引叶子节点上的地址引用。但查询速度会比非聚集索引慢。

聚集索引查询过程：

MySQL中的索引

在MySQL中索引都是有序的，就算是组合索引，也是有序的，假如存在一个联合索引：a，b，c，那它的4阶B+树索引结构是：

可以看到，从左到右，当a相同时，b是有序的，当b相同时，c是有序的。a，b，c在索引树的节点上顺序与定义索引时的顺序相同。a，b，c这个组合索引相当于创建了三个索引：索引a，索引a，b，索引a，b，c。

最左匹配原则

对于组合索引，使用索引时会从左到右的去扫描字段，如果最左边的字段匹配上了组合索引的第一个字段，则会走索引。假设存在一个组合索引(a,b,c)：

select * from table where a = 1 and b = 2 and c = 3;  -- 会走索引(a,b,c)，使用(a,b,c)索引select * from table where a = 1 and b = 2 ;  -- 会走索引(a,b,c)，使用(a,b)上的索引select * from table where a = 1 and c = 3;  -- 会走索引(a,b,c)，使用(a)上的索引select * from table where a = 1 ;  -- 会走索引(a,b,c)，使用(a)上的索引select * from table where b = 2 and c = 3;  -- 不会走索引，最左边的字段没用匹配上

说白了就是查询条件中的字段，与定义组合索引时最左边的字段是否相同，相同则会走索引。根据查询条件中的字段先后顺序不同，使用的组合索引方式有不同。如果查询字段的顺序与组合索引的顺序相同，则可以最大化的使用上组合索引。

索引覆盖

在MySQL中使用B+树，虽然非叶子节点上不存数据，但是有存索引值。假设存在一张表，有字段：id，a，b，c，其中id为主键，a为辅助索引。当我们查询：

select a from t where a = 9;

查询的流程如下：

因为需要查询的字段就是索引值，而节点上又存有节点值，所以当检索命中节点上的索引时，直接返回节点上的数据。

这就是索引覆盖。

回表查询

回顾聚集索引查询过程，当要使用辅助索引检索数据时，如果需要字段不是当前索引的字段，就会触发回表查询，即通过辅助索引的叶子节点上的id，去主键索引中查询到叶子节点中的数据地址，获取数据的过程就叫回表查询。

附

数据结构动画演示地址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html