六年前牛牛开始工作的时候，他发现在分页场景下，当offset变大的时候，MySQL的处理速度很慢！具体SQL如下：select*fromt_recordwhereage>10offset10000limit10表t_record的结构如下表所示。为了简单起见，只列出了我们将要讨论的字段，其余的字段都被省略了。字段名类型说明idbigint(20)unsignedprimarykeyidageintage其中t_record为要查询的数据表。表中有50,000条记录。age字段上有索引，age>10的记录有20000条。这条语句很慢，基本达到了秒级延迟，第二次请求缓存后变快了。这么小的数据量，索引还是这么慢，完全不能接受。我问我的主管为什么，他问“在索引场景下，MySQL中获取第n大数的时间复杂度是多少？”答案当时只知道MySQL的索引用的是树，所以我猜是O(logn)，以为在二叉树中找一个结点是O(logn)。导师自然是白了我一眼，让我自己研究。想来想去继续回答……只能从底层结构来分析。MySQL的索引是B+树。仔细想想，你会发现通过索引来查找很别扭。因为你不知道其他子树的前n个数的分布，也没有标记可以让你快速选择搜索哪棵子树，所以我们无法使用B+树分支过滤的搜索特性。现在明白指导老师的用意了——偏移n，也就是从第n大的数开始找！用树枝是查不到第n大数的，所以offset也不行！回到我们最开始的问题：select*fromt_recordwhereage>10offset10000limit10通过secondaryindexage，我们只能找到对应的起始节点，但是我们无法通过树结构过滤掉10000个节点，然后得到10个节点，因为我们没有办法知道某个子树下有多少数据，不能通过分支排除。那么该怎么办？让我们仔细看看B+树的结构。它不仅具有常规树的分支结构，而且在底部还有一个由叶子节点组成的链表。显然，最方便快捷的方法就是用树定位起始位置，然后直接用叶子节点组成的链表找第n大的数据，复杂度为O(n)。回到我们原来的问题，总结一下：问题的本质就是让offset找到第n大的数，然后遍历链表。在数据量很大的情况下，确实会很慢。但是即使是O(n)，也没有慢到只有几万条数据。还有其他影响因素吗？妞妞决定深入研究一下这个系统，带着疑问查了很多资料。这里推荐两本书，一本《MySQL技术内幕 InnoDB存储引擎》，通过它可以更深入地了解InnoDB的底层机制，如acid、mvcc、索引实现、文件存储等。第二本书是《高性能MySQL》。本书从使用层面入手，深入浅出，提及大量设计和优化思路，对日常工作和学习很有帮助。结合两本书，反复理解，MySQL差不多可以进屋了。针对我们的问题，这里有两个相关的概念：聚簇索引：包含主键索引和对应的实际数据，索引的叶子节点就是数据节点；辅助索引：也叫二级节点，它的叶子节点仍然是索引节点，没有完整的数据，只有索引值本身和主键id，完整的数据可以通过对簇索引进行逆向得到主键ID。如图所示，offset会先从二级索引的链表中依次找到10000个节点。注意，即使这10000个节点会被扔掉，MySQL也会通过二级索引上的主键id来检查聚簇索引上的数据。这是10000个随机IO，自然比Husky慢。读到这里你可能会问，为什么MySQL会有这种行为？这和它的优化器有关系，也算是MySQL的一个大坑。即使在今天，它也没有得到优化。问题解决针对分页性能问题，《高性能MySQL》中提到了两种解决方案，一起来看看：解决方案一：产品上的Bypass根据业务的实际需求，看能不能换成上一页或下一页功能，以便您可以通过与上次返回的数据进行比较来搭便车树枝过滤。尤其是ios和android端，以往完全分页的情况并不常见。也就是转换成下面的sql，第一次传last_id为0。2、直接通过主键索引查找，省略二级索引查找过程，性能会更高。缺点1.使用场景实际上是有限的。比如age字段有条件判断，然后进行分页，那么使用主键id查找不符合要求；2.主键id暴露了，本身应该不是业务层面关注的领域。可见该方案不适用于我们的场景。因为我们还有age作为过滤条件，所以这个时候，我们使用大于主键id的方法。虽然看起来变成了顺序IO，但是因为是按照主键id排列查找，而不是按照需要的age索引，所以会导致mysql去checkout更多的数据。虽然不符合我们案例的需求，但是我们来看看优缺点：方案二：前面只是介绍一个概念：索引覆盖：当辅助索引查询到的数据只有主键时id和辅助索引本身，则无需再次搜索聚簇索引。思路如下：select*fromt_recordidin(selectidfromt_recordwhereage>10offset10000limit10)这句话的意思是先从条件查询中，找到数据对应的数据库的唯一id值，因为主键存在于辅助索引上，所以有无需返回聚集索引的磁盘上拉。这样offset部分就不需要去检查聚集索引了。只有限制中的10个主键ID将用于查询聚簇索引，因此只会执行十次随机IO。在业务确实需要使用分页的情况下，使用这种方案可以大大提高性能。通常满足性能要求。优点1.维护分页需求，适用于所有limitoffset场景，大大减少随机IO，提升性能；2.在二级索引上，只查找id，传输的数据包也减少了。缺点是后面的链表还是会在二级索引上遍历，这部分的时间复杂度还是O(n)。方案选择如果产品本身需要分上下页，且没有使用其他过滤条件，可以使用planone。解决方案2更通用。同时，由于分表的大小比较合理，一般只有500w，二级索引上的O(n)搜索损失通常在可以接受的范围内。综上所述，从一个小问题做起，深入下去，不仅能深入理解问题，还能在面试和工作中大放异彩。同时，在探索的过程中，也可以扩大自己的知识储备，是提升技术的一条捷径。祝你工作顺利，牛牛玛特！
