本章内容

定义

索引（Index）是帮助MySQL高效获取数据的数据结构。

索引模型

索引常见的数据模型有哈希表、有序数组、搜索树。

哈希表

哈希表是一种以键 - 值（key-value）存储数据的结构，只要输入待查找的键（即：key），就可以找到其对应的值（即：value）。其实现思路是使用一个哈希函数将key换算成数组中的下标，并将value存储到该下标对应的位置。多个key值经过哈希函数换算后可能指向同一个下标，因此，采用一个链表来存储相同下标对应的value。

以人的身份证和姓名为例，如图所示：

图中，key2和key3对应的数组下标均为7，查找时，先根据key2或key3的哈希值定位到数组下标7，再遍历下标7对应的链表找到key2或key3对应的value2或value3。因此，哈希表比较适用于等值查询的场景。

有序数组

以人的身份证和姓名为例，如图所示：

图中，有序数组按照身份证号递增的顺序保存数组：

• 如果要查找card1对应的name，使用二分法可以快速得到card1对应的name1，时间复杂度为O(log(N))。
• 如果要查找card3～card4区间的数据，可以先用二分法找到card3（如果不存在card3，则找到大于card3的第一条数据），然后向右遍历，直到找到第一个大于card4的身份证号，退出循环。
• 如果要向有序数组中插入一条数据，则需要移动该记录后面的数据，成本相对较高。

因此，有序数组索引比较适用于静态存储引擎（即：不再修改的数据）。

搜索树

1）二叉搜索树

二叉搜索树的特点：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。

以人的身份证和姓名为例，如图所示：

图中，如果要查找card1对应的数据，则搜索顺序为：userA -> userB -> userE -> user1。时间复杂度为O(log(N))。

2）多叉搜索树

树可以是二叉，也可以是多叉。多叉树的每个节点有多个子节点，子节点之间的大小保证从左到右递增。二叉树的搜索效率最高，但是实际上大多数数据库存储并不使用二叉树，其原因是索引不止存在内存中，还需要写到磁盘中。

假如一棵存在100万个节点的二叉树，树高为20。一次查询可能需要访问20个数据块，从磁盘随机读一个数据块需要10ms的寻址时间。那么对于一个100万行的表，如果使用二叉树来存储，单独访问一个行可能需要20*10ms的时间。因此，为了让一个查询尽量少的访问磁盘，就需要让查询过程尽量少的访问数据块（即：使用N叉树，其中N取决于数据块的大小）。

以InnoDB的一个整数字段索引为例，这个N差不多为1200。当多叉树的树高为4时，可以存储1200^3个值（即：1728000000）。那么访问一个存储10亿行数据的表整数字段索引时，最多只需要访问3次磁盘即可，大大减少访问磁盘的次数，提高搜索效率。

InnoDB索引模型

B+树

在InnoDB中，以B+树作为索引模型。表是根据主键顺序以索引的形式进行存储，这种存储方式的表称为索引组织表。

B+树结构，如图所示：

图中：

• 淡黄色表示磁盘块。
• 浅蓝色表示数据项。
• 深蓝色表示指向磁盘块的指针。

其中，磁盘块1包含：

• 数据项16和38。
• 指针P1、P2、P3：
• P1表示小于16的磁盘块。
• P2表示在16和38之间的磁盘块。
• P3表示大于38的磁盘块。

真实数据存储在叶子节点（即：3、5、8、10、13、15、27、29、36、62、74、85、91、96）；非叶子节点不存储真实数据，只存储指引搜索方向的数据项，如：16、38并不真实存在于数据表中。

B+树查找过程

在上图中，要查找数据项27，查找过程如下：

• 1）将磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中使用二分查找确定27在数据项16和38之间，锁定磁盘块1的P2指针，内存操作时间非常短（相比磁盘的IO）可以忽略不计。
• 2）通过磁盘块1中P2指针的磁盘地址将磁盘块3由磁盘加载到内存，发生第二次IO，27在25和32之间，锁定磁盘块3的P2指针。
• 3）通过磁盘块3中P2指针的磁盘地址将磁盘块8由磁盘加载到内存，发生第三次IO，同时内存中做二分查找找到27，结束查询，总计三次IO。

通常情况下，三层的B+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能会有巨大的提升；如果没有索引，每个数据项都要发生一次IO，那么总共需要上百万次IO，查询成本将会非常高昂。

索引类型

根据B+树叶子节点的内容，索引类型分为主键索引和非主键索引：

• 主键索引的叶子节点存储的是整行数据。在InnoDB中，主键索引也被称为聚簇索引（clustered index）。
• 非主键索引的叶子节点存储的是主键的值。在InnoDB中，非主键索引也被称为二级索引（secondary index）。

其中：

• 主键索引查询，只需要按主键（如：id）搜索主键索引这颗B+树即可。
• 非主键索引（普通索引）查询，需要先搜索普通索引这颗B+树得到主键值，再根据主键值搜索主键索引B+树得到对应的数据，这个过程称为回表。

因此，基于非主键索引的查询需要多扫描一棵索引树。因此，在应用中应该尽量使用主键查询。

索引维护

创建表：

create table t_user(
    id int primary key,
    card int not null,
    name varchar(16),
    index idx_card(card)
)engine=InnoDB;

其中：

• id：主键索引。
• card：普通索引。

索引维护

向索引中插入数据，根据插入位置存在如下差异：

• 向末尾插入数据，将直接插入数据即可。
• 向中间插入数据，插入数据后需要移动该插入数据后面的数据，同时，如果插入数据所在的数据页已满，需要申请一个新的数据页，并挪动部分数据到新的数据页中，这个过程称为页分裂。因此，向中间插入数据除了影响性能外，页分裂操作还会影响数据页的利用率。即：原本放在一个数据页的数据需要分到两个页中，整体空间利用率降低大约50%。

注意：当相邻两个数据页由于删除数据导致利用率很低后，会对数据页进行合并。这个过程称为页合并，页合并为页分裂的逆过程。

自增主键索引维护

自增主键是指自增列上定义的主键，自增主键定义： NOT NULL PRIMARY KEY AUTO_INCREMENT。插入数据时可以不指定ID（自增列）的值，系统会获取当前ID最大值加1作为下一条记录的ID值。

自增主键的插入数据模式符合递增插入的场景，每次插入一条新数据都是追加操作，不涉及挪动其他记录，也不会触发叶子节点的页分裂。

非自增主键索引维护

非自增主键插入数据时，一般不保证数据有序插入，会因数据移动和页分裂而影响插入性能。同时，非自增主键占用的存储空间相对较大（如：身份证号码），通过以上B+树的查找过程可知，IO次数取决于B+树的高度h。假设当前数据表的数据量为N，每个磁盘块中数据项的数量为m，则树高h=log(m+1)N，当数据量N固定的情况下，m越大，h越小。而m = 磁盘块（数据页）的大小/数据项的大小，磁盘块大小固定，如果数据项占的空间越小，磁盘块中存储的数据项数量m就越多，B+树的高度h就越低。

覆盖索引

以上面的t_user表为例，初始化表数据：

insert into t_user values
(1,43252411115431,'南秋同学1'),
(2,43252411115432,'南秋同学2'),
(3,43252411115433,'南秋同学3'),
(5,43252411115435,'南秋同学5'),
(6,43252411115436,'南秋同学6'),
(8,43252411115438,'南秋同学8'),
(9,43252411115439,'南秋同学9');

执行语句：

select * from t_user where card between 43252411115433 and 43252411115438;

查询过程，如图所示：

处理流程：

• 1）从card索引树上查找card=43252411115433的记录，获得id = 3。
• 2）从主键（id）索引树查找id = 3对应的数据行。
• 3）重复步骤1和步骤2，直到找到card大于43252411115438的记录，结束循环，并将查询结果集返回给客户端。

以上处理流程中，查询card索引树5次，回表查询主键索引树4次。

覆盖索引指的是一个索引中包含了查询语句的查询结果，无需回表。如：select id from t_user where card between 43252411115433 and 43252411115438，该语句需要查询的id值存在于card索引树中，可以直接获得查询结果，无需回表。

由于覆盖索引可以减少树的搜索次数，显著提升查询性能，因此使用覆盖索引是一个常用的性能优化手段。

索引优化规则

索引最左前缀原则

最左前缀原则指的是在MySQL建立联合索引时，会遵守最左前缀匹配原则（即：最左优先），在检索数据时从联合索引的最左边开始匹配。

创建表：

create table t_user(
    id int primary key,
    name varchar(16),
    age int not null,
    gender varchar(1),
    index idx_name_age_gender(name,age,gender)
)engine=InnoDB;

最左前缀原则示例：

• 检索('张'三,20,'F')这样的数据时，B+树会优先比较name来确定下一步的搜索方向，如果name相同，则再依次比较age和sex，最后得到检索的数据。
• 检索(20,'F')这样没有name的数据时，B+树无法确定下一步的搜索方向，因为建立搜索树时，name为第一个比较因子，必须要先根据name搜索才能确定下一步的搜索方向。
• 检索('张三','F')这样的数据时，B+树可以使用name来确定下一步的搜索方向，但下一个字段age缺失，所以只能先将name为张三的数据查询出来，再匹配性别为F的数据。

注意：最左前缀匹配规则可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符。

索引下推原则

MySQL5.6引入索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

无索引下推，执行语句：

select * from t_user where name like '张%';

执行流程，如图所示：

图中，查询过程只会按顺序将name第一个字为'张'的记录取出来进行回表。因此，需要回表4次。

索引下推，执行语句：

select * from t_user where name like '张%' and age=20;

执行流程，如图所示：

图中，查询过程只会按顺序将name第一个字为'张'的记录取出来并判断age是否等于20，对于age不等于20的记录直接判断并跳过。因此，只需要对id为3和4的这两条记录进行回表（2次）。

【阅读推荐】

更多精彩内容，如：

• Redis系列

• 数据结构与算法系列

• Nacos系列

• MySQL系列

• JVM系列

• Kafka系列

请移步【南秋同学】个人主页进行查阅。内容持续更新中......

【作者简介】

一枚热爱技术和生活的老贝比，专注于Java领域，关注【南秋同学】带你一起学习成长～