明确场景

要答复这个问题，咱们个别分几步来走：

1.确认问题，对齐Sql语句；

2.解答问题自身，也就是工夫复杂度剖析；

3.针对自身提出这个场景，可能呈现的性能瓶颈进行剖析；

4.针对瓶颈，提出多种优化伎俩。

接下来咱们就依照这个思路来一步步深刻。

对齐Sql语句

通常而言，面试官抛出一个问题，不见得就是一个十分欠缺、十分精确的形容，他其实是心愿你能提出问题，通过沟通对齐，这也是工作中必备的能力。

首先问面试官，目前表的构造大略是怎么，索引的建设，又是怎么的，假如通过沟通，咱们失去如下简化过的表t_player：

只在score字段上建了二级索引，大小是从小到大。这里要找第k个，其实就是偏移k-1：

select * from t_player order by

工夫复杂度剖析

这个问题的外围就是查找语句的工夫复杂度是多少？

这道题理论是有肯定引导性的，成心说索引，就是想让你往树分支上引，咱们都晓得，走索引，按数值自身查找一个数据，那二级索引的工夫复杂度，必定是O(logN)。

但这题不一样，是找第k个，比方第100个，咱们其实是不晓得树的分支构造具体是怎么的，也就是说咱们不晓得左子树有多少个节点，右子树有多少个节点。

进一步而言，咱们没法确定走哪条路，树的分支构造不可行。

所以这里其实是考查B+树的了解，B+树除了分支，底层还有一个双链表，间接走双链表查问，反而是更快的了。

工夫简单读O(N)，咱们反过来想，其实这道题就是考你B+树数据结构，如果间接问你B+树结构，大多数有筹备的同学，都能答复分明，然而通过一个理论问题来问你，只有真正了解其作用，能力疾速答出。

这就完了吗？当然没有，这只是一个起手式，下一步，面试官必定会问你这个操作的性能如何，当然你也能够被动谈起。

offet慢问题

如果offset大于10000，这个数据查问就会十分的慢。为什么会慢呢，个别都会答因为遍历，工夫复杂度是O(N)。

但理论如果你测试一下，你会发现这条语句会慢得离谱，这绝不是所谓遍历能导致的。

更深层次的起因在于，对于前10000个不须要的数据，MySQL每次也要回表去查找，这就导致了10000次随机IO，当然慢成狗。

优化计划

如果有开发教训的同学，会很容易想到从业务状态下来优化，这里就不卖关子了，这种场景通常有三种解决方案。

1.业务上绕过

将limit、offset，改为next，也就是将第x页，改为下一页，这样就

能够通过树分支查找。

举个例子，百度的搜寻界面，就是典型的分页面。

而当初挪动互联网时代，用得更多的就是上一页、下一页这样的翻页逻辑，微博、抖音都是这样的逻辑。

--- 记录score为prev_score

应用这种模式，能够利用树索引间接找到指标，也绕过了有效回表问题，在Offset超过一万的状况下，性能通常都能进步两个量级以上。

当然，这种适宜给分页做优化，如果回到咱们题目自身来说，那查找第k大的数，就须要循环“下一页”上来，损耗反而更大。

2.硬碰硬

下面剖析了，对无用数据还回表查问，导致大量随机IO，是性能的外围瓶颈，那咱们隔靴搔痒，是否不回表呢？

当然能够，咱们能够进行索引笼罩。

索引笼罩是说当二级索引查问的数据都在二级索引自身，比方索引Key或主键ID，那么就不用再去查聚簇索引。

那你可能会问，在咱们的场景，还有其它须要查问的信息，比方名字，并不在二级索引上啊。

是的，但咱们能够通过sql的拆分，来达到目标，思路如下：

select * from t_player id in 

这句话是说，先从条件查问中，查找数据对应的数据库惟一id值，因为主键在辅助索引上就有，所以不必回归到聚簇索引的磁盘上拉取。

如此以来，offset局部均不须要去反查聚蔟索引，只有limit进去的10个主键id会去查问聚簇索引，这样只会1次IO。在业务的确须要用分页的状况下，应用该计划能够大幅度提高性能，通常能满足性能要求。有同学可能放心自身走B+树的双指针会是瓶颈，牛哥也做了测试：一张500w的表，offset 10000，要是没索引笼罩，解决工夫甚至能够达到十秒级，有了的话，能升高到十毫秒级，有质的飞跃。ps:具体时耗和数据库性能等因素无关，以上数据只是参考。

3.预判边界值

这其实也是依据业务场景的做法，能通过业务预判边界，这种形式并不是通用解决方案，但因为《高性能MySQL》中提到了，也一并列进去。

深层次灵魂提问

为什么MySQL不间接丢掉无用数据，还要傻乎乎地回表？

兴许你已经听过一个词，叫索引下推，在MySQL5.6之后，MySQL通过索引下推晋升了性能。

这个问题也相似，答案是Offset未曾下推！咱们先review下查找流程：

1.存储引擎通过二级索引查找，获取主键值；2.进行回表操作，将残缺记录返回给下层；3.下层判断是否须要该记录，须要则返回给客户端，不须要则跳过该记录；4.存储引擎接着查找下一条；

5.反复第二步。

从流程其实咱们能看出，存储引擎层是没有Offset信息的。

牛哥和咱们训练营导师虎哥也探讨过这个问题，虎哥的解释还是比拟到位的：

MySQL不做的起因，无非两点：

1.限度场景太多，给多个引擎做有点得失相当；

2.更外围的，分层设计理念，这件事自身是Sql层的，本就不该存储引擎做。

家养db

那咱们当初来看看所谓的家养db的状况：

家养db1号：阿里云

家养db 2号：腾讯云

另外，腾讯云还形容了实用场景：

下推之后阿里云测试了性能，Q3即咱们二级索引order by ... limit回表的场景，能够看到从25s升高到了329ms左右，相差75.82倍。

能够发现阿里腾讯两大云厂商MySQL自研版本都做了下推，那MySQL从技术上天然也能。

有大佬针对这个问题还给MySQL提了bug。https://bugs.mysql.com/bug.ph...

还带了修复计划：

https://bugs.mysql.com/file.p...

当然mysql有本人的设计理念和保持，可能当前也不会驳回。

而将阿里云、腾讯云这些称为家养db，其实也只是调侃的说法。

实际上他们都遵循实用准则，是十分优良的团队，自研产品的决策灵活性自身也更高一些。

这倒不是非要分个孰优孰劣，大家搞清楚前因后果即可。

补丁剖析

尽管咱们曾经将前因后果弄得很分明，但置信还是会有同学好奇，下面的大佬做的补丁，到底是怎么的。牛哥和虎哥，也做了一些剖析。

外围因素就是在引擎层减少了这么一个函数，能够下推索引。

这个函数有几层，最外围的其实在这里：

其实就是offset判断，如果offset比当初的遍历偏移还大，就跳过。

Sql层会调用引擎层这个函数，当然调用之前会有个判断。

很简单是吧，没事，咱们看注解：

其实就是限度了很多状况，比方group by，having这种推了也不顶用的，就不推了。

Review一下

能够看到，看起来很简略的一个问题，其实牵涉到的常识很广：

首先工夫复杂度是多少？考查B+树结构；

Offset为什么慢？考查对底层行为肯定水平的把握；

几种解决方案？考查技术视线和解决问题的能力；

深层次行为起因？考查MySQL分层架构，及对开源社区的关注。

如果你只是背八股文，而不去深刻摸索其中的原理，那面试官轻易问几个问题，就能看出你其实根底是不扎实的。

这里不是说八股文不好，而是不能感觉面试就是考八股文，这其实是一个很大的误区。