MySQL学习（四）| 索引

前言

索引是数据库中重要的概念，简单来说，索引就像是书的目录一样，其目的就是为了提高数据查询效率。

索引的常见模型

索引的出现是为了提高查找效率，但是实现索引的方式有很多种，这里介绍三种常见的索引结构。

哈希表

哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的值即 key，就可以找到其对应的值即 value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。

和Java类似，当链表过长时会影响查询效率，Java中的HashMap首先是会进行数组的扩容，在一定阈值后将拉链表转换为红黑树。

假设现在维护一个身份证信息和姓名的表，使用哈希索引的示意图如下：

假设，这时候你要查 ID_card_n2 对应的名字是什么，处理步骤就是：首先，将 ID_card_n2 通过哈希函数算出 N；然后，按顺序遍历，找到 User2。需要注意的是，图中四个 ID_card_n 的值并不是递增的，这样做的好处是增加新的 User 时速度会很快，只需要往后追加。但缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的。

所以，哈希表这种结构适用于只有等值查询的场景，而有序数组在等值查询和范围查询的性能都较好。

有序数组

依旧使用上面的例子，如果使用有序数组作为索引结构，示意图如下：

这时候如果你要查 ID_card_n2 对应的名字，用二分法就可以快速得到，这个时间复杂度是 O(log(N))。这种索引结构同样支持范围查询，如果要查身份证号在 [ID_card_X, ID_card_Y] 区间的 User，可以先用二分法找到 ID_card_X（如果不存在 ID_card_X，就找到大于 ID_card_X 的第一个 User），然后向右遍历，直到查到第一个大于 ID_card_Y 的身份证号，退出循环。

如果单纯看查询效率，有序数组是一个不错的存储结构，但当更新数据时，需要移动插入位置后的所有元素，成本较大。因此，有序数据索引结构只适合静态存储引擎

二叉搜搜索树

二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度是 O(log(N))。

为了维持O(log(N))的查询复杂度，需要保持搜索树为平衡二叉树，因此更新元素的时间复杂度也为O(log(N))。

更多情况下并不使用二叉搜索树作为索引。数据库索引不仅存在内存中，还要存储到磁盘里，不可避免的会涉及到读盘操作。二叉搜索树随着节点的增多，树高将不断增长，进行一次查询需要读取的数据块较多，就会导致查询效率降低。

InnoDB的索引模型

在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。每一个索引在InnoDB里面对应一棵B+树。

假设有这么一个表，主键列为ID，表中有字段k，并且在k上有索引。建表语句如下：

create table T (
	id int primary key,
	k int not null,
	name varchar(16),
	index(k)), engine = InnoBD;

表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下：

根据叶子节点的内容不同，索引类型分为 主键索引 和 非主键索引 。

主键索引的叶子节点存储的是整行数据，在InnoDB里，主键索引也称为 聚簇索引 。
非主键索引的叶子节点存储的内容是主键的值，在InnoDB里，非主键索引也称为 二级索引 。

也因为这种存储结构，基于主键索引的查询和普通索引存在区别：

如果查询语句是 select * from T where ID = 500，也就是主键查询的方式，那么只需要搜索ID这棵B+树。
如果查询语句是 select * from T where k = 5，也就是普通索引的方式，那么需要先搜索字段k这棵索引树，得到对应的主键ID值为500，再利用ID搜索ID索引树，这个过程也成为回表。

也就是说， 基于非主键索引的查询需要多扫描一棵索引树，所以如果可以的话尽量使用主键索引。

索引维护

数据页

在讲述索引维护之前，先简单了解一下MySQL数据页的概念。 页（Pages）是 InnoDB 中管理数据的最小单元。Buffer Pool中存的就是一页一页的数据。再比如，当我们要查询的数据不在 Buffer Pool 中时，InnoDB 会将记录所在的页整个加载到 Buffer Pool 中去；同样的，将 Buffer Pool 中的脏页刷入磁盘时，也是按照页为单位刷入磁盘的。

存储MySQL中的数据最后都是存储在页中的，在InnoDB的设计中，页与页之间是通过一个 双向链表连接起来的。如下图所示：

而存储在页中的一行一行记录则是通过单链表连接起来的。如下图所示：

维护

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。使用上面的例子，如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400需要逻辑上挪动后面的数据，空出位置。更糟的情况是，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率会下降。有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。

自增主键or其他字段

在很多建表规范中，要求建表语句中定义自增主键。也就是 NOT NULL PRIMARY KEY AUTO_INCREMENT。这时候插入新数据时，可以不指定ID的值，系统会获取当前ID最大值加1作为下一条记录的ID值。为什么使用自增主键可以从性能和存储两个方面考虑。

使用自增主键，每次插入一条新记录，都是追加操作，不涉及挪动其他记录，也不会触发叶子节点的分裂。使用业务字段做主键，往往不容易保证有序插入，写入数据的成本较高。
从存储角度考虑，假如在表中有唯一字段身份证号（字符串类型），那么还需要使用自增主键吗？——因为每个非主键索引的叶子节点上存放的都是主键的值，因此如果使用身份证号作为主键，占用的空间显然是比自增主键要来的大的。

有没有什么场景适合用业务字段直接做主键的呢？还是有的。比如，有些业务的场景需求是这样的：

只有一个索引；
该索引必须是唯一索引。

也就是典型的 KV 场景，由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树。

一个索引搜索的例子

有如下的一张表，若执行 select * from T where k between 3 and 5，需要经过几次树的搜索操作，会扫描多少行？表初始化语句如下：

create table T (
	ID int primary key,
	k int NOT NULL DEFAULT 0, 
	s varchar(16) NOT NULL DEFAULT '',
	index k(k))
		engine=InnoDB;
 
insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff');

此时SQL语句执行的查询流程如下：

在 k 索引树上找到 k=3 的记录，取得 ID = 300；
再到 ID 索引树查到 ID=300 对应的 R3；
在 k 索引树取下一个值 k=5，取得 ID=500；
再回到 ID 索引树查到 ID=500 对应的 R4；
在 k 索引树取下一个值 k=6，不满足条件，循环结束。

在这个过程中， 回到主键索引树搜索的过程，称为回表。这个查询过程读了 k 索引树的 3 条记录（步骤 1、3 和 5），回表了两次（步骤 2 和 4）。由于查询结果所需要的数据只在主键索引上有，所以不得不回表，这时候就可以考虑优化索引来避免回表。

覆盖索引

如果执行的语句是 select ID from T where k between 3 and 5，因为ID的值已经在k索引树上，所以不需要回表。在这个查询里面，索引k已经“覆盖了”查询需求，因此称为覆盖索引。 覆盖索引可以减少树的搜索次数，提升查询性能，所以一个常用的优化手段就是使用覆盖索引。

因此，如果有高频请求查询非主键字段，可以考虑建立联合索引来避免回表。

令表中字段为a、b、c、d，其中a为主键。对于一个二级索引b，若查询条件为b，且查询内容不是主键，那么需要回表查询；若存在联合索引（b，c），当查询内容不是主键，但为c时，为覆盖索引，不需要回表。

最左前缀原则

B+树这种索引结构，可以利用索引的“最左前缀”来定位记录。

假设存在(name，age)的联合索引，其示意图如下：

当你的逻辑需求是查到所有名字是“张三”的人时，可以快速定位到 ID4，然后向后遍历得到所有需要的结果。如果要查的是所有名字第一个字是“张”的人，你的 SQL 语句的条件是 where name like ‘张 %’。这时，也能够用上这个索引，查找到第一个符合条件的记录是 ID3，然后向后遍历，直到不满足条件为止。

可以看到，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

在建立联合索引时，需要考虑的是 索引的复用能力以及 占用的空间：

索引的复用能力，如果通过调整顺序可以少维护一个索引，那么这个顺序往往就是优先考虑采用的。
对于联合索引（a，b），当查询条件里面只有b时，是无法使用上联合索引的。此时可能需要再维护一个b的索引，因此这时候可以考虑a、b两个字段占用的空间大小来抉择。

索引下推

以一个联合索引（name，age）为例，如果有一个需求，检索出表中“名字第一个字是张，而且年龄是 10 岁的所有男孩”。SQL语句如下：

select * from t where name like '张 %' and age=10 and ismale=1;

由于存在前缀索引规则，这个语句会先使用“张”来搜索索引树，找到第一个满足条件的记录。在旧版本的MySQL中，由于没有索引下推的优化，在匹配到第一条满足条件的记录后便会一条一条的回表查询，引入索引下推后，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。两者的执行流程图如下：

两个流程的区别是，InnoDB 在 (name,age) 索引内部就判断了 age 是否等于 10，对于不等于 10 的记录，直接判断并跳过。在这个例子中，只需要对 ID4、ID5 这两条记录回表取数据判断，就只需要回表 2 次。如果没有索引下推， InnoDB 并不会去看 age 的值，只是按顺序把“name 第一个字是’张’”的记录一条条取出来回表。因此，需要回表 4 次。

延伸问题

如果自增主键用完了怎么办？

先简单回答一下，对于自增主键用完可以使用MySQL提供的线上修改方式或者第三方工具，修改字段类型，增加自增主键的数据范围，如改为BigInt。但细想，其实这个问题既成立又不成立，对于一个int类型作为自增主键，其数据范围是0～2147483648，单表21亿条数据，就算考虑ID断序的问题，那么也有十几亿条数据，显然查询的效率不会太高。这时候就需要考虑到分库分表，一旦分库分表，就不能依赖每个表的自增主键来全局唯一标识数据了，这时候就需要类似雪花算法、UUID等来提供全局唯一ID的生成。

前言