返回
学习

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索引组织结构

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

  • 主键索引的叶子节点存储的是整行数据，在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值。为什么使用自增主键可以从性能和存储两个方面考虑。

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

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

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

也就是典型的 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');

当前表的InnoDB索引组织结构
当前表的InnoDB索引组织结构

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

  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，不满足条件，循环结束。

在这个过程中， 回到主键索引树搜索的过程，称为回表。这个查询过程读了 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 次。

普通索引和唯一索引

查询过程

还是使用上文所述的身份证的例子，执行的查询语句为 select id from T where k=5 （k值是不重复的）。这个查询语句在索引树上查找的过程，先是通过 B+ 树从树根开始，按层搜索到叶子节点，然后可以认为数据页内部通过二分法来定位记录。

  • 对于普通索引来说，查找到满足条件的第一个记录 (5,500) 后，需要查找下一个记录，直到碰到第一个不满足 k=5 条件的记录。
  • 对于唯一索引来说，由于索引定义了唯一性，查找到第一个满足条件的记录后，就会停止继续检索。

由于InnoDB的数据是按数据页为单位来读写的。当需要读一条记录的时候，并不是将这个记录本身从磁盘读出来，而是以页为单位，将其整体读入内存（页大小默认为16KB）。对于普通索引来说，要多做的那一次“查找和判断下一条记录”的操作，就只需要一次指针寻找和一次计算，如果 k=5 这个记录刚好是这个数据页的最后一个记录，那么要取下一个记录，必须读取下一个数据页，这个操作会稍微复杂一些。 因此，其实两类索引在这个案例上的性能差异几乎为零。

更新过程

change buffer

当需要更新一个数据页时，如果数据页在内存中就直接更新，而如果这个数据页还没有在内存中的话，在不影响数据一致性的前提下，InooDB 会将这些更新操作缓存在 change buffer 中，这样就不需要从磁盘中读入这个数据页了。在下次查询需要访问这个数据页的时候，将数据页读入内存，然后执行 change buffer 中与这个页有关的操作。

将 change buffer 中的操作应用到原数据页，得到最新结果的过程称为 merge。除了访问这个数据页会触发 merge 外，系统有后台线程会定期 merge。在数据库正常关闭（shutdown）的过程中，也会执行 merge 操作。change buffer实际上也是可以持久化的，在内存中有拷贝也会写入磁盘。

change buffer的使用条件

对于唯一索引来说，所有的更新操作都要先判断这个操作是否违反唯一性约束。比如，要插入 (4,400) 这个记录，就要先判断现在表中是否已经存在 k=4 的记录，而这必须要将数据页读入内存才能判断。如果都已经读入到内存了，那直接更新内存会更快，就没必要使用 change buffer 了。所以， 唯一索引的更新就不能使用 change buffer，实际上也只有普通索引可以使用。

因此回到表中，如果要在表插入一条新的记录(4,400)，InnoDB的处理流程可以分为两种情况：

  1. 这个记录 要更新的目标页在内存中。

    • 对于 唯一索引 来说，找到3和5之间的位置，判断有没有冲突，插入这个值，语句执行结束。
    • 对于 普通索引 来说，找到3和5之间的位置，插入这个值，语句执行结束。

    可以看出，这种情况下，两种索引之间的区别仅仅只是判断有没有冲突，因此性能差距不大。

  2. 这个记录 要更新的目标页不在内存中。

    • 对于 唯一索引 来说，需要将数据页读入到内存中，判断有没有冲突，插入这个值，语句执行结束。
    • 对于 普通索引 来说，则是将更新记录在change buffer，语句执行就结束了。

    将数据从磁盘中读取内存涉及IO访问，成本较高，而change buffer就是避免了这一操作，对更新性能的提升是较为明显的。

change buffer使用场景

上面提到了change buffer适用于普通索引情况下，而不适用于唯一索引。那 是否所有的普通索引，使用change buffer都可以起到加速作用？

因为 merge 的时候是真正进行数据更新的时刻，而 change buffer 的主要目的就是将记录的变更动作缓存下来，所以在一个数据页做 merge 之前，change buffer 记录的变更越多（也就是这个页面上要更新的次数越多），收益就越大。所以， 对于写多读少的业务来说，页面在写完以后马上被访问到的概率比较小，此时 change buffer 的使用效果最好。 这种业务模型常见的就是账单类、日志类的系统。 反过来，假设一个业务的更新模式是写入之后马上会做查询，那么即使满足了条件，将更新先记录在 change buffer，但之后由于马上要访问这个数据页，会立即触发 merge 过程。这样随机访问 IO 的次数不会减少，反而增加了 change buffer 的维护代价。 所以，对于这种业务模式来说，change buffer 反而起到了副作用。

从上面的描述可以看出，在这两种索引的选择上，尽量选择普通索引，如果数据的更新伴随着查询，那么就应该关闭change buffer。 普通索引+change buffer 在数据量大的表中其实就能够起到不错的优化效果了。

至于MySQL怎么创建普通索引，如下所示（同时也列举了其他一些索引的创建方式）。

# 直接在建立表的时候就创建索引
CREATE TABLE users (
    id INT PRIMARY KEY,
    username VARCHAR(50),
    email VARCHAR(100),
    INDEX idx_username (username),       -- 普通索引
    UNIQUE INDEX idx_email (email),     -- 唯一索引
    PRIMARY KEY (id)                    -- 主键索引
);

# 创建完表之后再添加索引
-- 添加普通索引
ALTER TABLE users ADD INDEX idx_age (age);
-- 添加唯一索引
ALTER TABLE users ADD UNIQUE INDEX idx_phone (phone);
-- 添加复合索引
ALTER TABLE orders ADD INDEX idx_customer_date (customer_id, order_date);

change buffer和redo log

假设要在表中执行以下的插入语句 insert into t(id, k) values(d1, k1), (id2, k2); 假设当前k1所在的数据页page1在内存中，k2所在的数据页page2不在内存中。其更新状态如下图所示：

带change buffer的更新过程
带change buffer的更新过程

这条更新语句做了如下几个操作：

  1. Page 1 在内存中，直接更新内存；
  2. Page 2 没有在内存中，就在内存的 change buffer 区域，记录下“要往 Page 2 插入一行”这个信息
  3. 将上述两个动作记入 redo log 中（图中 3 和 4）。

做完这些之后，事务就可以完成了。那么之后的读请求要如何处理呢？假设之后要执行 select * from t where k in (k1, k2); 如果内存中的数据都还在，那么读过程如下图所示：

带change buffer的读过程
带change buffer的读过程

从图中可以看出：

  1. 读 Page 1 的时候，直接从内存返回。

    这里也说明了WAL之后读数据并不一定要等待redo log将数据写入磁盘。只要内存中的数据是正确的，就可以直接从内存中读取。

  2. 要读 Page 2 的时候，需要把 Page 2 从磁盘读入内存中，然后应用 change buffer 里面的操作日志，生成一个正确的版本并返回结果。

总结来说就是， redo log 主要节省的是随机写磁盘的 IO 消耗（转成顺序写），而 change buffer 主要节省的则是随机读磁盘的 IO 消耗。

延伸问题

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

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

参考

  1. MySQL45讲——04 深入浅出索引（上）
  2. MySQL45讲——05 深入浅出索引（下）
  3. MySQL 页完全指南——浅入深出页的原理 - 知乎
  4. MySQL中的自增主键用完了怎么办？
  5. MySQL45讲——09 普通索引和唯一索引，应该怎么选择？
© 2025 墨纹
你要相信流星划过会带给我们幸运，就像现实告诉你我要心存感激