MySQL索引原理详解(看这篇就够了)

MySQL索引可以极大的提升查询效率，为什么查询效率高?MySQL索引原理是什么？本篇重点详解。

MySQL索引数据结构

索引是一种高效获取数据的存储结构，所以要理解MySQL索引的原理，必须清楚一种数据结构就是B树或者 B+ 树。

MySQL一般以B+树作为其索引结构，具体有什么特点呢？

• 所有值按顺序存储，每个叶子到根的距离相同；
• 非叶子节点不存储数据，只存储指针索引；
• 叶子节点存储所有数据，不存储指针；
• 每个叶子节点都有指向相邻下一个叶子节点的指针，即顺序访问指针；

好了说了这么多的 B+ 树的特点，我们来张图看看 B+ 树到底长什么样子。

上面的数据页就是实际存放数据页的地方，且数据页之间是通过双向链表进行连接的。

 

B+树的查找过程

我们查询一条语句，会通过B+树来查找数据，过程如图所示：

主要会经历以下4大步骤：

1. 如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO。
2. 在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计。
3. 通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO。
4. 29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。

真实的情况是：3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的。

如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。

通过上面的分析，我们知道IO次数取决于B+数的高度H。

如果数据项占的空间越小，数据项的数量越多，树的高度越低，这就是为什么每个数据项，即索引字段要尽量的小，比如：int占4字节，要比bigint8字节少一半。

这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。

 

磁盘IO与预读

磁盘IO和预读也会涉及到MySQL索引的快慢的问题，也需要了解。

什么是磁盘IO和预读？

磁盘IO和预读就是：磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为：寻道时间、旋转延迟、传输时间三个部分。

1.寻道时间

寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下。

2.旋转延迟

旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms。

3.传输时间

传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。

那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右，听起来还挺不错的。

但要知道数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难，下图是计算机硬件延迟的对比图：

考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内。

因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。

每一次IO读取的数据我们称之为一页：page，具体一页有多大数据跟操作系统有关，一般为4k或8k。

也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。

 

MyISAM索引

MyISAM是MySQL 5.5之前的默认存储引擎，MyISAM索引文件和数据文件是分离的，即为非聚集索引。

非聚集索引的叶子层并不和实际数据页相重叠，而采用叶子层包含一个指向表记录的指针。

如下图所示：

如果有一个查询:

select * from user where user.Col1 = 30

如果使用的是索引查询，则会读第一个根节点，查找到30，它处于在5~56中间，则会进行一次I/O操作。

进入到文件中进行找到对应的索引，将读取的文件交给内存执行B+树查找，为没有找到数据则会进行第二次I/O操作，最终读取到了30这个索引值。

索引值存储的是一个索引所在行的磁盘文件地址，这个地址是指向的后缀文件，所以会进行I/O读取后缀的数据表文件读取对应行的值，这就是MyISAM索引引擎底层搜索所经历的流程。

 

Innodb 索引

MySQL 5.5之后的默认存储引擎，就是Innodb 。

InnoDB索引文件是合在一起的，即索引和数据存在一个文件，因此它属于聚集索引。

在聚集索引中，叶结点也即数据结点，所有数据行的存储顺序与索引的存储顺序一致。

聚集索引的好处之一：它对主键的排序查找和范围查找速度非常快，叶子节点的数据就是用户所要查询的数据。

如用户需要查找一张表，查询最后的10位用户信息，由于B+树索引是双向链表，所以用户可以快速找到最后一个数据页，并取出10条记录。

#参照第六小结测试索引的准备阶段来创建出表s1
mysql> desc s1; #最开始没有主键
+--------+-------------+------+-----+---------+-------+
| Field  | Type        | Null | Key | Default | Extra |
+--------+-------------+------+-----+---------+-------+
| id     | int(11)     | NO   |     | NULL    |       |
| name   | varchar(20) | YES  |     | NULL    |       |
| gender | char(6)     | YES  |     | NULL    |       |
| email  | varchar(50) | YES  |     | NULL    |       |
+--------+-------------+------+-----+---------+-------+
rows in set (0.00 sec)

mysql> explain select * from s1 order by id desc limit 10; #Using filesort，需要二次排序
+----+-------------+-------+------------+------+---------------+------+---------+------+---------+----------+----------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows    | filtered | Extra          |
+----+-------------+-------+------------+------+---------------+------+---------+------+---------+----------+----------------+
|  1 | SIMPLE      | s1    | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 2633472 |   100.00 | Using filesort |
+----+-------------+-------+------------+------+---------------+------+---------+------+---------+----------+----------------+
row in set, 1 warning (0.11 sec)

mysql> alter table s1 add primary key(id); #添加主键
Query OK, 0 rows affected (13.37 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> explain select * from s1 order by id desc limit 10; #基于主键的聚集索引在创建完毕后就已经完成了排序，无需二次排序
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+-------+
| id | select_type | table | partitions | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+-------+
|  1 | SIMPLE      | s1    | NULL       | index | NULL          | PRIMARY | 4       | NULL |   10 |   100.00 | NULL  |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+-------+
row in set, 1 warning (0.04 sec)

聚集索引的好处之二：范围查询（range query），即如果要查找主键某一范围内的数据，通过叶子节点的上层中间节点就可以得到页的范围，之后直接读取数据页即可。

mysql> alter table s1 drop primary key;
Query OK, 2699998 rows affected (24.23 sec)
Records: 2699998  Duplicates: 0  Warnings: 0

mysql> desc s1;
+--------+-------------+------+-----+---------+-------+
| Field  | Type        | Null | Key | Default | Extra |
+--------+-------------+------+-----+---------+-------+
| id     | int(11)     | NO   |     | NULL    |       |
| name   | varchar(20) | YES  |     | NULL    |       |
| gender | char(6)     | YES  |     | NULL    |       |
| email  | varchar(50) | YES  |     | NULL    |       |
+--------+-------------+------+-----+---------+-------+
rows in set (0.12 sec)

mysql> explain select * from s1 where id > 1 and id < 1000000; #没有聚集索引，预估需要检索的rows数如下
+----+-------------+-------+------------+------+---------------+------+---------+------+---------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows    | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+------+---------+----------+-------------+
|  1 | SIMPLE      | s1    | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 2690100 |    11.11 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+---------+----------+-------------+
row in set, 1 warning (0.00 sec)

mysql> alter table s1 add primary key(id);
Query OK, 0 rows affected (16.25 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> explain select * from s1 where id > 1 and id < 1000000; #有聚集索引，预估需要检索的rows数如下
+----+-------------+-------+------------+-------+---------------+---------+---------+------+---------+----------+-------------+
| id | select_type | table | partitions | type  | possible_keys | key     | key_len | ref  | rows    | filtered | Extra       |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+---------+----------+-------------+
|  1 | SIMPLE      | s1    | NULL       | range | PRIMARY       | PRIMARY | 4       | NULL | 1343355 |   100.00 | Using where |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+---------+----------+-------------+
row in set, 1 warning (0.09 sec)

作者简介

陈睿|mikechen，10年+大厂架构经验，BAT资深面试官，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

👇阅读更多mikechen架构文章👇

阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师

以上

关注作者「mikechen」公众号，获取更多技术干货！

后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》