作者：fanili，腾讯 WXG 后台开发工程师
知其然知其所以然！本文介绍索引的数据结构、查找算法、常见的索引概念和索引失效场景。
在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。（百度百科）
索引的目的是提高查找效率，对数据表的值集合进行了排序，并按照一定数据结构进行了存储。
本文将从一个案例开始，从索引的数据结构、分类、关键概念及如何使用索引提高查找效率等方面对索引知识进行总结。
业务中有个既存的历史 SQL 语句在运行时会导致 DB 服务器过载，进而导致相关服务阻塞无法及时完成。CPU 监控曲线如下：
从 DB 的 CPU 使用率曲线可以看到业务运行一直处于“亚健康”状态（1），随着业务的增长随时都可能出现问题。这种问题（2）在 11 月 11 日凌晨出现，当时 DB CPU 一直处于 100%高负荷状态，且存在大量的慢查询语句。最终以杀死进程降低 DB 负载、减少业务进程（3）的方式恢复业务。
在 11 月 11 日下午，对该业务的 SQL 语句进行了优化，优化的效果如下。业务运行时的 CPU 使用率峰值有很大的降低（对比图 2 的 1，2，3 可见）；慢查询语句几乎在监控曲线上也无法明显观察到（对比图 3 的 1，2，3 可见）。
表结构
CREATE TABLE T_Mch******Stat (`FStatDate` int unsigned NOT NULL DEFAULT 19700101 COMMENT '统计日期',
`FMerchantId` bigint unsigned NOT NULL DEFAULT 0 COMMENT '商户ID',
`FVersion` int unsigned NOT NULL DEFAULT 0 COMMENT '数据版本号',
`FBatch` bigint unsigned NOT NULL DEFAULT 0 COMMENT '统计批次',
`FTradeAmount` bigint NOT NULL DEFAULT 0 COMMENT '交易金额'
PRIMARY KEY (`FStatDate`,`FMerchantId`,`FVersion`),
INDEX i_FStatDate_FVersion (`FStatDate`,`FVersion`))
DEFAULT CHARSET = utf8 ENGINE = InnoDB;
从建表语句可以知道该表有两个索引：
优化前的 SQL 语句（做了部分裁剪）A：
SELECT SQL_CALC_FOUND_ROWS FStatDate,
FMerchantId,
FVersion,
FBatch,
FTradeAmount,
FTradeCount
FROM T_Mch******Stat_1020
WHERE FStatDate = 20201020
AND FVersion = 0
AND FMerchantId > 0
ORDER BY FMerchantId ASC LIMIT 0, 8000
对该 SQL 进行 explain 得到如下结果，Extra 字段的值为 using where，说明并没有使用到索引。
优化后的 SQL 语句（做了部分裁剪）B：
SELECT SQL_CALC_FOUND_ROWS a1.FStatDate,
a1.FMerchantId,
a1.FVersion,
FBatch,
FTradeAmount,
FTradeCount
FROM T_Mch******Stat_1020 a1, (
SELECT FStatDate, FMerchantId, FVersion
FROM T_Mch******Stat_1020
WHERE FStatDate = 20201020
AND FVersion = 0
AND FMerchantId > 0
ORDER BY FMerchantId ASC LIMIT 0, 8000 ) a2
where a1.FStatDate = a2.FStatDate
and a1.FVersion = a2.FVersion
and a1.FMerchantId = a2.FMerchantId;
优化关键步骤为：
该 SQL 的 explain 结果如下，子查询语句使用了索引，而最终在线上运行结果也证明了优化效果显著。
优化后的 SQL 语句 B 比原来的 SQL 语句 A 复杂的多（子查询，临时表关联等），怎么效率会提升，违反直觉？有三个疑问：
在 MySQL 中，索引是在存储引擎层实现的，而不同的存储引擎根据其业务场景特点会有不同的实现方式。这里会先介绍我们常见的有序数组、Hash 和搜索树，最后看下 Innodb 的引擎支持的 B+树。
数组是在任何一本数据结构和算法的书籍都会介绍到的一种重要的数据结构。有序数组如其字面意思，以 Key 的递增顺序保存数据在数组中。非常适合等值查询和范围查询。
ID：1ID：2......ID:N
在 ID 值没有重复的情况下，上述数组按照 ID 的递增顺序进行保存。这个时候如果需要查询特定 ID 值的 name，用二分法就可以快速得到，时间复杂度是 O(logn)。
// 二分查找递归实现方式
int binary_search(const int arr[], int start, int end, int key)
{
if (start > end)
return -1;
int mid = start + (end - start) / 2;
if (arr[mid] > key)
return binary_search(arr, start, mid - 1, key);
else if (arr[mid] < key)
return binary_search(arr, mid + 1, end, key);
else
return mid;
}
有序数组的优点很明显，同样其缺点也很明显。其只适合静态数据，如遇到有数据新增插入，则就会需要数据移动（新申请空间、拷贝数据和释放空间等动作），这将非常消耗资源。
哈希表是一种以键-值（K-V）存储数据的结构，我们只需要输入键 K，就可以找到对应的值 V。哈希的思路是用特定的哈希函数将 K 换算到数组中的位置，然后将值 V 放到数组的这个位置。如果遇到不同的 K 计算出相同的位置，则在这个位置拉出一个链表依次存放。哈希表适用于等值查询的场景，对应范围查询则无能为力。
二叉搜索树，也称为二叉查找树、有序二叉树或排序二叉树，是指一颗空树或者具有以下性质的二叉树：
二叉搜索树相比于其它数据结构的优势在于查找、插入的时间复杂度较低，为 O(logn)。为了维持 O(logn)的查询复杂度，需要保持这棵树是平衡二叉树。
二叉搜索树的查找算法：
相对于有序数组和 Hash，二叉搜索树在查找和插入两端的表现都非常不错。后续基于此不断的优化，发展出 N 叉树等。
Innodb 存储引擎支持 B+树索引、全文索引和哈希索引。其中 Innodb 存储引擎支持的哈希索引是自适应的，Innodb 存储引擎会根据表的使用情况自动为表生成哈希索引，不能人为干预。B+树索引是关系型数据库中最常见的一种索引，也将是本文的主角。
数据结构
在前文简单介绍了有序数组和二叉搜索树，对二分查找法和二叉树有了基本了解。B+树的定义相对复杂，在理解索引工作机制上无须深入、只需理解数据组织形式和查找算法即可。我们可以简单的认为 B+树是一种 N 叉树和有序数组的结合体。
例如：
B+树的 3 个优点:
操作算法
由根节点自顶向下遍历树，根据分离值在要查找的一边的指针；在节点内使用二分查找来确定位置。
Leaf Page（叶子）满Index Page（索引）满操作
叶子节点小于填充因子中间节点小于填充因子操作
注：插入和删除两个表格内容来自《MySQL 技术内幕-InnoDB 存储引擎》
填充因子（innodb_fill_factor）：索引构建期间填充的每个 B-tree 页面上的空间百分比，其余空间保留给未来索引增长。从插入和删除操作中可以看到填充因子的值会影响到数据页的 split 和 merge 的频率。将值设置小些，可以减少 split 和 merge 的频率，但是索引相对会占用更多的磁盘空间；反之，则会增加 split 和 merge 的频率，但是可以减少占用磁盘空间。Innodb 对于聚集索引默认会预留 1/16 的空间保证后续的插入和升级索引。
前文介绍了索引的基本数据结构，现在开始我们从 Innodb 的角度了解如何使用 B+树构建索引，索引如何工作和如何使用索引提升查找效率。
数据库中的 B+树索引可以分为聚集索引和非聚集索引。聚集索引和非聚集索引的不同点在于叶子节点是否是完整行数据。
Innodb 存储引擎表是索引组织表，即表中的数据按照主键顺序存放。聚集索引就是按照每张表的主键构造一棵 B+树，叶子节点存放的是表的完整行记录。非聚集索引的叶子节点不包含行记录的全部数据。Innodb 存储引擎的非聚集索引的叶子节点的内容为主键索引值。
若数据表没有主键聚集索引是怎么建立的？在没有主键时 Innodb 会给数据表的每条记录生成一个 6 个字节长度的 RowId 字段，会以此建立聚集索引。
下面例子将展示索引数据的组织形式及 Select 语句查询数据的过程。
create table T (
ID int primary key,
k int NOT NULL DEFAULT 0,
s varchar(16) NOT NULL DEFAULT '',
index k(k)
) engine=InnoDB DEFAULT CHARSET=utf8;
insert into T values(100, 1, 'aa'),(200, 2, 'bb'),(300, 3, 'cc'),(500, 5, 'ee'),(600,6,'ff'),(700,7,'gg');
左边是以主键 ID 建立起的聚集索引，其叶子节点存储了完整的表记录信息；右边是以普通字段 K 建立的普通索引，其叶子节点的值是主键 ID。
select * from T where k between 3 and 5;
执行流程如下：
上述查找记录的过程中引入了一个重要的概念：回表，即回到主键索引树搜索的过程。避免回表操作是提升 SQL 查询效率的常规思路及重要方法。那么如何避免回表？
注：该例子来自《MySQL 实战 45 讲》
MySQL 5.7,建表语句：
CREATE TABLE `employees` (
`emp_no` int(11) NOT NULL,
`birth_date` date NOT NULL,
`first_name` varchar(14) NOT NULL,
`last_name` varchar(16) NOT NULL,
`gender` enum('M','F') NOT NULL,
`hire_date` date NOT NULL,
PRIMARY KEY (`emp_no`),
KEY `i_first_name` (`first_name`),
KEY `i_hire_date` (`hire_date`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
explain select * from employees where hire_date > '1990-01-14';
explain 结果：
explain select emp_no from employees where hire_date > '1990-01-14';
explain 结果：
从前后两次 explain 的结果可以看到 SQL 语句 A 的 extra 为 using where，SQL 语句 B 的 extra 为 using where;using index。这说明 A 没有使用索引，而 B 使用了索引。
索引 K 中包含了查询语句所需要的字段 ID 的值，无需再次回到主键索引树查找，也就是“覆盖”了我们的查询需求，我们称之为覆盖索引。覆盖索引可以减少树的搜索次数，显著提升查询性能。
explain select * from employees where hire_date > '1990-01-14' and first_name like '%Hi%';
explain select * from employees where hire_date > '1990-01-14' and first_name like 'Hi%';
在上述测试的 SQL 语句 A 使用了极端方式: first_name like '%Hi%'，前后都增加模糊匹配使得 SQL 语句无法使用到索引；当去掉最左边的‘%’后，SQL 语句 B 就使用了索引。最左匹配可以是字符串索引的最左 N 个字符，也可以是联合索引的最左 M 的字段。合理规划、使用最左匹配可以减少索引，从而节约磁盘空间。
何为索引下推？我们先从下面这组对比测试开始，将在 MySQL5.5 版本和 MySQL5.7 版本中执行同一条 SQL 语句：
select * from employees where hire_date > '1990-01-14' and first_name like 'Hi%';
执行查询花费时间为 0.12s
执行查询花费时间为 0.02s
explain 结果中的 extra 字段值包含 using index condition，则说明使用了索引下推。索引下推功能是从 5.6 版本开始支持的。在 5.6 版本之前，i_first_name 索引是没有使用上的，需要每次去主键索引表取完整的记录值进行比较。从 5.6 版本开始，由于索引 i_first_name 的存在，可以直接取索引的 first_name 值进行过滤，这样不符合"first_name like 'Hi%'"条件的记录就不再需要回表操作。
MySQL 5.6 版本开始支持 Multi-Range Read(MRR)优化，MRR 优化的目的是为减少磁盘的随机访问，并且将随机访问转化为较为顺序的数据访问，对于 IO-bound 类型的 SQL 查询语句可带来性能极大提升。我们先看下对比测试，以下测试语句在同一个 MySQL 实例下执行，执行前均进行 mysql 服务重启，以保证缓存此没被预热。
SET @@optimizer_switch='mrr=off';
select * from employees where hire_date > '1990-01-14' and first_name like 'Hi%';
执行耗时为 0.90s
SET @@optimizer_switch='mrr=on,mrr_cost_based=off';
select * from employees where hire_date > '1990-01-14' and first_name like 'Hi%';
从测试结果可以发现在 mrr 从关闭到开启，耗时从 0.90s 减少到 0.03s，查询速率达到 30 倍的提升。
在 MySQL 表中建立了索引，SQL 查询语句就会一定使用到索引么？不一定，存在着索引失效的场景。我们给 employees 表增一个组合索引，后续例子均基于此表进行分析、测试。
alter table employees add index i_b_f_l(birth_date, first_name, last_name)
alter table employees add index i_h(hire_date);
explain select * from employees where hire_date > '1989-06-02';
alter table employees add index i_first_name (first_name);
explain select * from employees where first_name = 1;
explain select * from employees where CHAR_LENGTH(hire_date) = 10;
explain select * from employees where hire_date like '%1995';
explain select * from employees where last_name = 'Kalloufi' and first_name = 'Saniya';
explain select * from employees where hire_date > '1999-06-02';
模糊匹配和不使用组合索引的首字段作为查询条件均是无法快速定位索引位置从而导致无法使用索引。模糊匹配当查询条件是 lwhere A ike 'a%'，a 是 A 的最左前缀时是可能用上索引的（最左匹配），是否用上最终还是依赖优化器对查询数据量的评估。
让我们回到文章初的案例，尝试回答下当时提出的 3 个问题。
-- A语句
SELECT FStatDate, FMerchantId, FVersion, FBatch, FTradeAmount, FTradeCount FROM T_Mch******Stat_1020 WHERE FStatDate = 20201020 AND FVersion = 0 AND FMerchantId > 0 ORDER BY FMerchantId ASC LIMIT 0, 8000;
-- B语句
SELECT SQL_CALC_FOUND_ROWS a1.FStatDate,
a1.FMerchantId,
a1.FVersion,
FBatch,
FTradeAmount,
FTradeCount
FROM T_Mch******Stat_1020 a1, (
SELECT FStatDate, FMerchantId, FVersion
FROM T_Mch******Stat_1020
WHERE FStatDate = 20201020
AND FVersion = 0
AND FMerchantId > 0
ORDER BY FMerchantId ASC LIMIT 0, 8000 ) a2
where a1.FStatDate = a2.FStatDate
and a1.FVersion = a2.FVersion
and a1.FMerchantId = a2.FMerchantId;
SQL 语句 A 的查询条件字段都在主键中，主键索引用到了没？
主键索引其实是有被使用的：索引的范围查询，只是其需要逐条读取和解析所有记录才导致慢查询。
SQL 语句 B 的子查询为什么能够用到索引？
前后两条语句执行流程的差异是什么？
顾名思义该类索引由表的主键组成，从左到右由小到大排序。一个 Innodb 存储表只有一张主键索引表（聚集索引）。
最为平常的一种索引，没有特别限制。
该索引的字段不能有相同值，但允许有空值。
由多列字段组合而成的索引，往往是为了提升查询效率而设置。
在文章开始时介绍了常见的几种索引数据结构，适合静态数据的有序数组、适合 KV 结构的哈希索引及兼顾查询及插入性能的搜索二叉树；然后介绍了 Innodb 的常见索引实现方式 B+树及 Select 语句使用 B+树索引查找记录的执行过程，在这个部分我们了解了几个关键的概念，回表、覆盖索引、最左匹配、索引下推和 MMR；之后还总结了索引的失效场景及背后的原因。最后，我们回到最初的案例，分析出优化前后 SQL 语句在使用索引的差异，进而导致执行效率的差异。
本文介绍了索引的一些粗浅知识，希望能够对读者有些许帮助。作为阶段性学习的一个总结，文章对 MySQL 索引的相关知识基本上是浅尝辄止，日后还需多多使用和深入学习。
何以解忧？唯有学习。
参考书目和资料
京公网安备 11010802035086号