一般会使用三种算法：
哈希分库分表：
根据分库分表键算出一个哈希值，根据这个哈希值选择一个数据库。最常见的就是数字类型的字段作为分库分表键，然后取余。比如在订单表里，可以按照买家的ID除以8的余数进行分表
范围分库分表：
将某个数据按照范围大小进行分段。比如说根据ID，
[0,1000)
在一张表，
[1000,2000)
在另外一张表。最常见的应该是按照日期进行分库分表，比如每个月一张表
中间表：
引入一个中间表来记录数据所在的目标表。一般是记录主键到目标表的映射关系。
这三者并不互斥，也就是说可以考虑使用哈希分库分表，同时引入一个中间表；也可以先进行范围分库分表，再引入一个中间表。
基于 Spring Boot + MyBatis Plus + Vue & Element 实现的后台管理系统 + 用户小程序，支持 RBAC 动态权限、多租户、数据权限、工作流、三方登录、支付、短信、商城等功能
项目地址：https://github.com/YunaiV/ruoyi-vue-pro
视频教程：https://doc.iocoder.cn/video/
SDK形态：
通过依赖的形式引入代码里，比如Java的依赖ShardingSphere
Proxy形态：
独立部署的分库分表中间件，对于所有的业务方来说，就像一个普通的数据库，业务方的查询发送过去后，就会执行分库分表，发起实际的查询，再把查询结果返回给业务方。ShardingSphere也支持这种形态。
Sidecar形态：
提供了一个分库分表的Sidecar，但是现在并没有非常成熟的产品
Sidecar是一种分库分表中间件的形态。它是一个理论上的概念，指的是一个独立的组件，为应用程序提供分库分表的功能。在这种形态下，Sidecar作为应用程序的伴随服务运行，类似于服务网格中的Sidecar容器，它与应用程序实例部署在一起，但作为独立的进程运行。
其中，SDK形态的性能最好，但是和语言强耦合。
Proxy形态性能最差，因为所有的数据库查询都发送给它了，很容易成功性能瓶颈。尤其单机部署Proxy的话，还面临着单节点故障的问题。优点是跟编程语言无关，部署一个Proxy之后可以给使用不同编程语言的业务使用。同时，业务方可以轻易地从单库单表切换到分库分表。
Sidecar 目前还没有成熟的产品，但是从架构上来说它的性能应该介于 SDK 和 Proxy 之间，并且也没有单体故障、集群管理等烦恼。
基于 Spring Cloud Alibaba + Gateway + Nacos + RocketMQ + Vue & Element 实现的后台管理系统 + 用户小程序，支持 RBAC 动态权限、多租户、数据权限、工作流、三方登录、支付、短信、商城等功能
项目地址：https://github.com/YunaiV/yudao-cloud
视频教程：https://doc.iocoder.cn/video/
还需要弄清楚几个问题：
有没有因为排序或分页而引起的性能问题？最终怎么解决的
还可以去看看公司的监控数据，注意下分页查询的响应时间。并且在业务高峰期或是频繁执行分页的时候，看看内存和CPU的使用率。这些数据可以作为分页查询比较引起性能问题的证据。
面试策略上来说，最好把分页查询优化作为你性能优化的一个举措，可以进一步和前面的查询优化、数据库参数优化相结合，这样方案会更完善，能力会更全面。
如果面试官问到了数据库性能优化和数据库分页查询，你都可以尝试把话题引导到分页查询上。
可以尝试介绍一下是如何优化数据库性能的，比如SQL本身优化、数据库优化，然后罗列出准备的SQL案例，说明你在SQL优化方面做过哪些事情，比如优化过分库分表的查询，其中最典型的就是优化分页查询。
假设之前是全局查询，现在采用禁用跨页查询的方案来优化
最开始我在公司监控慢查询的时候，发现有一个分页查询非常慢。这个分页查询是按照更新时间降序来排序的。后来我发现那个分页查询用的是全局查询法，因为这个接口原本是提供给 Web 端用的，而 Web 端要支持跨页查询，所以只能使用全局查询法。当查询的页数靠后的时候，响应时间就非常长。后来我们公司搞出 App 之后，类似的场景直接复用了这个接口。但是事实上在 App 上是没有跨页需求的。所以我就直接写了一个新接口，这个接口要求分页的时候带上上一页的最后一条数据的更新时间。也就是我用这个更新时间构造了一个查询条件，只查询早于这个时间的数据。那么分页查询的时候 OFFSET 就永远被我控制在 0 了，查询的时间就非常稳定了。
最后你可以加一个总结。
分页查询在分库分表里面是一个很难处理的问题，要么查询可能有性能问题，比如说这里使用的全局查询法，要么就是要求业务折中，比如说我优化后禁用了跨页，以及要求数据平均分布的平均分页法，当然还有各方面都不错，但是实现比较复杂的二次查询法、中间表法。
当面试官追问你其中细节的时候，你就可以这样来引导。
理论上说，分页查询要在全局有序的情况下进行，但是在分库分表以后，要做到全局有序就很难了。假如说我们的数据库
order_tab
是以
buyer_id % 2
来进行分表的，如果你要执行一个语句
SELECT
* FROM order_tab ORDER BY id LIMIT 4 OFFSET 2
实际执行查询的时候，就要考虑各种数据的分布情况。
符合条件的数据全部在某个表里面。在这就是
order_tab_0
上有全部数据，或是
order_tab_1
上有全部数据。
偏移量中前面两条全部在一张表，但是符合条件的数据在另外一张表
偏移量和数据在两张表都有
在分库分表中，一个SELECT语句生成的目标语句是这样的：
SELECT * FROM order_tab ORDER BY id LIMIT 6 OFFSET 0 SELECT * FROM order_tab ORDER BY id LIMIT 6 OFFSET 0
注意看LIMIT部分，被修改成了0,6。通俗的说，如果一个分页语句是
LIMIT x OFFSET y
的形式，那么最终生成的目标语句就是
LIMIT x + y OFFSET 0
。
LIMIT x OFFSET y => LIMIT x+y OFFSET 0
当分库分表中间件拿到这两个语句的查询结果之后，就要在内存里进行排序，再找出全局的
LIMIT 4 OFFSET 2
可以先回答这种全局排序的思路，关键词就是
LIMIT x + y OFFSET 0
分库分表中间件一般采用的就是全局排序法。假如说我们要查询的是LIMIT X OFFSET y，那么分库分表中间件会把查询改写为LIMIT x+y OFFSET 0，然后把查询请求发送给所有的目标表。在拿到所有的返回值后，在内存中排序，然后根据排序结果找出全局符合条件的目标数据。
接下来可以先从性能问题上刷一个亮点，抓住受影响的三个方面：
网络、内存和CPU
这个解决方案的最大问题就是性能不好。
首先是网络传输瓶颈，比如在
LIMIT 10 OFFSET 1000
这种场景下，如果没有分库分表，只需要传输10条数据；在分库分表的情况下，如果命中了N个表，那么需要传输的是
(1000+10)*N条数据
。而实际上最终我们只会用其中的10条数据，存在巨大的浪费。
其次是内存瓶颈。收到那么多数据之后，中间件需要维持在内存中排序。
CPU也会成为瓶颈，因为排序本身是一个CPU密集的操作。所以在Proxy形态的分库分表中间件里，分页查询一多，就容易把中间件的内存耗尽，引发OOM，又或是CPU 100%。
不过可以通过归并排序来缓解这些问题。
关键在拿到数据之后，使用归并排序的算法。
在分库分表里，可以使用归并排序算法来给返回的结果排序，也就是说在改写为
LIMIT x+y OFFSET 0
之后，每个目标表返回的结果都是有序的，自然可以使用归并排序。在归并排序的过程中，我们可以逐条从返回结果中读取，这意味着没必要将所有的结果一次性放到内存中再排序。在分页的场景下，取够了数据可以直接返回，剩下的数据就可以丢弃了。
前面说了全局查询这个方案的性能很差，那么有没有其他方案呢？
的确有，比如平均分页、禁用跨页查询、换用其他中间件等。不过任何方案都不是十全十美的，这些方案也存在一些难点，有的是需要业务折中，有的处理过程非常复杂。我们先来看第一个需要业务折中的平均分页方案
看到分页查询的第一个念头应该是：能不能在不同的表上平均分页查询数据，得到的结果合并在一起就是分页的结果
例如，查询中的语句是这样的
SELECT * FROM order_tab ORDER BY id LIMIT 4 OFFSET 2
因为本身有两张表，可以改成这样
SELECT * FROM order_tab_0 ORDER BY id LIMIT 2 OFFSET 1 SELECT * FROM order_tab_1 ORDER BY id LIMIT 2 OFFSET 1
在每一张表都查询从偏移量1开始的2条数据，那么合并在一起就可以认为从全局的偏移量2开始的4条数据。
图里我们能够看出来，按照道理全局的
LIMIT 4 OFFSET 2
拿到的应该是 3、4、5、6 四条数据。但是这里我们拿到的数据却是 2、4、5、9。这也就是这个方案的缺陷：它存在精度问题。也就是说，它返回的数据并不一定是全局最精确的数据
那么这个方案是不是就不能用了呢？并不是的，在一些对顺序、精度要求不严格的场景下，还是可以用的。例如浏览页面，你只需要返回足够多的数据行，但是这些数据具体来自哪些表，用户并不关心。
关键词就是平均分页
在一些可以接受分页结果不精确的场景下，可以考虑平均分页的做法。举个例子来说，如果查询的是
LIMIT 4 OFFSET 2
，并且命中了两张目标表，那么就可以考虑在每个表上都查询
LIMIT 2 OFFSET 1
。这些结果合并在一起就是
LIMIT 4 OFFSET 2
的一个近似答案。这种做法对于数据分布均匀的分库分表效果很好，偏差也不大。
这个方案还有一个进阶版本，就是根据数据分布来决定如何取数据。
更加通用的做法是根据数据分布来决定分页在不同的表上各自取多少条数据。比如说一张表上面有 70% 的数据，但是另一张表上只有 30% 的数据，那么在
LIMIT 10 OFFSET 100
的场景下，可以在 70% 的表里取
LIMIT 7 OFFSET 70
，在 30% 的表里取
LIMIT 3 OFFSET 30
。所以，也可以把前面平均分配的方案看作是各取 50% 的特例
那如何知道一张表上有70%的数据，另外一张表上有30%。
在开发的时候先用SQL在不同的表上执行一下，看看同样的WHERE条件下各自返回了多少数据，就可以推断出来了。
不过实际上，能够接受不精确的业务场景还是比较少的。所以我们还有一种业务折中的解决方案，它精确并且高效，也就是禁用跨页查询方案。
只允许用户从第0页开始，逐页往后翻，不允许跨页。
假如业务上分页查询是50条数据一页，那么发起的查询依次是：
SELECT * FROM order_tab ORDER BY id LIMIT 50 OFFSET 0 SELECT * FROM order_tab ORDER BY id LIMIT 50 OFFSET 50 SELECT * FROM order_tab ORDER BY id LIMIT 50 OFFSET 100
不断增长的只有偏移量，如何控制住这个偏移量呢？
答案是根据
ORDER BY
的部分来增加一个查询条件。上述例子里的
order by
是根据id升序排序的，只需要在where部分增加一个大于上次查询的最大id的条件就可以了。
max_id
是上一批次的最大id
SELECT * FROM order_tab WHERE `id` > max_id ORDER BY id LIMIT 50 OFFSET 0
即使
order by
里使用了多个列，规则也是一样的
总体来看，回答要分成两部分，第一部分介绍基本做法，关键词是拿到上一批次的极值。
目前比较好的分页做法是禁用跨页查询，然后在每一次查询条件里加上上依次查询的极值，也就是最大值或者最小值。比如说第一次查询的时候
ORDER BY ID LIMIT 10 OFFSET 0
，那么下一页就可以改为
WHERE id > max_id ORDER BY ID LIMIT 10 OFFSET 0
。在现在的手机 App 里这个策略是非常好用的，因为手机 App 都是下拉刷新，天然就不存在跨页的问题。
第一部分提到了极值，面试官可能问你什么时候用最大值，什么时候用最小值，可以这样说：
至于用最大值还是最小值，取决于order by。总的原则就是升序用最大值，降序用最小值。如果order by里面包含了多个列，那么针对每一个列是升序还是降序，来确定使用最大值还是最小值。
这种方案并没有彻底解决分库分表查询中的分页问题，但是控制了偏移量，极大的减少了网络通信的消耗和磁盘扫描的消耗。
一种思路是使用NoSQL之类的来存储数据，比如使用Elasticsearch、ClickHouse；另一种思路是使用分布式关系型数据库，相当于把分页的难题抛给了数据库
先尝试获取某个数据的全局偏移量，再根据这个偏移量来计算剩下数据的偏移量。这里用一个例子来阐述它的基本原理，再抽象出一般步骤。
假设我们的查询是
SELECT * FROM order_tab ORDER BY id LIMIT 4 OFFSET 4
数据分布如图所示：
全局的
LIMIT 4 OFFSET 4
是 5、6、7、8 四条数据
把SQL语句改写成这样：
SELECT * FROM order_tab_0 ORDER BY id LIMIT 4 OFFSET 2 SELECT * FROM order_tab_1 ORDER BY id LIMIT 4 OFFSET 2
我们只是把OFFSET平均分配了，但是LIMIT没变
第一次查询到的数据是这样
order_tab_0
拿到了4、6、10、12，而
order_tab_1
拿到了 7、8、9、11
