MySQL 索引知识点总结

【转载】【腾讯技术工程】MySQL 索引知识点总结：https://mp.weixin.qq.com/s/QduIxKOykMmoZp13UGF1XQ

作者：fanili，腾讯 WXG 后台开发工程师

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

什么是索引？

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

索引的目的是提高查找效率，对数据表的值集合进行了排序，并按照一定数据结构进行了存储。

本文将从一个案例开始，从索引的数据结构、分类、关键概念及如何使用索引提高查找效率等方面对索引知识进行总结。

从一个案例开始

现象

业务中有个既存的历史 SQL 语句在运行时会导致 DB 服务器过载，进而导致相关服务阻塞无法及时完成。CPU 监控曲线如下：

索引的数据结构

在 MySQL 中，索引是在存储引擎层实现的，而不同的存储引擎根据其业务场景特点会有不同的实现方式。这里会先介绍我们常见的有序数组、Hash 和搜索树，最后看下 Innodb 的引擎支持的 B+树。

有序数组

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

ID：1	ID：2	......	ID:N
name2	name2	......	nameN

// 二分查找递归实现方式
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 次数更少
每次都需要查询到叶子节点，查询性能稳定
叶子节点形成有序链表，范围查询方便

操作算法

查找由根节点自顶向下遍历树，根据分离值在要查找的一边的指针；在节点内使用二分查找来确定位置。
插入
删除

注：插入和删除两个表格内容来自《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');


* 索引结构示意

![image](https://user-images.githubusercontent.com/13992911/102578938-57ae1d00-4136-11eb-8ee6-ffcc1c4ea1c4.png)

左边是以主键 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 结果：
![image](https://user-images.githubusercontent.com/13992911/102579054-a8257a80-4136-11eb-86df-d53bc5baa9f5.png)

SQL 语句 B:

explain select emp_no from employees where hire_date > '1990-01-14';

explain 结果：
![image](https://user-images.githubusercontent.com/13992911/102579084-bd020e00-4136-11eb-9e25-482cef5a3068.png)

* 分析
从前后两次 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%';

TFdream / blog