想深入MySQL索引，这篇千万不能错过

大家好，我是【码老思】，索引是一个数据库绕不开的话题，今天和大家一起聊聊。

1. 索引

索引是对数据库表中一列或多列的值进行排序的一种结构。 MySQL索引的建立对于MySQL的高效运行是很重要的，索引可以大大提高MySQL的检索速度。索引只是提高效率的一个因素，如果你的MySQL有大数据量的表，就需要花时间研究建立最优秀的索引，或优化查询语句。

简单类比一下，数据库如同书籍，索引如同书籍目录，假如我们需要从书籍查找与 xx 相关的内容，我们可以直接从目录中查找，定位到 xx 内容所在页面，如果目录中没有 xx 相关字符或者没有设置目录（索引），那只能逐字逐页阅读文本查找，效率可想而知。

1.1 索引优缺点

优点：

以常见的B+树索引为例，按照顺序存储数据。总结来看有如下三个优点：

缺点：

1.2 索引的原理

MySQL中的数据是保存在磁盘上的，引入索引的目的就是提高访问磁盘上数据的效率。

那么这里先简单介绍一下磁盘IO和预读，磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分。

• 寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下；
• 旋转延迟就是硬盘通过盘片的旋转，使得要读取的扇区转到读写头的下方所需要花费的时间的平均值，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120 / 2 = 4.17ms；
• 传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。

那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右，听起来还挺不错的，但要知道一台500 -MIPS的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。

如果有一种数据结构，每次查找数据时把磁盘IO次数控制在一个很小的数量级，最好是常数数量级，这样就能大大提高数据的访问效率，在这种背景下，索引应运而生。

在数据库中，索引是分很多种类的。而不同的种类很显然是为了应付不同的场合，这里介绍几种常见的索引底层数据结构。

Hash表

哈希表是做数据快速检索的有效利器。哈希算法也叫散列算法，就是把任意值(key)通过哈希函数变换为固定长度的 key 地址，然后通过这个地址来获取具体数据。

但是哈希算法有个数据碰撞的问题，也就是哈希函数可能对不同的 key 会计算出同一个结果，解决碰撞问题的一个常见处理方式就是链地址法或者当链表过长时转为红黑树（JDK1.8的HashMap的处理方法）。

哈希算法只需要计算一次就可以获取到对应的数据，检索速度非常快。但是 Mysql 并没有采取哈希作为其底层算法，因为哈希算法没办法做数据高效范围查找，因此不适合作为MySQL的底层索引结构。

自适应Hash索引

自适应Hash索引（Adatptive Hash Index，内部简称AHI）是InnoDB的三大特性之一，还有两个是 Buffer Pool简称BP、双写缓冲区 Doublewrite Buffer。

自适应Hash索引 = 自适应 + hash索引： 1、自适应即我们不需要自己处理，当InnoDB引擎根据查询统计发现某一查询满足hash索引的数据结构特点，就会给其建立一个hash索引；2、hash索引底层的数据结构是散列表（Hash表），其数据特点就是比较适合在内存中使用，自适应Hash索引存在于InnoDB架构中的缓存中（不存在于磁盘架构中），见下面的InnoDB架构图

Innodb存储引擎会监控对表上二级索引的查找，如果发现某二级索引被频繁访问，二级索引成为热数据，建立哈希索引可以带来速度的提升，则：

经常访问的二级索引数据会自动被生成到hash索引里面去(最近连续被访问三次的数据)，自适应哈希索引通过缓冲池的B+树构造而来，因此建立的速度很快。

InnoDB的自适应Hash索引是默认开启的，可以通过配置参数设置：innodb_adaptive_hash_index = off进行关闭。

自适应Hash算法的也有明显的缺点：

1、hash自适应索引会占用innodb buffer pool；
2、自适应hash索引只适合搜索等值的查询，如select * from table where index_col='xxx'，而对于其他查找类型，如范围查找，是不能使用的；
3、极端情况下，自适应hash索引才有比较大的意义，可以降低逻辑读。

二叉查找树

二叉查找树是一种支持数据快速查找的数据结构，如图下所示:

二叉查找树的时间复杂度是 O(logN)，也可以实现范围查找，但是普通的二叉查找树有个致命缺点：极端情况下会退化为线性链表，二分查找也会退化为遍历查找，时间复杂退化为 O（N），检索性能急剧下降。

在数据库中，数据的自增是一个很常见的形式，比如一个表的主键是 id，而主键一般默认都是自增的，如果采取二叉树这种数据结构作为索引，那上面介绍到的不平衡状态导致的线性查找的问题必然出现。因此，简单的二叉查找树存在不平衡导致的检索性能降低的问题，是不能直接用于实现 Mysql 底层索引的。

红黑树

红黑树是一种自平衡二叉查找树，通过在插入和删除节点时进行颜色变换和旋转操作，使得树始终保持平衡状态，它具有以下特点：

红黑树并不追求严格的平衡，而是大致的平衡，一定程度上解决了二叉查找树可能的平衡问题。但是红黑树的平衡性相对较弱，可能会导致树的高度较高，也会导致一些数据需要进行多次磁盘 IO 操作才能查询到，这也是 MySQL 没有选择红黑树的主要原因。（在数据库中主键自增，主键一般都是数百万数千万的，这种情况下可能导致红黑树一直存在右倾的趋势，长此以往严重影响查询性能）

因为红黑树在插入和删除节点时只需进行 O(1) 次数的旋转和变色操作，即可保持基本平衡状态，TreeMap、TreeSet 以及 JDK1.8 的 HashMap 底层都用到了红黑树。

AVL树

AVL 树的特点是保证任何节点的左右子树高度之差不超过 1，因此也被称为高度平衡二叉树，它的查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logN)。

AVL树采用了旋转操作来保持平衡，虽然解决了二叉查找树可能存在的不平衡问题，但是需要频繁地进行旋转操作（复杂度O（logN））来保持平衡，因此会有较大的计算开销进而降低了查询性能。

而且在使用 AVL 树时，每个树节点仅存储一个数据，而每次进行磁盘 IO 时只能读取一个节点的数据，如果需要查询的数据分布在多个节点上，那么就需要进行多次磁盘 IO。

磁盘 IO 有个有个特点，就是从磁盘读取 1B 数据和 1KB 数据所消耗的时间是基本一样的，我们就可以根据这个思路，我们可以在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这就是 B 树，B+树的的设计原理了。

B树

下面这个 B 树，每个节点限制最多存储两个 key，一个节点如果超过两个 key 就会自动分裂。比如下面这个存储了 7 个数据 B 树，只需要查询两个节点就可以知道 id=7 这数据的具体位置，也就是两次磁盘 IO 就可以查询到指定数据，优于 AVL 树。

下面是一个存储了 16 个数据的 B 树，同样每个节点最多存储 2 个 key，查询 id=16 这个数据需要查询比较 4 个节点，也就是经过 4 次磁盘 IO。看起来查询性能与 AVL 树一样。

但是考虑到磁盘 IO 读一个数据和读 100 个数据消耗的时间基本一致，那我们的优化思路就可以改为：尽可能在一次磁盘 IO 中多读一点数据到内存。这个直接反映到树的结构就是，每个节点能存储的 key 可以适当增加。

当我们把单个节点限制的 key 个数设置为 6 之后，一个存储了 7 个数据的 B 树，查询 id=7 这个数据所要进行的磁盘 IO 为 2 次。

一个存储了 16 个数据的 B 树，查询 id=7 这个数据所要进行的磁盘 IO 为 2 次。相对于 AVL 树而言磁盘 IO 次数降低为一半。

所以数据库索引数据结构的选型而言，B 树是一个很不错的选择。总结来说，B 树用作数据库索引有以下优点：

• 优秀检索速度，时间复杂度：B 树的查找性能等于 O（h * logN），其中 h 为树高，n 为每个节点关键词的个数；
• 尽可能少的磁盘 IO，加快了检索速度；
• 可以支持范围查找。

B+树

为了进一步的树的高度，在每一个节点内存储更多的数据，引入B+树来解决这个问题。

相比B树，B+树有几个特点：

• B 树一个节点里存的是数据，而 B+树存储的是索引（地址），所以 B+树一个节点能存很多索引。
• B+树叶子节点会存放所有的数据，而所有叶子节点之间，用了一个链表串联起来，便于基于范围查找。

通过 B 树和 B+树的对比我们看出，B+树节点存储的是索引，在单个节点存储容量有限的情况下，单节点也能存储大量索引，使得整个 B+树高度降低，减少了磁盘 IO。其次，B+树的叶子节点是真正数据存储的地方，叶子节点用了链表连接起来，这个链表本身就是有序的，在数据范围查找时，更具备效率。因此 Mysql 的索引用的就是 B+树，B+树在查找效率、范围查找中都有着非常不错的性能。

为什么选择B+树来实现索引？

总结来讲，主要有以下4点原因：

• B+ 树的层级更少：相较于 B 树 B+ 每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快
• B+ 树查询速度更稳定：B+ 所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
• B+ 树天然具备排序功能：B+ 树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
• B+ 树全节点遍历更快：B+ 树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像 B 树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B+树一个节点有多大？3层B+树能存放多少数据？

InnoDB存储引擎也有自己的最小储存单元——页（Page），一个页的大小默认是16K。B+树一个节点的大小设为一页或页的倍数最为合适。因为如果一个节点的大小 < 1页，那么读取这个节点的时候其实读取的还是一页，这样就造成了资源的浪费。 在 MySQL 中 B+ 树的一个节点大小为“1页”，也就是16K。之所以设置为一页，是因为对于大部分业务，一页就足够了。

mysql> show variables like 'innodb_page_size';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+

接下来可以大概估计下3层B+树能存放多少数据，首先InnoDB的B+树中，非叶子节点存的是key + 指针；叶子节点存的是数据行。
对于叶子节点，如果一行数据大小为1k，那么一页就能存16条数据；对于非叶子节点，如果key使用的是bigint，则为8字节，指针在mysql中为6字节，一共是14字节，则16k能存放 16 * 1024 / 14 = 1170 个索引指针。于是可以算出，对于一颗高度为2的B+树，根节点存储索引指针节点，那么它有1170个叶子节点存储数据，每个叶子节点可以存储16条数据，一共 1170 x 16 = 18720 条数据，具体可以参考下图。

而对于高度为3的B+树，就可以存放 1170 x 1170 x 16 = 21902400 条数据（两千多万条数据），也就是对于两千多万条的数据，我们只需要高度为3的B+树就可以完成，通过主键查询只需要3次IO操作就能查到对应数据。所以在 InnoDB 中B+树高度一般为3层时，就能满足千万级的数据存储，所以一个节点为1页，也就是16k是比较合理的。

MyISM和InnoDB中的索引实现

这两个引擎底层数据和索引的组织方式并不一样，MyISAM 引擎把数据和索引分开了，一人一个文件，这叫做非聚集索引方式；Innodb 引擎把数据和索引放在同一个文件里了，这叫做聚集索引方式。从两者建表之后生成的文件就可以看出来：

Innodb 创建表后生成的文件有：

• frm:创建表的语句
• idb:表里面的数据+索引文件

MyISAM 创建表后生成的文件有：

• frm:创建表的语句
• MYD:表里面的数据文件（myisam data）
• MYI:表里面的索引文件（myisam index）

1. MyISAM引擎的底层实现（非聚集索引方式）

MyISAM 用的是非聚集索引方式，即数据和索引落在不同的两个文件上。MyISAM 在建表时以主键作为 KEY 来建立主索引 B+树，树的叶子节点存的是对应数据的物理地址。我们拿到这个物理地址后，就可以到 MyISAM 数据文件中直接定位到具体的数据记录了。

当我们为某个字段添加索引时，我们同样会生成对应字段的索引树，该字段的索引树的叶子节点同样是记录了对应数据的物理地址，然后也是拿着这个物理地址去数据文件里定位到具体的数据记录。

2. InnoDB 引擎的底层实现（聚集索引方式）

InnoDB 是聚集索引方式，因此数据和索引都存储在同一个文件里。首先 InnoDB 会根据主键 ID 作为 KEY 建立索引 B+树，如左下图所示，而 B+树的叶子节点存储的是主键 ID 对应的数据，比如在执行 select * from user_info where id=15 这个语句时，InnoDB 就会查询这颗主键 ID 索引 B+树，找到对应的 user_name='Bob'。

这是建表的时候 InnoDB 就会自动建立好主键 ID 索引树，这也是为什么 Mysql 在建表时要求必须指定主键的原因。当我们为表里某个字段加索引时 InnoDB 会怎么建立索引树呢？比如我们要给 user_name 这个字段加索引，那么 InnoDB 就会建立 user_name 索引 B+树，节点里存的是 user_name 这个 KEY，叶子节点存储的数据的是主键 KEY。拿到主键 KEY 后，InnoDB 才会去主键索引树里根据刚在 user_name 索引树找到的主键 KEY 查找到对应的数据。

总结对比

InnoDB 和 MyISAM 相比而言，MyISAM 查询性能更好。MyISAM 直接找到物理地址后就可以直接定位到数据记录，但是 InnoDB 查询到叶子节点后，还需要再查询一次主键索引树，才可以定位到具体数据（针对非主键的查询）。等于 MyISAM 一步就查到了数据，但是 InnoDB 要两步，那当然 MyISAM 查询性能更高。

InnoDB中的主键索引为聚集索引，其他索引均为非聚集索引。主要原因在于，一个表里可能有很多个索引，InnoDB 都会给每个加了索引的字段生成索引树，如果每个字段的索引树都存储了具体数据，那么这个表的索引数据文件就会非常大，有很多数据冗余。采用现有的设计方案，能够在牺牲较少查询性能的前提下，节省大量的磁盘空间。另外，如果和MyISAM一样在主键索引和辅助索引的叶子节点中都存放数据指针，一旦数据发生迁移，则需要去重新组织维护所有的索引，这也会产生巨大的开销。

1.3 索引分类

按照数据结构维度划分：

• BTree 索引：MySQL 里默认和最常用的索引类型。只有叶子节点存储 value，非叶子节点只有指针和 key。存储引擎 MyISAM 和 InnoDB 实现 BTree 索引都是使用 B+Tree，但二者实现方式不一样（前面已经介绍了）。
• 哈希索引：类似键值对的形式，一次即可定位。
• RTree 索引：一般不会使用，仅支持 geometry 数据类型，优势在于范围查找，效率较低，通常使用搜索引擎如 ElasticSearch 代替。
• 全文索引：对文本的内容进行分词，进行搜索。目前只有 CHAR、VARCHAR ，TEXT 列上可以创建全文索引。一般不会使用，效率较低，通常使用搜索引擎如 ElasticSearch 代替。

按照物理存储方式划分：

• 聚簇索引（聚集索引）：索引结构和数据一起存放的索引，InnoDB 中的主键索引就属于聚簇索引。
• 非聚簇索引（非聚集索引）：索引结构和数据分开存放的索引，二级索引(辅助索引)就属于非聚簇索引。MySQL 的 MyISAM 引擎，不管主键还是非主键，使用的都是非聚簇索引。

按照应用维度划分：

• 主键索引：加速查询 + 列值唯一（不可以有 NULL）+ 表中只有一个。
• 普通索引：仅加速查询。
• 唯一索引：加速查询 + 列值唯一（可以有 NULL）。
• 覆盖索引：一个索引包含（或者说覆盖）所有需要查询的字段的值。
• 联合索引：多列值组成一个索引，专门用于组合搜索，其效率大于索引合并。
• 全文索引：对文本的内容进行分词，进行搜索。目前只有 CHAR、VARCHAR ，TEXT 列上可以创建全文索引。一般不会使用，效率较低，通常使用搜索引擎如 ElasticSearch 代替。

聚集索引与非聚集索引

聚集索引和非聚集索引的根本区别是表记录的排列顺序和与索引的排列顺序是否一致。聚集索引的叶节点就是数据节点。而非聚簇索引的叶节点仍然是索引节点，只不过有一个指针指向对应的数据块

1. 聚簇索引（Clustered Index）：聚集索引表记录的排列顺序和索引的排列顺序一致（以InnoDB聚集索引的主键索引来说，叶子节点中存储的就是行数据，行数据在物理储器中的真实地址就是按照主键索引树形成的顺序进行排列的），所以查询效率快，只要找到第一个索引值记录，其余就连续性的记录在物理也一样连续存放。

聚集索引对应的缺点就是修改慢，因为为了保证表中记录的物理和索引顺序一致，在记录插入的时候，会对数据页重新排序（因为在真实物理存储器的存储顺序只能有一种，而插入新数据必然会导致主键索引树的变化，主键索引树的顺序发生了改变，叶子节点中存储的行数据也要随之进行改变，就会发生大量的数据移动操作，所以效率会慢）。因为在物理内存中的顺序只能有一种，所以聚集索引在一个表中只能有一个。

2. 非聚簇索引（Clustered Index）：非聚集索引制定了表中记录的逻辑顺序，但是记录的物理和索引不一定一致（在逻辑上数据是按顺序排存放的，但是物理上在真实的存储器中是散列存放的），两种索引都采用B+树结构，非聚集索引的叶子层并不和实际数据页相重叠，而采用叶子层包含一个指向表中的记录在数据页中的指针方式。

非聚集索引层次多，不会造成数据重排。所以如果表的读操作远远多于写操作，那么就可以使用非聚集索引。但非聚集索引有一个很大的缺点就是可能产生二次查询，也就是回表， 当查到索引对应的指针或主键后，可能还需要根据指针或主键再到数据文件或表中查询。

主键索引

数据表的主键列使用的就是主键索引。一张数据表有只能有一个主键，并且主键不能为 null，不能重复。

在 MySQL 的 InnoDB 的表中，当没有显示的指定表的主键时，InnoDB 会自动先检查表中是否有唯一索引且不允许存在 null 值的字段，如果有，则选择该字段为默认的主键，否则 InnoDB 将会自动创建一个 6Byte 的自增主键。

二级索引（辅助索引）

二级索引（Secondary Index）又称为辅助索引，是因为二级索引的叶子节点存储的数据是主键。也就是说，通过二级索引，可以定位主键的位置。

唯一索引，普通索引，前缀索引等索引属于二级索引。

覆盖索引和联合索引

覆盖索引： 如果一个索引包含 （或者说覆盖）所有需要查询的字段的值，我们就称之为 覆盖索引（Covering Index） 。我们知道在 InnoDB 存储引擎中，如果不是主键索引，叶子节点存储的是主键+列值。最终还是要“回表”，也就是要通过主键再查找一次，这样就会比较慢。而覆盖索引直接从辅助索引中就能得到查询的记录，而不需要查询聚集索引中的记录。

这里举个例子，我们有一张user表，Id列上有主键索引，同时在Name列上建立了辅助索引，

如上图，如果通过name进行数据检索：

select * from users where name = ?

需要需要在name索引中找到name对应的Id，然后通过获取的Id在主键索引中查到对应的行。整个过程需要扫描两次索引，一次name，一次id。如果我们查询只想查询id的值，就可以改写SQL为：

select id from users where name = ?

因为只需要id的值，通过name查询的时候，扫描完name索引，我们就能够获得id的值了，所以就不需要再去扫面id索引，就会直接返回。当然，如果你同时需要获取age的值：

select id，age from users where name = ?

这样就无法使用到覆盖索引了。

知道了覆盖索引，就知道了为什么sql中要求尽量不要使用select *，要写明具体要查询的字段。其中一个原因就是在使用到覆盖索引的情况下，不需要进入到数据区，数据就能直接返回，提升了查询效率。在用不到覆盖索引的情况下，也尽可能的不要使用select *，如果行数据量特别多的情况下，可以减少数据的网络传输量。

联合索引： 指对表上的多个列进行索引，在使用联合索引进行查询时，会遵守下面提到的最左匹配原则。

为什么要使用联合索引 ？

1. 减少开销。建一个联合索引 (col1,col2,col3)，实际相当于建了 (col1)，(col1,col2)，(col1,col2,col3) 三个索引。每多一个索引，都会增加写操作的开销和磁盘空间的开销。对于大量数据的表，使用联合索引会大大的减少开销！
2. 覆盖索引。对联合索引 (col1,col2,col3)，如果有如下的 SQL：select col1,col2,col3 from test where col1=1 and col2=2;。那么 MySQL 可以直接通过遍历索引取得数据，而无需回表，这减少了很多的随机 IO 操作。减少 IO 操作，特别的随机 IO 其实是 DBA 主要的优化策略。所以，在真正的实际应用中，覆盖索引是主要的提升性能的优化手段之一。
3. 效率高。索引列越多，通过索引筛选出的数据越少。有 1000W 条数据的表，有如下 SQL：select from table where col1=1 and col2=2 and col3=3，假设假设每个条件可以筛选出 10% 的数据，如果只有单值索引，那么通过该索引能筛选出 1000W10%=100w 条数据，然后再回表从 100w 条数据中找到符合 col2=2 and col3=3 的数据，然后再排序，再分页；如果是联合索引，通过索引筛选出 1000w * 10% * 10% * 10% =1w，效率提升可想而知！

最左匹配原则：

最左前缀匹配原则指的是，在使用联合索引时，MySQL 会根据联合索引中的字段顺序，从左到右依次到查询条件中去匹配，如果查询条件中存在与联合索引中最左侧字段相匹配的字段，则就会使用该字段过滤一批数据，直至联合索引中全部字段匹配完成，或者在执行过程中遇到范围查询（如 >、=、 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，因为c字段是一个范围查询，它之后的字段会停止匹配。

alter table user add index index1(email) 
alter table user add index index2(email(6))