图片来自 Pexels
具体 sql 如下：
- select * from t_record where age > 10 offset 10000 limit 10
下表所示为表 t_record 结构，为了简单起见，只列了我们将讨论的字段，其余字段省略。
其中 t_record 是要查询的数据表，表中一共有 50000 条记录，age 字段上有索引，且 age>10 的记录有 20000 条。
这条语句非常慢，基本达到了秒级延迟，在第二次请求有缓存之后，才变快。
在数据量这么少的情况下，走索引还这么慢，这完全不能接受，我就问我导师为什么，他反问“索引场景，MySQL 中获得第 n 大的数，时间复杂度是多少?”
答案的追寻
①小白直觉作答
当时只知道 MySQL 索引使用的是树，瞎猜了个 O(logn)，心想二叉树找一个节点不就是 O(logn) 么。自然而然，导师白了一眼，让我自己去研究。
②继续解答
想来想去...只能从底层结构分析了，MySQL 的索引是 B+ 树。仔细想一下，就会发现通过索引去找很别扭。
因为你不知道前 n 个数在其他子树的分布情况，也没有标记让你能快速选择去哪个子树寻找，我们无法利用 B+ 树分支过滤的查找特性。
这下我明白导师的用意了——offset n，就是从第 n 大的数开始找!第 n 大的数没法使用树分支查找，所以 offset，也不能!
回到我们一开始的问题：
- select * from t_record where age > 10 offset 10000 limit 10
通过二级索引 age，我们只能找到对应的起始节点，但无法通过树结构过滤掉 10000 个节点，再获取 10 个节点，因为我们无法知道某个子树下有多少数据，就无法通过分支进行排除。
那该怎么办呢?我们来仔细看下 B+ 树的结构，它不光有常规树的分支结构，底部还有一个由叶子节点组成链表。
显而易见，最方便最快的方式，就是用树定位到起始位置，然后直接通过叶子节点组成的链表，以 O(n) 的复杂度找到第 n 大的数据。
回到我们最初的问题，总结一下：问题的本质其实就是让 offset 找到第 n 大的数，再通过链表遍历，在数据量很大的情况下，确实会慢。
但是即使是 O(n)，也不至于仅有几万数据就慢得令人发指。是不是还有其他影响因素?
③系统学习
我决定深入研究，带着问题去查找了很多资料。
这里推荐两本书，一本《MySQL 技术内幕 InnoDB 存储引擎》，通过它可以对 InnoDB 的底层机制，如 ACID、MVCC、索引实现、文件存储，有更深的理解。
第二本是《高性能 MySQL》，这本书从使用层面着手，讲得比较深入，并提到了很多设计和优化的思路，对日常工作和学习都有很大的帮助。
两本书相结合，反复领会，MySQL 就差不多能登堂入室了。
针对我们的问题，这里介绍两个相关的概念：
- 聚簇索引：包含主键索引和对应的实际数据，索引的叶子节点就是数据节点。
- 辅助索引：也叫二级节点，其叶子节点还是索引节点，并没有完整的数据，仅包含了索引值本身和主键 id，用主键 id 反查聚蔟索引才能获取完整数据。
如图所示，offset 会先从二级索引的链表顺序找 10000 个节点。
注意，即使这 10000 个节点会被扔掉，MySQL 也会通过二级索引上的主键 id，去聚簇索引上查一遍数据，这可是 10000 次随机 IO，自然慢成哈士奇。
大家读到这里可能会提出疑问，为什么 MySQL 会有这种行为?
这和它的优化器有关系，也算是 MySQL 的一个大坑，时至今日，也没有优化。
问题的解决
针对分页性能问题，《高性能 MySQL》中提到了两种方案，让我们一起来看看：
方案一：产品上绕过
根据业务实际需求，看能否替换为上一页、下一页的功能，这样子就可以通过和上次返回数据进行比较，搭上树分支过滤的便车。
特别在 iOS，Android 端，以前那种完全的分页是不常见的。即转换为如下 sql，第一次 last_id 传 0 即可。
- select * from t_record where id > last_id limit 10
优点：
- 能利用树的分支结构，过滤掉第 n 个数之前的数据集。
- 直接通过主键索引查找，省略了二级索引查找过程，性能会更高。
缺点：
- 使用场景其实是受限制的。比如，如果是针对 age 字段有条件判断，再分页，那么使用主键 id 查找就不满足需求。
- 把主键 id 暴露出去了，这个本身不应该是业务层面关心的字段。
可以看到，该方案在我们的场景中，是不适用的。
因为我们还有 age 做过滤条件，此时用大于主键 id 的方式，虽然看起来变成顺序 IO 了，但由于是根据主键 id 排列来寻找，而不是根据需要的 age 索引，所以会导致 MySQL 去查更多的数据。
虽然不符合我们案例的需求，但还是来看看优缺点：
方案二：正面刚
这里先介绍一个概念：索引覆盖。当辅助索引查询的数据只有主键 id 和辅助索引本身，那么就不必再去查聚簇索引。
思路如下：
- select * from t_record id in
- (select id from t_record where age > 10 offset 10000 limit 10）
这句话是说，先从条件查询中，查找数据对应的数据库唯一 id 值，因为主键在辅助索引上就有，所以不用回归到聚簇索引的磁盘上拉取。
如此以来，offset 部分均不需要去反查聚蔟索引，只有 limit 出来的 10 个主键 id 会去查询聚簇索引，这样只会十次随机 IO。
在业务确实需要用分页的情况下，使用该方案可以大幅度提高性能。通常能满足性能要求。
优点：
- 维持了分页需求，适用所有 limit offset 场景，大大减少随机 IO，提高了性能。
- 二级索引上，只查找 id，传输的数据包也变小。
缺点：二级索引上还是会走下面的链表来遍历，这部分时间复杂度还是 O(n)。
方案选型
如果产品本身的需求，是分上下页，且没用其他过滤条件，可以用方案一。
方案二更具有普适性，同时由于合理分表的大小，一般也就 500w，二级索引上 O(n) 的查找损耗，通常也在可接受范围。
总结
从一个小问题，往下深究，不仅可以深入理解这个问题，在面试和工作中大放异彩，同时在探索的过程中，自身的知识储备也能得到拓展，是技术的一个提升捷径。
作者：牛牛码特
编辑：陶家龙
出处：转载自公众号牛牛码特(ID：niuniu_mart)
