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

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

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

MySQL索引数据结构

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

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

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

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

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

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

 

B+树的查找过程

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

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

主要会经历以下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毫秒的时间,显然是个灾难,下图是计算机硬件延迟的对比图:

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

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

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

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

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

 

MyISAM索引

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

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

如下图所示:

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

如果有一个查询:

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索引文件是合在一起的,即索引和数据存在一个文件,因此它属于聚集索引。

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

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

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

如用户需要查找一张表,查询最后的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」公众号,获取更多技术干货!

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

评论交流
    说说你的看法