作者：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_MchStat (`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;
从建表语句可以知道该表有两个索引：
主键索引，是一个组合索引，由字段 FStateDate、FMerchantId 和 FVersion 组成；普通索引，是一个组合索引，由字段 FStateDate 和 FVersion 组成；优化前的 SQL 语句（做了部分裁剪）A：
SELECT SQL_CALC_FOUND_ROWS FStatDate, FMerchantId, FVersion, FBatch, FTradeAmount, FTradeCountFROM T_MchStat_1020WHERE FStatDate = 20201020 AND FVersion = 0 AND FMerchantId > 0ORDER 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, FTradeCountFROM T_MchStat_1020 a1, ( SELECT FStatDate, FMerchantId, FVersion FROM T_MchStat_1020 WHERE FStatDate = 20201020 AND FVersion = 0 AND FMerchantId > 0 ORDER BY FMerchantId ASC LIMIT 0, 8000 ) a2where a1.FStatDate = a2.FStatDate and a1.FVersion = a2.FVersion and a1.FMerchantId = a2.FMerchantId;
优化关键步骤为：
新增一个子查询，select 字段只有主键字段；该 SQL 的 explain 结果如下，子查询语句利用了索引，而终极在线上运行结果也证明了优化效果显著。
疑问
优化后的 SQL 语句 B 比原来的 SQL 语句 A 繁芜的多（子查询，临时表关联等），怎么效率会提升，违反直觉？有三个疑问：
SQL 语句 A 的查询条件字段都在主键中，主键索引用到了没？SQL 语句 B 的子查询为什么能够用到索引？前后两条语句实行流程的差异是什么？索引的数据构造在 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;}
有序数组的优点很明显，同样其缺陷也很明显。其只适宜静态数据，如碰着有数据新增插入，则就会须要数据移动（新申请空间、拷贝数据和开释空间等动作），这将非常花费资源。
Hash哈希表是一种以键-值（K-V）存储数据的构造，我们只须要输入键 K，就可以找到对应的值 V。哈希的思路是用特定的哈希函数将 K 换算到数组中的位置，然后将值 V 放到数组的这个位置。如果碰着不同的 K 打算出相同的位置，则在这个位置拉出一个链表依次存放。哈希表适用于等值查询的场景，对应范围查询则无能为力。
二叉搜索树
二叉搜索树，也称为二叉查找树、有序二叉树或排序二叉树，是指一颗空树或者具有以下性子的二叉树：
若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于或即是它的根节点的值；任意节点的左、右子树也分别为二叉查找树；二叉搜索树比较于其它数据构造的上风在于查找、插入的韶光繁芜度较低，为 O(logn)。为了坚持 O(logn)的查询繁芜度，须要保持这棵树是平衡二叉树。
二叉搜索树的查找算法：
若 b 是空树，则搜索失落败，否则：若 x 即是 b 的根节点的值，则查找成功；否则：若 x 小于 b 的根节点的值，则搜索左子树；否则：查找右子树。相对付有序数组和 Hash，二叉搜索树在查找和插入两端的表现都非常不错。后续基于此不断的优化，发展出 N 叉树等。
B+树Innodb 存储引擎支持 B+树索引、全文索引和哈希索引。个中 Innodb 存储引擎支持的哈希索引是自适应的，Innodb 存储引擎会根据表的利用情形自动为表天生哈希索引，不能人为干预。B+树索引是关系型数据库中最常见的一种索引，也将是本文的主角。
数据构造
在前文大略先容了有序数组和二叉搜索树，对二分查找法和二叉树有了基本理解。B+树的定义相对繁芜，在理解索引事情机制上无须深入、只需理解数据组织形式和查找算法即可。我们可以大略的认为 B+树是一种 N 叉树和有序数组的结合体。
例如：
B+树的 3 个优点:
层级更低，IO 次数更少每次都须要查询到叶子节点，查询性能稳定叶子节点形成有序链表，范围查询方便操作算法
查找由根节点自顶向下遍历树，根据分离值在要查找的一边的指针；在节点内利用二分查找来确定位置。
插入Leaf Page（叶子）满Index Page（索引）满操作
删除
叶子节点小于添补因子中间节点小于添补因子操作
注：插入和删除两个表格内容来自《MySQL 技能底细-InnoDB 存储引擎》
添补因子（innodb_fill_factor）：索引构建期间添补的每个 B-tree 页面上的空间百分比，别的空间保留给未来索引增长。从插入和删除操作中可以看到添补因子的值会影响到数据页的 split 和 merge 的频率。将值设置小些，可以减少 split 和 merge 的频率，但是索引相对会占用更多的磁盘空间；反之，则会增加 split 和 merge 的频率，但是可以减少占用磁盘空间。Innodb 对付聚拢索引默认会预留 1/16 的空间担保后续的插入和升级索引。
Innodb B+树索引前文先容了索引的基本数据构造，现在开始我们从 Innodb 的角度理解如何利用 B+树构建索引，索引如何事情和如何利用索引提升查找效率。
聚拢索引和非聚拢索引数据库中的 B+树索引可以分为聚拢索引和非聚拢索引。聚拢索引和非聚拢索引的不同点在于叶子节点是否是完全行数据。
Innodb 存储引擎表是索引组织表，即表中的数据按照主键顺序存放。聚拢索引便是按照每张表的主键布局一棵 B+树，叶子节点存放的是表的完全行记录。非聚拢索引的叶子节点不包含行记录的全部数据。Innodb 存储引擎的非聚拢索引的叶子节点的内容为主键索引值。
若数据表没有主键聚拢索引是怎么建立的？在没有主键时 Innodb 会给数据表的每条记录天生一个 6 个字节长度的 RowId 字段，会以此建立聚拢索引。
Select 语句查找记录的过程下面例子将展示索引数据的组织形式及 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 语句实行过程select from T where k between 3 and 5;
实行流程如下：
在 K 索引树上找到 k=3 的记录，取得 ID=300；再到 ID 索引树上查找 ID=300 对应的 R3；在 k 索引树取下一个值 k=5，取得 ID=500；再回到 ID 索引树查到 ID=500 对应的 R4；在 k 索引树取下一个值 k=6，不知足条件，循环结束。上述查找记录的过程中引入了一个主要的观点：回表，即回到主键索引树搜索的过程。避免回表操作是提升 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;SQL 语句 A
explain select from employees where hire_date > '1990-01-14';
explain 结果：
SQL 语句 B
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 的值，无需再次回到主键索引树查找，也便是“覆盖”了我们的查询需求，我们称之为覆盖索引。覆盖索引可以减少树的搜索次数，显著提升查询性能。
最左匹配SQL 语句 Aexplain 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%';在 MySQL 5.5 实行 explain，extra 字段的值显示没有利用索引
实行查询花费韶光为 0.12s
在 MySQL 5.7 实行 explain，extra 字段的值显示利用了索引下推
实行查询花费韶光为 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%'"条件的记录就不再须要回表操作。
MRR 优化MySQL 5.6 版本开始支持 Multi-Range Read(MRR)优化，MRR 优化的目的是为减少磁盘的随机访问，并且将随机访问转化为较为顺序的数据访问，对付 IO-bound 类型的 SQL 查询语句可带来性能极大提升。我们先看下比拟测试，以下测试语句在同一个 MySQL 实例下实行，实行前均进行 mysql 做事重启，以担保缓存此没被预热。
关闭 MRRSET @@optimizer_switch='mrr=off';select from employees where hire_date > '1990-01-14' and first_name like 'Hi%';
实行耗时为 0.90s
开启 MRR
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 的比拟结果，可以看到新语句用到索引下推，解释索引并未失落效。为什么？在不该用覆盖索引的情形下，优化器只有在数据量小的时候才会选择利用非聚拢索引。受制于传统的机器磁盘特性，通过聚拢索引顺序读数据行的性能会比通过非聚拢索引离散读数据行要好。以是，优化器在即使有非聚拢索引、但是访问数据量可能达到送记录数的 20%时会选择聚拢索引。当然也可以用 Force index 逼迫利用索引。
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_MchStat_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, FTradeCountFROM T_MchStat_1020 a1, ( SELECT FStatDate, FMerchantId, FVersion FROM T_MchStat_1020 WHERE FStatDate = 20201020 AND FVersion = 0 AND FMerchantId > 0 ORDER BY FMerchantId ASC LIMIT 0, 8000 ) a2where a1.FStatDate = a2.FStatDate and a1.FVersion = a2.FVersion and a1.FMerchantId = a2.FMerchantId;
SQL 语句 A 的查询条件字段都在主键中，主键索引用到了没？
主键索引实在是有被利用的：索引的范围查询，只是其须要逐条读取和解析所有记录才导致慢查询。
SQL 语句 B 的子查询为什么能够用到索引？
前文中我们先容了聚拢索引，其索引键值便是主键。两条 SQL 语句的不同之处在于 B 语句的子查询语句的 Select 字段都包含在主键字段中，而 A 语句还有其它字段（例如 FBatch 和 FTradeAmount 等）。这种情形下只凭主键索引的键值就能知足 B 语句的字段哀求；A 语句则须要逐条取整行记录进行解析。前后两条语句实行流程的差异是什么？
SQL 语句 A 的实行过程：逐条扫描索引表并比较查询条件碰着符合查询条件的则读取整行数据返回回到 a 步骤，直至完成所有索引记录的比较对返回的所有符合条件的记录（完全的记录）进行排序选取前 8000 条数据返回SQL 语句 B 的实行过程：逐条扫描索引表并比较查询条件碰着符合查询条件的则从索引键中取干系字段值返回回到 a 步骤，直至完成所有索引记录的比较对返回的所有符合条件的记录（每条记录只有 3 个主键）进行排序选取前 8000 条数据返回形成临时表关联临时表与主表，利用主键相等比较查询 8000 条数据比拟两个 SQL 语句的实行过程，可以创造差异点集中在步骤 2 和步骤 4。在步骤 2 中 SQL 语句 A 须要随机读取整行数据并解析非常耗资源；步骤 4 涉及 MySQL 的排序算法，这里也会对实行效率有影响，排序效果上看 SQL 语句 B 比 SQL 语句 A 好。名词阐明主键索引顾名思义该类索引由表的主键组成，从左到右由小到大排序。一个 Innodb 存储表只有一张主键索引表（聚拢索引）。
普通索引最为平常的一种索引，没有特殊限定。
唯一索引该索引的字段不能有相同值，但许可有空值。
组合索引由多列字段组合而成的索引，每每是为了提升查询效率而设置。
总结在文章开始时先容了常见的几种索引数据构造，适宜静态数据的有序数组、适宜 KV 构造的哈希索引及兼顾查询及插入性能的搜索二叉树；然后先容了 Innodb 的常见索引实现办法 B+树及 Select 语句利用 B+树索引查找记录的实行过程，在这个部分我们理解了几个关键的观点，回表、覆盖索引、最左匹配、索引下推和 MMR；之后还总结了索引的失落效场景及背后的缘故原由。末了，我们回到最初的案例，剖析出优化前后 SQL 语句在利用索引的差异，进而导致实行效率的差异。
本文先容了索引的一些粗浅知识，希望能够对读者有些许帮助。作为阶段性学习的一个总结，文章对 MySQL 索引的干系知识基本上是浅尝辄止，日后还需多多利用和深入学习。
何以解忧？唯有学习。
参考书目和资料
《MySQL 技能底细-InnoDB 存储引擎》第二版，作者：姜承尧《MySQL 实战 45 讲》，作者：林晓斌https://dev.mysql.com/doc/refman/8.0/en/https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9重温数据构造：理解 B 树、B+ 树特点及利用场景 - Androidhttps://github.com/zhangyachen/zhangyachen.github.io/issues/117
