MySQL索引详解篇

先来感受一下关于MySQL面试题的夺命连环炮。Q1：为什么使用索引? Q2: MySQL InnoDB、MyiSAM索引底层是怎么实现的有什么区别？Q3：为什么索引底层使用B+树实现，用红黑树或者AVL树不行吗？Q4：MySQL5.6版本对索引进行了哪些优化？Q5：ICP、MRR是怎么回事呢？Q6：索引什么情况下会失效呢？Q7：索引优化做过吗？怎么做的？Q8：索引最左匹配原则是怎么回事？等等问题...

1、磁盘那些事

    先问大家个问题当你在SQL Windows中输入select * from user查询语句时，计算机是如何为你读取到数据的呢？大体流程是这样的：操作系统只识别0和1组成的代码为啥呢？我们知道数据存在于磁盘或者内存中，如果你从磁盘中读取数据会发现磁盘是凹凸不平的，是因为要区分是否被磁化，凸起的地方代表数字1其实是被磁化为1，凹的地方代表数字0。因此硬盘可以以二进制来存储表示文字数据等信息。读取数据的时候首先根据逻辑地址找到磁盘对应的物理地址，也就是要知道数据在哪个磁道和扇区，然后磁盘将磁头放置在该扇区之后开始从内存中读取数据，要想找到扇区还需要寻道以及磁盘旋转将目标扇区旋转到磁头下，如果你没理解或者没接触过磁盘底层原理也没关系，介绍这些只是为了让你知道你读取数据是如此复杂。

2、局部性原理

    既然读取数据如此麻烦那有没有什么好的方法可以使读取效率提高呢？思考下既然磁盘的寻道等过程无法省略，那每次都帮我多读取一些数据不就好了？如你查询id为6的数据但是我把id为1的前后数据也帮你读取出来，如将id为1-6以及6-10的数据都读取出来放置在内存中，这样做的好处是加入哪天你要查询id为1的用户信息时你都不需要再IO一次。这个过程叫做预读取。这样做的主要原因是预读取的时候是顺序读取对于磁盘来说不需要寻道时间只需要旋转时间（目标扇区旋转到磁头的时间）。再来个确切的例子，你现在要使用字典来查询“莫”，如果没有目录你会怎么做是不是一页页翻，直到找到为止，问题来了下次我要查找“魔”那又该怎么办呢？尴尬了“莫”字在字典中第20页，“魔”在字典183页，明明这2个汉字拼音相同只是音调不同但是我要翻到183页才能找到。如果使用预读取会这样处理：既然拼音相同而音调不同我就认为他们是具备某个共同特征，读取音调为1的时候我就把mo的2，3，4和“莫”相近的汉字都列出来，并且我将他们放在一页或者多页，下次我再读“魔”字的时候它肯定在20页附近，这样我会少读100多页，效率提高了吗？

    再聊回计算机操作系统，它把预读取的一块数据叫做“页”，你也可以理解为预读取单位，读取的一页数据大小一般是4K，磁盘和操作系统读取数据都是以页进行交换。

3、索引

    如上所述，虽然解决了相近音调读取的问题，但是现在查询某个汉字的时候还是需要一页页翻，还可以再优化吗？聪明的你肯定会想到在字典第一页加个目录，从a-z排序再次读取的时候先去目录找到拼音然后翻到对应页数，这样你找的汉字肯定会在当前页或者相邻页。至此终于引出了为什么使用索引，下面来讨论下MySQL是如何设计实现索引的。

4、索引之数据结构

    站在设计者的角度索引使用的数据结构应该满足询值复杂度较低即可在页中快速找到所需数据。满足条件的数据结构很多比如Hash、链表、二叉树、AVL树、平衡二叉树、B树、B+树，那为何InnoDB存储引擎使用B+树作为索引的实现呢？

Hash算法：提到Hash你可能首先想到的是HashMap因为它底层实现依托于Hash算法，Hash的优点是寻址快（O(1)复杂度）只要有key就可以马上得到Value，缺点是数据量大的时候会造成Hash冲突，而解决Hash冲突本身是一个很复杂的过程，虽然再Hash方法、拉链法可以有效解决冲突但又会造成内存开销。比这些缺点更让人难以接受的是Hash不支持范围查找，只能做等值匹配，换言之只能查询select id = 1却不能查询select id > 10。

二叉树：要想了解B+树需要先了解二叉树，因为B+树是通过二叉树，再由平衡二叉树，B树演化而来，为了更好的理解树采用模拟的方式展示下各种树的区别。

 

    如图所示在二叉树查找中左子树的值总是小于根节点的数据，右子树的值总是大于根节点的值，根据这一规则如果想要找到6的记录，先找到根节点8，因为6小于根节点因此在左子树中寻找记录，而6大于5因此再寻找右子树，一共遍历了3次节点，同样如果想要找到11也需要遍历3次，而如果不使用二叉树改为平均顺序查找呢？(1+2+3+4+5+6+7) / 7 = 4，二叉树平均查找次数为：(3+3+3+3+2+2+1) / 7 = 3 因此二叉树的平均查找速度要比普通的顺序查找快。那为何不使用二叉树实现索引呢？这是因为二叉树可以随便构造，如下图所示：

 

如果插入的数据为有序数据则会构造出来一棵顺序二叉树，这样查找数据的时候就又重新回到了平均顺序查找。因此二叉树的升级版本AVL登场。

ALV：又叫自平衡二叉树，它出现的目的就是为了解决二叉树出现上述顺序排列的情况，AVL树规定任何两个节点的子树高度最大差为1，这样就可以避免二叉树一直构造，成为顺序查找，当然实现AVL需要旋转（左旋右旋）所以维护AVL树会有一定开销，如果是对节点进行删除那还需要对删除后的节点重新旋转。

B树：即多路平衡查找树，为了解释B树我们先来看一下B树长什么样子，B树的数据结构不多做介绍，主要研究下B树如何实现检索，如现在要查询数据16，第一次磁盘IO：16小于根节点17，所以走左侧，第二次IO：16大于12走右侧，第三次IO：需要在内存中对13和16进行一次比较，最后找到16。整个寻找过程满足BST树规则，和AVL树不同的是B树中每个节点存放的值增多，如17\35节点存放的值越多表示在一次磁盘IO中可以查找更多的数据，换言之可以减少磁盘IO次数从而提高查询效率。

    我们知道AVL树要想保持平衡需要进行左旋或者右旋，那B树如何保证呢？答案是节点分裂或合并。如下图1所示Degree(度)最大为3的B树中，如果现在要插入4过程为：首先判断4小于6因此走左侧，到了第二层4大于3应该在3的右边插入但是由于Degree最大为3即表示孩子节点数必须小于3，因此需要将第二次的3\5进行分裂，分裂过程为：首先4处于3和5之间对于该层次4处于中间节点，因此中间节点需要向上层Index Page进行合并，换言之现在4要去上层但尴尬一幕出现了上层为根节点6/8，如果再向它们插入4后Degree为3不满足规则(如果节点为3个数据则Degree必定为4我们限制的Degree为3)，因此现在需要再次进行分裂，由于4已经移动到了上层因此现在上层结构为4/6/8，6处于中间节点因此6需要继续向上移动，最后会变成如下图2所示：

 

图1

图2

B+树：终于来到了终极实现方案B+树，既然B树已经有很高的查询效率为何还需要B+树呢？首先B树中所有的节点都会存放数据，上面叙述的B树在添加数据时需要不停的分裂合并会造成树的高度越来越高，IO次数又会变多，那么B+树做了哪些改良呢？知道B树缺点后我们进行改善为了让树的高度降低从而减少IO次数，我们将B树中的关键字树N和Degree设置为相等，同时非叶子节点不再存储真实的数据，将每一行的数据都放在叶子节点上，B+树结构如下：

B+树有如下特点：B+树中所有记录节点都是按键值大小顺序存在同一层的叶子节点上，由各叶子节点指针进行连接，上图B+树高度为2，每页可以存放4条记录，当然只是一个模型图所以存放数据比较少，在Innodb每页大小默认为16kb，现在我们来模拟一个场景，如果Mysql中一条记录对应大小为1kb而bigint类型在Mysql中占8个字节，那么再加上上层节点对下层节点引用的指针大小(每个指针大小为6字节)，那么一个节点的大小为14字节，一页为16kb对应字节数为16384(16*1024)，那么此时在0度(第一层)下会有16384/14=1170路，也就是会有1170个分叉，那么到了第二层就会有1170*1170路，最后到达叶总节点因为一个叶子节点会存放16kb数据，因此一颗深度为2的B+树一共可以存放1170*1170*16=21902400条数据。因此一张为2000万条数据记录的表查找数据时只需要进行3次IO，如果表数据上亿条则只需要将树深度变为3同时再多一次IO(4次)即可。对比B树来说B+树可以用更少的IO次数存放更多的数据，这就是为什么Innodb存储引擎默认使用B+树的数据结构作为索引实现。

5、索引的分类

聚集索引：InnoDB存储引擎将索引分为聚集索引(也叫主键索引)和辅助索引(或者非聚集索引)，首先介绍聚集索引它是按照每张表的主键构造一颗B+树，同时叶子节点存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页，然后每个数据页都通过一个双向链表进行链接。由于数据页只能按照一颗B+树进行排序，所以每张表只能有一个聚集索引也就是一个主键。我再以图的形式表现一下：

在根节点中存放key和指向下个位置的pointer指针，其中key是值计算是主键值的二进制，我这里的80000001是主键为1的二进制当然我省略了0x，你一定很好奇为什么不是0x0001呢？这是因为在创建表指定主键类型为INT的时候是无符号的。接着根据指针0040找到处于叶子节点的数据即表数据。这里需要注意的一点是虽然图中是按照顺序存放的聚集索引，但是实际上聚集索引是逻辑上连续的而非物理上，如果是物理上连续的话那么维护成本会很高，聚集索引的好处自然是查找数据快。

辅助索引：对于辅助索引来说它和聚集索引最大的区别就是叶子节点并不包含全部的记录数据，而是存放辅助索引本身以及指向聚集索引的主键值，因此如果你对表中的name字段做了辅助索引的话，查找name = 'runqing'的时候首先是在辅助索引的这颗B+树上查找到runqing，然后在根据runqing所对应的主键值去聚集索引的B+树上根据主键去查找出完整的数据，这个过程叫做"回表"。那么辅助索引查询每次都必须要回表吗？答案是否定的假如我现在有select id from user where name = 'runqing'这个过程首先去辅助索引找到runqing，由于辅助索引runqing中有包含主键id而此次查询也只是需要查到id属性，这种情况下就不需要去聚集索引中回表查询，这种查询被成为"索引覆盖"。

6、索引最左匹配

    建立索引时有时候需要建立联合索引如对name\age 2个属性联合起来建立索引，假设有select * from user where name = ? and age = ?，select * from user where name = ?，select * from user where age= ? ，select * from user where age = ? and name = ? 四条查询语句那么那几条会走索引呢？答案是：1/2/4这三条会走，第一条语句完全匹配索引因此会走索引，第二条语句因为建立索引时name在左因此在构建B+树时会在叶子节点的最左侧有序排列，因此name是有序的也是会走索引的，而第三条则不会走索引，这是因为age是在叶子节点中name属性后面建立并不是有序的因此不会走索引，最后第四条虽然顺序不同但是会走索引，因为MySQL优化器会自动为你排序转化为name/age顺序(CBO优化器)，优化器的话单独会有一篇。为此我又画了一幅图以便于理解，这里name我就用字母顺序以代表有序，b< h<r<y为有序排列, 对于age来说16、18、25、23并不是有序排列的，因此该类查询并不会走索引。这就是索引的最左匹配原则。

7、索引下推（ICP）

    之所以聊索引下推是建立在MySQL5.6版本之后对索引的一种优化方式，在此之前版本的MySQL是不支持索引下推的。在没有ICP之前首先根据索引查找记录，然后再根据where条件进行过滤，如select * from user where name='haihan' and age=18假设name为辅助索引查询时首先根据name索引查找出满足条件的记录，然后再根据age=18来过滤，而ICP优化的内容为将where条件过滤这部分放在存储引擎层来做，当查询name='haihan'时会判断是否可以进行where条件过滤，参照第6部分的图有了索引下推查找数据首先找到name='haihan'之后不会直接返回放在服务层去筛选(ICP之前)，而是会把age=18和当前B+树中name='haihan'对应的age比较最后返回，因此说它是将服务层的操作下推到了Innodb存储引擎层来做，这样可以减少IO次数从而提高性能。

8、MRR

    MRR的出现主要是为了减少磁盘的随机访问，并且将随机访问转化为顺序的数据访问，这样的话SQL查询的时候性能会有极大提升，MRR有这样几个好处：首先在查询辅助索引时，根据得到的查询结果按照主键进行排序，然后再根据主键去回表查询完整数据。同时还可以减少缓冲池中页被替换次数，批量处理对键值的查询操作。MRR是如何工作的呢？首先会将根据辅助索引查询到的键值放在缓存中，这个时候查询到的数据都是根据之前的主键进行排序好的，然后将缓存中的键值根据RowID(主键类型为int因此rowId就是主键列)进行排序，最后根据RowId去访问实际的数据文件。举个例子还是以上面的name/age为例，现在有查询语句select * from user where age >= 15 and age < 30 and name = '张三'(假设有多个张三但是年龄不同)，没有MRR的话做法是先把age>15并且小于30的数据都取出来然后再根据name='张三'进行筛选，这样做的弊端如果有大量name并不是张三但是满足age条件的数据被取出来如下图所示，因此MRR会进行查询条件的拆分然后再去查找数据，优化器会将上述的查询条件拆分为(15, '张三')(16, '张三')(17,'张三')...，这样的话虽然是范围查询但是就相当于变成了索引全匹配查询，效率自然提升。

9、索引失效

    这是一个关于如何根据索引写好查询语句的问题，没有什么难的，只需要记住常见的几条就好。我这里每一条失效的原因都解释下还是以上面的name\age辅助索引为例，当然索引失效的场景有很多，要想看是否走索引只需要在查询语句前加EXPLAIN。

1)  使用!=或者<>会让索引失效(name!='xx'匹配不到索引列会进行全表扫描)

2）类型不一致(name创建的时候为varchar，你查询的时候用的是int)

3）有些MySQL函数会使得索引失效(如DATE())

4）运算符导致索引失效(where age-1=18，索引不知道-1是个啥包括一些+-*/,等等)

5）如果使用OR连接的不是一个字段会造成索引失效

6）like语句随便用(name like '%浩'不好意思索引不知道你的前缀%匹配，直接进行全表扫描)

7）IS NULL(这个是经常会犯错的，name is null真的不会走索引)

10、索引创建的时机以及场景？

    这个问题如果你去网上搜索基本上都是一套标准回答，比如下面这套模版，看了之后等你真正需要创建索引的时候还是一脸无奈。

      要想建立合适的索引绝对不是靠经验或者想象去做，在Mysql中有一个叫Cardinality的东西也就是基数值，在介绍它之前我们先来说一种很容易就可以判断是否需要建立索引的依据，如果user表中有性别字段sex，请问它需要建立索引吗？答案是肯定的不需要，因为它属于低选择性什么意思呢？sex的取值范围只有男女('M','F')两种，这种情况下你就算以sex作为查询条件全表扫描也就50%的数据，并没有发挥索引的作用，相反如果是以name创建辅助索引基本上一个应用中name是不允许重复的，就算偶尔会有重复但name的取值范围也会很广，这种称为高选择性，因此在创建索引的时候应该选择那些高选择性的字段。

    以我创建的cust表为例，该表有42299条数据，我对cust_name这个字段创建了索引，先来看下：

Cardinality的值为41655，Cardinality表示不重复记录的预估值或者叫基数值，最好的效果是Cardinality/rows=1也就是Cardinality/42299=1表示该字段不会有重复值或重复值较小，如果该结果太大则表示不应该创建索引。但是我再执行一次show index则可能会有不同的结果。

这是因为Cardinality的值是抽样统计，过程为：首先取得B+树索引中叶子节点的数量记录为A，然后随机取得B+树索引的8个叶子节点，统计每页不能记录的个数记为P1,P2...P8，最后根据采集到的信息计算Cardinality值：Cardinality=(P1+P2+...+P8)*A/8，之所以每次结果都不一样是因为每次都是随机取8个叶子节点进行统计。

总结：索引本身包含很多内容，本文只是介绍了索引的由来、索引分类、B+树、MRR、ICP、回表、最左匹配、索引失效、Cardinality等内容，有些其他涉及到的内容另行补充。