图片来自Pexels具体sql如下：select*fromt_recordwhereage>10offset10000limit10表t_record的结构如下表所示。为了简单起见，只列出了我们将要讨论的字段，其余的字段都被省略了。其中，t_record为要查询的数据表。表中一共有50000条记录，age字段上有索引，age>10的记录有20000条。这条语句很慢，基本达到了秒级延迟，第二次请求缓存后变快了。在数据量这么小的情况下，索引还这么慢，这是完全不能接受的。我问我的导师为什么，他问“在索引场景下，MySQL中获取第n大数的时间复杂度是多少？”答案追寻①小白凭直觉回答。当时只知道MySQL的索引用的是树，所以就猜了O(logn)，以为在二叉树中找一个结点就是O(logn)。导师自然是白了我一眼，让我自己研究。②深思熟虑后继续回答……只能从底层结构分析。MySQL的索引是B+树。仔细想想，你会发现通过索引来查找很别扭。因为你不知道前n个数在其他子树中的分布，也没有标记可以让你快速选择查找哪棵子树，所以我们无法利用B+树分支过滤的搜索特性。现在明白导师的用意了——offsetn就是从第n大的数开始找！用树枝是查不到第n大数的，offset也不行！回到我们原来的问题：select*fromt_recordwhereage>10offset10000limit10通过二级索引age，我们只能找到对应的起始节点，但是我们不能通过树结构过滤掉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。select*fromt_recordwhereid>last_idlimit10优点：可以利用树的分支结构，过滤掉第n个数之前的数据集。直接通过主键索引查找，省略二级索引查找过程，性能会更高。缺点：使用场景其实是有限的。比如对age字段进行条件判断，然后分页，那么使用主键id来查找就不符合要求了。主键id暴露了，本身应该不是业务层面关注的领域。可见该方案不适用于我们的场景。因为我们还有age作为过滤条件，这时候使用大于主键id的方法，虽然看起来是顺序IO，但是因为是按照主键id排列，而不是按照requiredageindex，会导致MySQL去查更多的数据。虽然不符合我们案例的需求，但是我们来看看优缺点：方案二：Frontside这里只介绍一个概念：索引覆盖。当辅助索引查询到的数据只有主键id和辅助索引本身时，就不需要再去查找聚簇索引了。思路如下：select*fromt_recordidin(selectidfromt_recordwhereage>10offset10000limit10)这句话的意思是先从条件查询中，找到数据对应的数据库的唯一id值，因为主键存在于辅助索引上，所以有无需返回聚集索引的磁盘上拉。这样offset部分就不需要去查找聚集索引了。只有限制中的10个主键ID将用于查询聚簇索引，因此只会执行十次随机IO。在业务确实需要使用分页的情况下，使用这种方案可以大大提高性能。通常满足性能要求。优点：维护分页需求，适用于所有limitoffset场景，大大减少随机IO，提升性能。在secondaryindex上，只查找id，传输的数据包也减少了。缺点：下面的链表还是会在二级索引上遍历，这部分的时间复杂度还是O(n)。方案选择如果产品本身需要分上下页，且没有使用其他过滤条件，可以使用planone。解决方案2更通用。同时，由于分表的大小比较合理，一般只有500w，二级索引上的O(n)搜索损失通常在可以接受的范围内。综上所述，从一个小问题做起，深入下去，不仅能深入理解问题，还能在面试和工作中大放异彩。同时，在探索的过程中，也可以扩大自己的知识储备，是提升技术的一条捷径。作者：牛牛商城编辑：陶佳龙来源：转载自公众号牛牛商城（ID：niuniu_mart）
