乐趣区

关于程序员:腾讯-WXG-后台开发工程师对-MySQL-索引知识点总结

jiezi

知其然知其所以然！本文介绍索引的数据结构、查找算法、常见的索引概念和索引生效场景。

什么是索引？

在关系数据库中，索引是一种独自的、物理的对数据库表中一列或多列的值进行排序的一种存储构造，它是某个表中一列或若干列值的汇合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录，能够依据目录中的页码疾速找到所需的内容。（百度百科）

索引的目标是进步查找效率，对数据表的值汇合进行了排序，并依照肯定数据结构进行了存储。

本文将从一个案例开始，从索引的数据结构、分类、要害概念及如何应用索引进步查找效率等方面对索引常识进行总结。

从一个案例开始

景象

业务中有个既存的历史 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;

从建表语句能够晓得该表有两个索引：

  1. 主键索引，是一个组合索引，由字段 FStateDate、FMerchantId 和 FVersion 组成；
  2. 一般索引，是一个组合索引，由字段 FStateDate 和 FVersion 组成；

优化前的 SQL 语句（做了局部裁剪）A：

SELECT SQL_CALC_FOUND_ROWS 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

对该 SQL 进行 explain 失去如下后果，Extra 字段的值为 using where，阐明并没有应用到索引。

​

优化后的 SQL 语句（做了局部裁剪）B：

SELECT SQL_CALC_FOUND_ROWS a1.FStatDate,

a1.FMerchantId,
a1.FVersion,
FBatch,
FTradeAmount,
FTradeCount

FROM T_MchStat_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;

优化关键步骤为：

  • 新增一个子查问，select 字段只有主键字段；

该 SQL 的 explain 后果如下，子查问语句应用了索引，而最终在线上运行后果也证实了优化效果显著。

​

疑难

优化后的 SQL 语句 B 比原来的 SQL 语句 A 简单的多（子查问，长期表关联等），怎么效率会晋升，违反直觉？有三个疑难：

  1. SQL 语句 A 的查问条件字段都在主键中，主键索引用到了没？
  2. SQL 语句 B 的子查问为什么可能用到索引？
  3. 前后两条语句执行流程的差别是什么？

索引的数据结构

在 MySQL 中，索引是在存储引擎层实现的，而不同的存储引擎依据其业务场景特点会有不同的实现形式。这里会先介绍咱们常见的有序数组、Hash 和搜寻树，最初看下 Innodb 的引擎反对的 B+ 树。

有序数组

数组是在任何一本数据结构和算法的书籍都会介绍到的一种重要的数据结构。有序数组如其字面意思，以 Key 的递增程序保留数据在数组中。非常适合等值查问和范畴查问。

ID：1

ID：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 计算出雷同的地位，则在这个地位拉出一个链表顺次寄存。哈希表实用于等值查问的场景，对应范畴查问则无能为力。

​

二叉搜寻树

二叉搜寻树，也称为二叉查找树、有序二叉树或排序二叉树，是指一颗空树或者具备以下性质的二叉树：

  1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
  3. 任意节点的左、右子树也别离为二叉查找树；

​

二叉搜寻树相比于其它数据结构的劣势在于查找、插入的工夫复杂度较低，为 O(logn)。为了维持 O(logn) 的查问复杂度，须要放弃这棵树是均衡二叉树。

二叉搜寻树的查找算法：

  1. 若 b 是空树，则搜寻失败，否则：
  2. 若 x 等于 b 的根节点的值，则查找胜利；否则：
  3. 若 x 小于 b 的根节点的值，则搜寻左子树；否则：
  4. 查找右子树。

绝对于有序数组和 Hash，二叉搜寻树在查找和插入两端的体现都十分不错。后续基于此一直的优化，倒退出 N 叉树等。

B+ 树

Innodb 存储引擎反对 B+ 树索引、全文索引和哈希索引。其中 Innodb 存储引擎反对的哈希索引是自适应的，Innodb 存储引擎会依据表的应用状况主动为表生成哈希索引，不能人为干涉。B+ 树索引是关系型数据库中最常见的一种索引，也将是本文的配角。

数据结构

在前文简略介绍了有序数组和二叉搜寻树，对二分查找法和二叉树有了根本理解。B+ 树的定义绝对简单，在了解索引工作机制上毋庸深刻、只需了解数据组织模式和查找算法即可。咱们能够简略的认为 B+ 树是一种 N 叉树和有序数组的结合体。

例如：

​

B+ 树的 3 个长处:

  1. 层级更低，IO 次数更少
  2. 每次都须要查问到叶子节点，查问性能稳固
  3. 叶子节点造成有序链表，范畴查问不便

操作算法

  • 查找

由根节点自顶向下遍历树，依据拆散值在要查找的一边的指针；在节点内应用二分查找来确定地位。

  • 插入

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;

执行流程如下：

  1. 在 K 索引树上找到 k=3 的记录，获得 ID=300；
  2. 再到 ID 索引树上查找 ID=300 对应的 R3；
  3. 在 k 索引树取下一个值 k=5，获得 ID=500；
  4. 再回到 ID 索引树查到 ID=500 对应的 R4；
  5. 在 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 语句 A

explain select * from employees where hire_date > ‘1990-01-14’ and first_name like ‘%Hi%’;

​

  • SQL 语句 B

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 服务重启，以保障缓存此没被预热。

  • 敞开 MRR

SET @@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’;

​

  • 无奈应用 B+ 索引疾速查找

    B+ 树索引反对疾速查问的基本要素是因为其索引键值是有序存储的，从左到右由小到大，这样就能够在每个层级的节点中疾速查并进入下一层级，最终在叶子节点找到对应的值。

    应用函数会使得 MySQL 无奈应用索引进行疾速查问，因为对索引字段做函数操作会毁坏索引值的有序性，所以优化器抉择不应用索引。而查问条件类型不统一其实也是同样的状况，因为其应用了隐式类型转换 *。

含糊匹配和不应用组合索引的首字段作为查问条件均是无奈疾速定位索引地位从而导致无奈应用索引。含糊匹配当查问条件是 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,
FTradeCount

FROM T_MchStat_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 的子查问为什么可能用到索引？

  1. 前文中咱们介绍了汇集索引，其索引键值就是主键。
  2. 两条 SQL 语句的不同之处在于 B 语句的子查问语句的 Select 字段都蕴含在主键字段中，而 A 语句还有其它字段（例如 FBatch 和 FTradeAmount 等）。这种状况下只凭主键索引的键值就能满足 B 语句的字段要求；A 语句则须要逐条取整行记录进行解析。

前后两条语句执行流程的差别是什么？

  • SQL 语句 A 的执行过程：
  1. 逐条扫描索引表并比拟查问条件
  2. 遇到合乎查问条件的则读取整行数据返回
  3. 回到 a 步骤，直至实现所有索引记录的比拟
  4. 对返回的所有符合条件的记录（残缺的记录）进行排序
  5. 选取前 8000 条数据返回
  • SQL 语句 B 的执行过程：
  1. 逐条扫描索引表并比拟查问条件
  2. 遇到合乎查问条件的则从索引键中取相干字段值返回
  3. 回到 a 步骤，直至实现所有索引记录的比拟
  4. 对返回的所有符合条件的记录（每条记录只有 3 个主键）进行排序
  5. 选取前 8000 条数据返回造成长期表
  6. 关联长期表与主表，应用主键相等比拟查问 8000 条数据
  • 比照两个 SQL 语句的执行过程，能够发现差别点集中在步骤 2 和步骤 4。在步骤 2 中 SQL 语句 A 须要随机读取整行数据并解析十分耗资源；步骤 4 波及 MySQL 的排序算法，这里也会对执行效率有影响，排序成果上看 SQL 语句 B 比 SQL 语句 A 好。

​

名词解释

  • 主键索引

顾名思义该类索引由表的主键组成，从左到右由小到大排序。一个 Innodb 存储表只有一张主键索引表（汇集索引）。

  • 一般索引

最为平时的一种索引，没有特地限度。

  • 惟一索引

该索引的字段不能有雷同值，但容许有空值。

  • 组合索引

由多列字段组合而成的索引，往往是为了晋升查问效率而设置。

总结

在文章开始时介绍了常见的几种索引数据结构，适宜静态数据的有序数组、适宜 KV 构造的哈希索引及兼顾查问及插入性能的搜寻二叉树；而后介绍了 Innodb 的常见索引实现形式 B+ 树及 Select 语句应用 B+ 树索引查找记录的执行过程，在这个局部咱们理解了几个要害的概念，回表、笼罩索引、最左匹配、索引下推和 MMR；之后还总结了索引的生效场景及背地的起因。最初，咱们回到最后的案例，剖析出优化前后 SQL 语句在应用索引的差别，进而导致执行效率的差别。

本文介绍了索引的一些浅显常识，心愿可能对读者有些许帮忙。作为阶段性学习的一个总结，文章对 MySQL 索引的相干常识基本上是浅藏辄止，日后还需多多应用和深刻学习。

何以解忧？唯有学习。

​

举荐浏览

=====

MySQL 从入门到进阶教程，主讲老师：马士兵、连鹏举

字节跳动总结的设计模式 PDF 火了，完整版凋谢分享

刷 Github 时发现了一本阿里大神的算法笔记！标星 70.5K

如果能听懂这个网约车实战，哪怕接私活你都能够月入 40K

为什么阿里巴巴的程序员成长速度这么快，看完他们的内部资料我懂了

程序员达到 50W 年薪所须要具备的常识体系。

对于【暴力递归算法】你所不晓得的思路

看完三件事❤️

========

如果你感觉这篇内容对你还蛮有帮忙，我想邀请你帮我三个小忙：
点赞，转发，有你们的『点赞和评论』，才是我发明的能源。
关注公众号『Java 斗帝』，不定期分享原创常识。
同时能够期待后续文章 ing????

退出移动版