一、索引到底是什么？

数据库索引，是数据库管理系统（DBMS）中一个排序的数据结构，以协助快速排序、更新数据库表中数据。

我们怎样来理解这张图呢？数据在计算机磁盘中以文件的形式存储，每一行数据有其自己的磁盘地址。如果没有索引，在查找某数据时就需要在磁盘中依次遍历所有数据才能查询；而如果有了索引，就只需要在索引的存储空间内去检索这些数据的磁盘地址（索引的特殊数据结构来完成）就可以完成查询。

就类似于在字典中可以通过拼音或者部首来查询相应的字。

在Navicat工具中，我们在创建索引时是以下这样情况：

索引类型

点开索引类型后可以看到三个选项：Normal、Unique、Full Text。

• Normal：非唯一索引，最普通的索引，没有任何限制。
• Unique：唯一索引，要求键值不能重复。
• Full Text：全文索引，在数据内容比较大时使用，可以提高Like的检索效率。

索引方法

索引的方法有两种：BTREE、HASH

我们首先来看Hash索引：

• Hash索引的时间复杂度是O(1)，因为Hash索引里面的数据不是按顺序存放的，因此不能用来排序。
• Hash索引根据键值来得到HashCode，只能支持等值的查询，不能进行范围查询（无序）。
• 当字段的重复值过多时，就会出现哈希碰撞。虽然可以通过链表或者红黑树来解决，但是也会降低效率。

InnoDB引擎并不是不支持Hash索引，而是不能显示的支持Hash索引。

二、MySQL索引数据模型推演

首先我们来思考一下索引的数据结构。

当使用有序数组时，我们在等值查询与比较查询时效率较高，但是因为数组的结构限制我们只能在存储静态数据时使用。如果需要更新数据（update），可以使用链表来存储。但如果用但单链表来存储，它的效率还是不能达到我们想要的程度时，就有一种叫BST（Binary Search Tree）的数据结构，也就是二叉查找树。

我们来看一下二叉查找树的结构：

如果将二叉查树中的数据投影到平面来看，就可以发现它就是一个有序的链表。既可以实现较高的效率，又可以进行数据的插入，解决了有序数组和单链表的问题。

但二叉查招数同样会有问题，它的查询效率与树的深度息息相关。在最坏的情况下，查询的时间复杂度会达到O(n)。

类似于图中的情况，当数据一直向一个方向插入，就会导致左右子树的深度相差甚远。这样被称之为斜树，类似于一个单向链表，这样的效率时最低的。那么能不能让左右子树达到一种平衡的状态来提高效率呢？

平衡二叉树：左右子树深度差绝对值不能超过1.

那么平衡二叉树都存储一些什么内容呢？

在一个节点中会存储三种数据：键值、数据磁盘的地址、子节点的引用。使用这种数据结构存储时，索引与数据一样存储在磁盘中，如果要存储的数据达不到结点的内存大小，就会浪费大量的空间，从而增加了数据与磁盘交互的次数，消耗的时间就会很多。在继续改良后，将分叉增加，就会形成多路平衡二叉树（B Tree）。

假如我们需要查找的数是15，在查找磁盘块1中的数据时发现17大于15，就查找它的左子树磁盘块2，又因为磁盘块2中12小于15，就查找磁盘块2的右子树磁盘块3，就可以找到15。通过这一过程我们会发现，当节点的分叉数增加时，查找的效率也会随之增加。

如果再进一步升级数据结构，可以得到B+树：

• B+树是B树的升级，所有B树能够做到的事情B+树都能做到。
• 如果想要遍历所有数据，就不需要使用树形结构遍历，直接遍历底部的链表即可。
• B+树的磁盘读写能力比B树更强，因为没有在根节点和枝节点保存数据，所以在一个节点之中可以保存更多的关键字，一次磁盘加载的关键字就会更多。
• 排序能力更强，因为底部数据区有指针将它们形成链表的数据结构。
• 查找的效率更加稳定，因为数据都是存储在叶子节点中，IO次数稳定。

三、存储引擎中索引如何落地？

1. MyISAM—主键索引

从图中可以看出，MyISAM中有两个文件类型：.MYI和.MYD文件。

• .MYI就是索引文件
• .MYD就是数据文件

在.MYI文件中，依旧存储了数据文件的地址，从索引文件中找到数据对应的键值之后就会到.MYD文件中查找数据。

2. MyISAM—辅助索引

辅助索引中同样是这样的方式来获取数据。

3. InnoDB—主键索引

InnoDB引擎中，除了表结构定义文件外，只有.idb文件。主键索引的叶子节点中直接存储了数据，而不是数据的磁盘地址。

聚集索引中数据物理存放的顺序与索引的顺序相一致。InnoDB中，只有主键索引是聚集索引，因为数据是以主键索引组织存储的。而如果我们在其他字段上加入索引，就会是非聚集索引。

我们可以使用生活中的例子来理解：在字典中，如果是按照拼音来查字，字的顺序与拼音的顺序一致，这就是聚集索引。而按照笔画来查，就是非聚集索引，因为字的顺序与笔画的顺序不一致。

4. InnoDB—辅助索引

如果给name字段加上索引，它的叶子节点中除了索引还有主键值。如果在辅助索引你中查询数据，需要先在辅助索引的叶子节点中拿到主键值，再去主键索引中查出数据。这里引出两个问题。

（1）那么为什么要存储主键值而不是主键磁盘的地址呢？

在B树中，是因为有分岔和合并的操作才能让一个节点存储多个关键字并且保证平衡。这时如果键值的地址发生变化，辅助索引就无法找到了，索引就只能存储键值。

（2）没有主键索引怎么办？

数据库会创建一个隐藏的列作为一个默认的聚集索引，所以一张表不可能没有主键索引。

四、索引的使用原则

1. 列的离散度

• 离散度公式：count(distinct(column_name)):count(*)

简单的说，数据中重复值越多，离散度就越低；重复值越少，离散度越高。

因为如果一列中的数据重复值太多，我们就需要扫描非常多的数据。由此我们就可以得出我们应该在离散度高的列上建立索引，这样才能让查询速度最大化。

2. 联合索引的最左匹配

ALTER table user_innodb
ADD INDEX 'comidx_name_phone'('name','phone');

这是同时为多个字段建立索引，数据库会首先判断最左边的字段name，只有当name相等时才会继续判断次左边的字段phone。

explain select * from user_innodb where name = '张三' and phone = '111';
explain select * from user_innodb where name = '张三';
explain select * from user_innodb where phone = '111';

如果我们依次运行上面的代码就会发现，在执行计划中，第一、二两条代码会用到联合索引，而第三条没有用到，因为它没有依据name进行查询。

也就是说，在联合索引中，必须要使用最左边的字段进行查询，否则就不会用到联合索引。

3. 覆盖索引

什么是回表？

在之前我们提到了在InnoDB引擎中，使用辅助索引在查询数据时在叶子节点中会有主键的值来导回到主键索引中，这个过程就称之为回表。

什么是覆盖索引？

如果我们要进行的以下这类的查询操作：

select name from user_innodb where name = '张三';

也就是说，我们只需要查询某一项数据中的某一个字段，就不需要回表这个过程，而这就是覆盖索引的状态。

index 'comidx_name_phone'('name','phone');
explain select name,phone from user_innodb where name = '张三';
explain select name from user_innodb where name = '张三' and phone = '111';
explain select id,phone from user_innodb where phone = '111';
explain select name from user_innodb where name = '张三';