浅谈MySQL索引

在前天的面试中，和面试官聊了聊MySQL索引的部分问题，面试官给我讲了很多，下来后查阅了相关资料并做了一个整理

Reference：

聚集索引&非聚集索引

聚集（clustered）索引，也叫聚簇索引：数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。通常：如果我们定义id为主键时，建立了聚集索引。数据行的物理顺序与列值得顺序相同。如果我们查询id比较靠后的数据，那么这行数据的地址在磁盘中的物理地址也会比较靠后。而且由于物理排列顺序方式与聚集索引的顺序相同，索引也就只能建立一个聚集索引。

非聚集（unclustered）索引：该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。其实按照定义，除了聚集索引以外的索引都是非聚集索引。

理解聚集索引和非聚集索引可通过对比汉语字典的索引。汉语字典提供了两类检索汉字的方式，第一类是拼音检索（前提是知道该汉字读音），比如拼音为cheng的汉字排在拼音chang的汉字后面，根据拼音找到对应汉字的页码，这就是我们通常所说的字典序；第二类是部首笔画检索，根据笔画找到对应汉字，查到汉字对应的页码。拼音检索就是聚集索引，因为存储的记录（数据库中是行数据、字典中是汉字的详情记录）是按照该索引排序的；笔画索引，虽然笔画相同的字在笔画索引中相邻，但是实际存储页码却不相邻。

创建索引

如果不创建索引，系统会自动创建一个隐含列作为表的聚集索引。

聚集索引一般是表中的主键索引，如果表中没有显示指定主键，则会选择表中的第一个不允许为NULL的唯一索引，如果还是没有的话，就采用Innodb存储引擎为每行数据内置的6字节ROWID作为聚集索引

create table student (
    `id` INT UNSIGNED AUTO_INCREMENT,
    `name` VARCHAR(255),
    `score` INT UNSIGNED,
    PRIMARY KEY(`id`),
    KEY(`name`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

最好还是在创建表的时候添加聚集索引，由于聚集索引的物理顺序上的特殊性，因此如果再在上面创建索引的时候会根据索引列的排序移动全部数据行上面的顺序，会非常地耗费时间以及性能

查找分析

该表中主键id是该表的聚集索引、name为非聚集索引；表中的每行数据都是按照聚集索引id排序存储的；比如要查找name='Arla'和name='Arle'的两个同学，他们在name索引表中位置可能是相邻的，但是实际存储位置可能差的很远。name索引表节点按照name排序，检索的是每一行数据的主键。聚集索引表按照主键id排序，检索的是每一行数据的真实内容。

非聚集索引的二次查询（回表）

非聚集索引叶节点仍然是索引节点，只是有一个指针指向对应的数据块，此如果使用非聚集索引查询，而查询列中包含了其他该索引没有覆盖的列，那么他还要进行第二次的查询，查询节点上对应的数据行的数据。

比如：

select * from student where name = 'Arle'

查询name='Arle'的记录时，score列没有索引覆盖，需要二次查询。首相通过name索引表查找到Arle的主键id（可能有多个主键id，因为有重名的同学），再根据主键id的聚集索引找到相应的行记录

如何解决非聚集索引的二次查询问题？

复合索引（覆盖索引）：建立两列以上的索引，即可查询复合索引里的列的数据而不需要进行回表二次查询，如index(col1, col2)，执行下面的语句

查找比较

select * from student where id > 5000 and id < 20000

根据id进行范围查询，因为(5000, 20000)范围内的记录在磁盘上按顺序存储，顺序读取磁盘很快就能读到这批数据

select * from student where name > 'Alie' and name < 'John'

查询（'Alie', 'John'）范围内的记录，主键id分布可能是离散的1，100，20001，5000.....；增加了随机读取数据页几率；所以普通索引的范围查询效率被聚集索引甩开几条街都不止；非聚集索引的精确查询效率还是可以的，比聚集索引查询只增加了一次IO开销

总结

使用聚集索引的查询效率要比非聚集索引的效率要高，但是如果需要频繁去改变聚集索引的值，写入性能并不高，因为需要移动对应数据的物理位置。
非聚集索引在查询的时候可以的话就避免二次查询，这样性能会大幅提升。
不是所有的表都适合建立索引，只有数据量大表才适合建立索引，且建立在选择性高的列上面性能会更好。

索引底层数据结构分析

索引（Index）是帮助MySQL高效获取数据的数据结构。索引的本质：索引是数据结构，而且是实现了高级查找算法的数据结构索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作

Hash索引

如果是等值查询，哈希索引明显有绝对优势。 前提：键值唯一
哈希索引没办法完成范围查询检索
哈希索引也没办法利用索引完成排序，以及like ‘xxx%’ 这样的部分模糊查询
哈希索引也不支持多列联合索引的
在有大量重复键值情况下，哈希索引的效率也最左前缀原则是极低的，因为存在哈希碰撞问题

B Tree索引

度(Degree)-节点的数据存储个数
叶子节点具有相同的深度
叶子节点的指针为空
节点中的数据key从左到右递增排列

假如我们要查找id=28的用户信息，那么我们在上图B树中查找的流程如下：

先找到根节点也就是页1，判断28在键值17和35之间，我们那么我们根据页1中的指针p2找到页3
将28和页3中的键值相比较，28在26和30之间，我们根据页3中的指针p2找到页8
将28和页8中的键值相比较，发现有匹配的键值28，键值28对应的用户信息为(28,bv)

B+ Tree索引

非叶子节点不存储data，只存储key，可以增大度：之所以这么做是因为在数据库中页的大小是固定的，innodb中页的默认大小是16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数有会再次减少，数据查询的效率也会更快
叶子节点不存储指针
顺序访问指针，提高区间访问的性能

因为B+树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而B树因为数据分散在各个节点，要实现这一点是很不容易的。

B+树索引就是innodb中B+树索引真正的实现方式

查询分析

select * from user where id >= 18 and id < 40

其中id是主键

一般根节点都是常驻内存的，也就是说页1已经在内存中了，此时不需要到磁盘中读取数据，直接从内存中读取即可。从内存中读取到页1，要查找这个id>=18 and id <40或者范围值，我们首先需要找到id=18的键值。从页1中我们可以找到键值18，此时我们需要根据指针p2，定位到页3
要从页3中查找数据，我们就需要拿着p2指针去磁盘中进行读取页3。从磁盘中读取页3后将页3放入内存中，然后进行查找，我们可以找到键值18，然后再拿到页3中的指针p1，定位到页8
同样的页8页不在内存中，我们需要再去磁盘中将页8读取到内存中。将页8读取到内存中后。因为页中的数据是链表进行连接的，而且键值是按照顺序存放的，此时可以根据二分查找法定位到键值18。此时因为已经到数据页了，此时我们已经找到一条满足条件的数据了，就是键值18对应的数据。因为是范围查找，而且此时所有的数据又都存在叶子节点，并且是有序排列的，那么我们就可以对页8中的键值依次进行遍历查找并匹配满足条件的数据。我们可以一直找到键值为22的数据，然后页8中就没有数据了，此时我们需要拿着页8中的p指针去读取页9中的数据（叶子结点之间有指针链接）
因为页9不在内存中，就又会加载页9到内存中，并通过和页8中一样的方式进行数据的查找，直到将页12加载到内存中，发现41大于40，此时不满足条件。那么查找到此终止
最终我们找到满足条件的所有数据为：(18,kl),(19,kl),(22,hj),(24,io),(25,vg),(29,jk),(31,jk),(33,rt),(34,ty),(35,yu),(37,rt),(39,rt)。总共12条记录

总结

哈希虽然能够提供 O(1) 的单数据行操作性能，但是对于范围查询和排序却无法很好地支持，最终导致全表扫描；
B 树能够在非叶节点中存储数据，但是这也导致在查询连续数据时可能会带来更多的随机 I/O，而 B+ 树的所有叶节点可以通过指针相互连接，能够减少顺序遍历时产生的额外随机 I/O；