你真的理解索引吗？从数据结构层面解析mysql索引原理

2023-07-28 16:08:28

从《mysql存储引擎InnoDB详解，从底层看清InnoDB数据结构》中，我们已经知道了数据页内各个记录是按主键正序排列并组成了一个单向链表的，并且各个数据页之间形成了双向链表。在数据页内，通过页目录，根据主键可以快速定位到一条记录。这一章中，我们深入理解一下mysql索引实现。

本文主要内容是根据掘金小册《从根儿上理解 MySQL》整理而来。如想详细了解，建议购买掘金小册阅读。

索引数据结构

先回顾一下上一章节中数据页基本结构：

从上图可以推断出，查询某条记录关键步骤只有2个：

定位到数据页
定位到记录

如果没有索引，查询某条记录只能先依次遍历数据页，确定记录所在的数据页之后；再从数据页中通过页目录定位到具体的记录，这样做效率肯定是很低的。

为了方便说明，先建一张示例表：

mysql> CREATE TABLE index_demo(
    ->     c1 INT,
    ->     c2 INT,
    ->     c3 CHAR(1),
    ->     PRIMARY KEY(c1)
    -> ) ROW_FORMAT = Compact;
Query OK, 0 rows affected (0.03 sec)

为了展示便方便，行格式中只展示record_type、next_record和实际各列的值。

把一些记录放到页里边的示意图就是：

上面提到过，数据页中的记录是按主键正序排列的。实际上就是为了能够使用二分查找法快速定位一条记录。同理，要想快速定位一个数据页，也得保证各个数据页是按顺序排序的。排序的规则就是后一个数据页的最小主键必须大于当前数据页的最大主键。这样实际上就保证了，所有记录的主键都是正序排列的了。

页分裂

假设每个数据页最多只能存放3条记录。现在index_demo插入了3条记录 (1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y')。

然后，再向index_demo插入一条记录(4, 4, 'a')。由于每个数据页最多只能存放3条记录，并且还要保证所有记录主键是按主键正序排列的。mysql会新建一个页面(假设是页28)，然后将主键值为5的记录移动到页28中，最后再把主键值为4的记录插入到页10中。

简单来说，当向一个已经存满记录的数据页插入新记录时，mysql会以新插入记录的位置为界，把当前页面分裂为2个页面，最后再将新记录插入进去。

mysql索引实现

假设index_demo已经存在多条记录，数据页结构如下所示：

为了能够使用二分法快速查找数据页，我们可以给每个数据页建一个目录项，每个目录项主要包含两部分数据：

页的用户记录中最小的主键值，我们用key来表示。
页号，我们用page_no表示。

在mysql中，这些目录项其实就是另一类型的数据记录，称为目录项数据记录（record_type=1）,目录项数据记录也是存储在页中的，同一页中的目录项数据记录也可以通过页目录快速定位。

虽然目录项记录基本只存储了主键值和页号。但是当表中的数据很多时，一个数据页肯定是无法保存所有的目录项记录的。因此存储目录项记录的数据页实际上可能有很多个。

这个时候，我们就需要快速定位存储目录项记录的数据页了。实际上，我们只需要生成更高级的目录即可，同时保证最高一级的目录项记录的数据页只有一个。这样就能根据主键从上到下快速定位到一条记录了。

实际上，上面的结构就是一颗B+树。实际的用户记录其实都存放在B+树的叶子节点上，而非叶子节点存放的是目录项。

聚簇索引

上面介绍的索引实际上就是聚簇索引，它有两个特点：

使用主键值的大小进行记录和页的排序，这包括三个方面的含义：
1. 页内的记录是按照主键的大小顺序排成一个单向链表。
2. 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
3. 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
B+树的叶子节点存储的是完整的用户记录。

InnoDB存储引擎会自动根据主键创建聚簇索引。同时，聚簇索引就是InnoDB存储引擎中数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。

二级索引

在实际场景中，我们更多的是为某个列建立二级索引。实际上，二级索引和聚簇索引实现的原理一样的。主要的区别只有2个：

使用索引列的值的大小进行记录和页的排序。
B+树的叶子节点存储的是对应记录的主键值。

如图是以c2列建立的二级索引：

由于B+树的叶子节点存储的是对应记录的主键值。如果我们要查询完成记录的话，在拿到主键之后，再需要再到聚簇索引中查出用户记录，这个过程也叫回表。

联合索引

在实际场景中，经常也出现为多个列建立一个索引的情况，这种索引也称为联合索引。联合索引本质上也是二级索引，区别仅仅在于由一个列变为多个列而已。简单来说就是同时以多个列的大小作为排序规则，也就是同时为多个列建立索引。比如我们为c2和c3列建立联合索引：

先把各个记录和页按照c2列进行排序。
在记录的c2列相同的情况下，采用c3列进行排序。

InnoDB的B+树索引的注意事项

根节点不变性

上面介绍B+树的时候，为了理解方便，采用自下而上的方式介绍。实际上，B+树的形成过程如下：

每次为某个表创建B+索引的时候，都会为这个索引创建一个根节点页面。当表中没有记录时，每个B+根节点既没有用户记录，也没有目录项记录。
随后向表中插入用户记录时，先把用户记录存储到根节点中。
当根节点空间用完后，再次插入数据。会将根节点数据复制到一个新页中，再对这个新页进行页分裂操作。此时，根节点自动升级为存储目录项记录的页。

可以看出，一个B+树索引的根节点自诞生之日起，便不会再移动。

内节点中目录项记录的唯一性

我们知道B+树索引的内节点中目录项记录的内容是索引列+页号的搭配，但是这个搭配对于二级索引来说有点儿不严谨。为了保证内节点目录项记录的唯一性，目录项还需要存储主键值数据。也就是说，目录项记录的内容包含索引列的值、主键值和页号。

MyISAM中的索引方案简单介绍

我们知道InnoDB中索引即数据，也就是聚簇索引的那棵B+树的叶子节点中已经把所有完整的用户记录都包含了，而MyISAM的索引方案虽然也使用树形结构，但是却将索引和数据分开存储：

MyISAM存储引擎把记录按照记录的插入顺序单独存储在数据文件中。这个文件并不划分为若干个数据页，有多少记录就往这个文件中塞多少记录就成了。我们可以通过行号而快速访问到一条记录。
MyISAM存储引擎会把索引信息另外存储到索引文件中。MyISAM会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值+行号的组合。也就是先通过索引找到对应的行号，再通过行号去找对应的记录！
这一点和InnoDB是完全不相同的，在InnoDB存储引擎中，我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录。而在MyISAM中却需要进行一次回表操作，意味着MyISAM中建立的索引相当于全部都是二级索引！
如果有需要的话，我们也可以对其它的列分别建立索引或者建立联合索引，原理和InnoDB中的索引差不多，不过在叶子节点处存储的是相应的列+行号。这些索引也全部都是二级索引。

索引的使用

上面介绍了B+索引的原理，接下来介绍如何更好的使用索引。大家都知道索引不是建的越多越好，因为创建索引在空间上和时间上都会付出代价。

空间上的代价
每创建一个索引，本质上就是要建立一个B+树，创建索引肯定会占用一部分存储空间。
时间上的代价
每次对表中的数据进行增删改操作时，都需要去修改各个B+树索引，而B+树索引的记录又是按照索引列的值排序的。每次增删改操作时，不可避免的会破坏原有记录的顺序，所以存储引擎需要额外的时间来进行记录移位、页面分裂等操作来维护记录的顺序。

简单来说，一张表的索引越多，占用的存储空间也会越多，增删改的性能会更差。

B+树索引适用的条件

首先创建一张示例表person_info，用来存储人的一些基本信息。

CREATE TABLE person_info(
    id INT NOT NULL auto_increment,
    name VARCHAR(100) NOT NULL,
    birthday DATE NOT NULL,
    phone_number CHAR(11) NOT NULL,
    country varchar(100) NOT NULL,
    PRIMARY KEY (id),
    KEY idx_name_birthday_phone_number (name, birthday, phone_number)
);

简要说明一下：

id列为主键，自动递增。InnoDB会自动为id列建立聚簇索引。
为name, birthday, phone_number建立了一个联合索引。所以这个二级索引的叶子节点包含了name, birthday, phone_number和id列的值。

下面，简要画一下idx_name_birthday_phone_number联合索引的示意图。

从图中可以看出，这个idx_name_birthday_phone_number索引对应的B+树中页面和记录的排序方式就是这样的：

先按照name列的值进行排序。
如果name列的值相同，则按照birthday列的值进行排序。
如果birthday列的值也相同，则按照phone_number的值进行排序。

全值匹配

全值匹配指的是搜索条件中的列和索引列一致。比如：

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27' AND phone_number = '15123983239';

在idx_name_birthday_phone_number联合索引上进行全值匹配的查询过程如下：

因为B+树的数据页和记录先是按照name列的值进行排序的，所以先可以很快定位name列的值是Ashburn的记录位置。
在name列相同的记录里又是按照birthday列的值进行排序的，所以在name列的值是Ashburn的记录里又可以快速定位birthday列的值是'1990-09-27'的记录。
如果name和birthday列的值都是相同的，那记录是按照phone_number列的值排序的，所以联合索引中的三个列都可能被用到。

联合索引最左匹配

其实在搜索语句中不用包含全部联合索引的列，只包含左边的列也能够使用索引，这就是联合索引的最左匹配原则。比如：

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27';

如果我们想使用联合索引中尽可能多的列，搜索条件中的各个列必须是联合索引中从最左边连续的列。

前缀匹配

对于字符串类型的索引列来说，我们只匹配它的前缀也是可以快速定位记录的。因为字符串比较本质上按一个一个字符比较得出的，也就是说这些字符串的前n个字符，也就是前缀都是排好序的。比如：

SELECT * FROM person_info WHERE name LIKE 'As%';

但是如果只给出后缀或者中间的某个字符串，是无法使用索引的，比如这样：%As或者%As%。如果实际场景中碰到要以字符串后缀查询数据的话，可以考虑逆序存储，将后缀匹配转化为前缀匹配。

范围匹配

因为索引B+树是按照索引列大小排序的，因此按索引列范围查询可以快速查询出数据记录。比如：

SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';

由于B+树中的数据页和记录是先按name列排序的，所以我们上边的查询过程其实是这样的：

找到name值为Asa的记录。
找到name值为Barlow的记录。
由于叶子节点记录本身是一个链表，直接取出范围之内的记录。
回表查询完整记录。

精确匹配某一列并范围匹配另外一列

对于同一个联合索引来说，虽然对多个列都进行范围查找时只能用到最左边那个索引列，但是如果左边的列是精确查找，则右边的列可以进行范围查找，这种场景下依然会使用索引。

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday > '1980-01-01' AND birthday < '2000-12-31' AND phone_number > '15100000000';

整个查询过程大致如下：

name = 'Ashburn'，对name列进行精确查找，当然可以使用B+树索引了。
birthday > '1980-01-01' AND birthday < '2000-12-31'，由于name列是精确查找，所以通过name = 'Ashburn'条件查找后得到的结果的name值都是相同的，它们会再按照birthday的值进行排序。所以此时对birthday列进行范围查找是可以用到B+树索引的。
phone_number > '15100000000'，通过birthday的范围查找的记录的birthday的值可能不同，所以这个条件无法再利用B+树索引了，只能遍历上一步查询得到的记录。

用于排序

在实际业务场景中，经常需要对查询出来的结果进行排序。一般情况下，只能将记录全部加载到内存中（结果集太大可能使用磁盘存放中间结果），再使用排序算法排序。这种在内存中或者磁盘上的排序方式统称为文件排序filesort，性能较差。但是如果order by子句使用到了索引列，就可能避免filesort。比如下面这个查询语句：

SELECT * FROM person_info ORDER BY name, birthday, phone_number LIMIT 10;

这个查询结果依次按name、birthday和phone_number排序，而idx_name_birthday_phone_numberB+索引树也刚好是按上述规则排好序的，因此只需要直接从索引中提取数据，然后回表即可。
需要注意的是，对于联合索引来说，ORDER BY的子句后边的列的顺序也必须跟索引列的顺序一致，否则排序的时候就无法使用索引了。

用于分组

有时候我们为了方便统计表中的一些信息，会把表中的记录按照某些列进行分组。比如下边这个分组查询：

SELECT name, birthday, phone_number, COUNT(*) FROM person_info GROUP BY name, birthday, phone_number

和使用B+树索引进行排序是一个道理，分组列的顺序也需要和索引列的顺序一致，也可以只使用索引列中左边的列进行分组。

覆盖索引

上面提到到，所谓回表就是在二级索引中获取到主键id集合之后，再分别到聚簇索引查询出完整记录，简单来说就是一次二级索引查询，多次聚簇索引回表。这意味着二级索引命中的主键记录越多，需要回表的记录也会也多，整体的性能就会越低。因此某些查询，宁可使用全表扫描也不使用二级索引。
为了更好的使用二级索引+回表的方式进行查询，一般推荐使用limit限制要查询的记录，这样回表的次数也能得到控制。

为了彻底告别回表操作带来的性能损耗，建议：在查询列表里只包含索引列，比如这样：

SELECT name, birthday, phone_number FROM person_info WHERE name > 'Asa' AND name < 'Barlow'

因为只查询name, birthday, phone_number这三个索引列的值，所以就没必要进行回表操作了。我们把这种只需要用到索引的查询方式称为覆盖索引。

如何挑选索引

上面主要介绍了索引的适用场景，接下来我们介绍下建立索引时或者编写查询语句时就应该注意的一些事项。

只为用于搜索、排序或分组的列创建索引

只为出现在WHERE子句中的列、连接子句中的连接列，或者出现在ORDER BY或GROUP BY子句中的列创建索引。而出现在查询列表中的列就没必要建立索引了。

考虑列的基数

列的基数指的是某一列中不重复数据的个数。，在记录行数一定的情况下，列的基数越大，该列中的值越分散，列的基数越小，该列中的值越集中。因此推荐的方式是为那些列的基数大的列建立索引，为基数太小列的建立索引效果可能不好。

索引列的类型尽量小

在表示的整数范围允许的情况下，尽量让索引列使用较小的类型。原因如下：

数据类型越小，在查询时进行的比较操作越快
数据类型越小，索引占用的存储空间就越少，在一个数据页内就可以放下更多的记录，从而减少磁盘I/O带来的性能损耗，也就意味着可以把更多的数据页缓存在内存中，从而加快读写效率。

使用前缀索引

当字段值比较长的时候，建立索引会消耗很多的空间，搜索起来也会很慢。我们可以通过截取字段的前面一部分内容建立索引，这个就叫前缀索引。
例如：创建一张商户表，因为地址字段比较长，在地址字段上建立前缀索引:

create table shop(address varchar(120) not null);

问题是，截取多少呢?截取得多了，达不到节省索引存储空间的目的，截取得少了，重复内容太多，字段的基数会降低。实际场景中，可以通过不同长度的基数与总记录数据基数的比值，选择一个较为合理的截取长度。

select count(distinct left(address,10))/count(*) as sub10,
count(distinct left(address,11))/count(*) as sub11,
count(distinct left(address,12))/count(*) as sub12,
count(distinct left(address,13))/count(*) as sub13
from shop;

避免索引列字段参与计算

如果索引列在比较表达式中不是以单独列的形式出现，而是以某个表达式，或者函数调用形式出现的话，是用不到索引的。
比如有一个整数列my_col，WHERE my_col * 2 < 4查询是不会使用索引的，而WHERE my_col < 4/2能正常使用索引。

主键插入顺序

我们知道，对于InnoDB来说，数据实际上是按主键大小正序存储在聚簇索引的叶子节点上的。所以如果我们插入的记录的主键值是依次增大的话，那我们每插满一个数据页就换到下一个数据页继续插入。而如果我们插入的主键值忽大忽小的话，就会造成频繁的页分裂，严重影响性能。因此，为了保证性能，需要保证主键是递增的。

无法使用索引的几种情况

ORDER BY的子句后边的列的顺序也必须跟索引列的顺序不一致。
ASC、DESC混用
排序列包含非同一个索引的列
排序列使用了复杂的表达式
索引列上使用函数(replace\SUBSTR\CONCAT\sum count avg)、表达式、计算(+ - * /)
like 条件中前面带%
字符串不加引号，出现隐式转换

原创不易，觉得文章写得不错的小伙伴，点个赞

码农公寓