版权说明

未经作者允许，一律不得私自转载，否则将追究责任。

技术背景

1. 随着业务数据量的增大，传统的关系型数据库（如mysql）的单表处理效率达到瓶颈。但是由于业务需要，此类数据仍需存储在关系型数据库中。为了提高效率，可以把数据按一定规则分类，分别存入n张表中。这n张表按一定规则分类，分别由m个数据库管理。如下图所示：

   
   分库分表架构图
2. 传统单表的分页查询功能，需前后端配合实现。当需要查询某一页时，前端传给后端两个参数①页码 ②分页大小；后端接收这两个参数，并通过公式：
   起始行号 = （页码-1）*分页大小
   计算出起始行号，然后依托于LIMIT关键字，其所需参数为①起始行号 ②分页大小，到数据库中进行分页查询。单次查询后即返回结果集，并同时返回一个参数——所有符合查询条件的数据的数量，该回参用于前端显示数据总量及页码的计算。
3. 基于上述分库分表方案，由于把一张表拆分成了n张表，并且n张表分布在不同的m个数据库中，那么由此引发出了一个问题：传统的分页查询已经不再适用。由于分库分表，可能存在某一页的数据被存储在多张表中的情况，仅仅靠前端传来的两个参数无法进行传统的分页查询。

核心功能

1. 在不变动前端的前提下，通过设计算法，动态计算LIMIT关键字所需的两个参数①起始行号 ②分页大小，使得关系型数据库分库分表情况下，可以像单表一样进行分页查询。
2. 由于两个参数是动态计算的，当查询到了足够的数据（分页大小）之后，便返回结果。减少sql查询操作，提高效率。

算法描述

1. 从第一张分表开始循环，直到满足结果或循环完最后一张分表
2. 查询当前分表i，得到结果集resTemp
3. 如果resTemp有数据，则把resTemp加入返回结果resList
   3.1 如果resList满足分页大小，则退出循环
   3.2 如果resList不满足分页大小，则下次查询起始行号startTemp=0（从表头0开始），且下次查询的分页大小pagesizeTemp -= resTemp的大小
4. 如果resTemp无数据，则startTemp -= count(当前表数据量);

时间复杂度

假设分表数为n，则在最坏情况下，算法需要执行n次循环，每次循环执行一次select和count操作。故此算法的时间复杂度为O(n)。

举例说明

如图1所示，假设我们把mysql单表分成了3张分表，并且取名为表001，表002，表003，在这三张表中，分别存储了一些数据，我们把这些数据进行编号，一共十条，其中表001存储了7条，表002存储了2条，表003存储了1条。

图1. 单表分成了3张分表

算法的核心思路为：无论分了多少张表，都把它们看作是一张逻辑总表，这张表由所有分表首尾相连。如下图2所示：

图2. 逻辑总表
现在假设前端用户需要分页查询，从第1页开始查，每一页显示3条数据，直到查询完所有数据。那么转换为SQL就如图3所示：
图3. 逻辑总表的分页查询

分页查询依托于LIMIT关键字，其所需参数为①起始行号 ②分页大小。基于逻辑总表的分页查询，我们可以得到如下对应关系：

Sql语句	页码	涉及的表	查询的数据
LIMIT（0,3）	1	表001	1,2,3
LIMIT（3,3）	2	表001	4,5,6
LIMIT（6,3）	3	表001，表002	7，……，8,9
LIMIT（9,3）	4	表001，表002，表003	……，10

下面我们对于四条sql语句逐一分析：
LIMIT（0,3）：
表001作为起始表，对其执行LIMIT（0,3）可返回1,2,3这3条数据，满足分页大小，即可返回查询结果：1,2,3。
LIMIT（3,3）：
表001作为起始表，对其执行LIMIT（3,3）可返回4,5,6这3条数据，满足分页大小，即可返回查询结果：4,5,6。
至此，我们的查询只涉及表001。上文提到，由于分库分表，可能存在某一页的数据被存储在多张表中的情况，下面我们来看这种情况。
*LIMIT（6,3）：
表001作为起始表，对其执行LIMIT（6,3）可返回7这1条数据，还需2条；由于对表001的查询有满足的数据，所以对表002执行LIMIT（0,2）。为什么是LIMIT（0,2）？“0”是因为对表001的查询有满足的数据，所以对表002只需从第一条开始查询即可。“2”是因为此次查询还需要2条数据即可返回，我们把这种规则称为 规则1。表002执行完LIMIT（0,2）可返回8，9这2条数据。至此，满足分页大小，即可返回查询结果：7,8,9。
*LIMIT（9,3）：
表001作为起始表，对其执行LIMIT（9,3）无数据返回；由于对表001的查询无数据返回，所以对表002执行LIMIT（2,3）。为什么对表002执行LIMIT（2,3）？“2”是因为对表001的查询无数据返回，所以对表002的起始位置计算公式为：9-count(表001) = 2，
其中count(表001)是对表001的数据进行count计数操作。“3”是因为还需要3条数据即可返回，我们把这种规则称为 规则2。表002执行LIMIT（2,3）后仍无数据返回（注：mysql行号下标从0开始计数）。那么同理，根据 规则2，继续对表003执行LIMIT（0,3）可返回10这1条数据。若还有表004，则仍可根据规则1计算下去。但是由于已经遍历完了全部3张分表，此次查询返回结果：10。

根据算法，我们进一步抽象出如下逻辑：
变量说明：
resTemp——当前分表查询结果集
startTemp——下次查询的起始行号；
pagesizeTemp——下次查询的分页大小
resList——总的返回结果

伪代码逻辑：

for 循环所有的分表：
    查询当前的分表得到结果集resTemp;
    if resTemp有数据:
        then
        把resTemp加入返回结果resList;
        if resList满足分页大小:
            then break;
        else resList不满足分页大小:
            startTemp= 0;
            pagesizeTemp -= resTemp.size();
        end if
    else resTemp没有数据:
        startTemp -= count(当前表数据);
    end if
end for

注：由于数据量在实际情况当中是不断变化的，必须保证startTemp>=0 && pagesizeTemp>0。
所以for循环继续下一次查询需满足的条件有：

1. 尚未循环完最后一张分表
2. startTemp>=0
3. pagesizeTemp>0
4. 已查询到的数据量尚未满足分页大小

Java实现

接口

/**
 * 分库分表下的分页查询参数接口
 */
public interface MultiTableQuery {
    /**
     * 需要实现 单表的分页查询 功能
     * @param shard 表号
     * @param start 起始行号
     * @param pageSize 分页大小
     * @param queryParam where查询条件
     * @return 单表查询数据集
     */
    List<Map<String, Object>> queryByPageAndShard(int shard,int start, int pageSize,Map<String,Object> queryParam);

    /**
     * 需实现 单表count 功能
     * @param shard 表号
     * @param queryParam where查询条件
     * @return 单表中数据量
     */
    int countByShard(int shard,Map<String,Object> queryParam);

    /**
     * 需返回 分表总数
     * @return 分表的总数，即共有多少张表
     */
    int getShardNum();
}

工具类

/**
 * 分库分表工具类
 */
public class MultiTableUtils {

    /**
     * 分库分表下的分页查询
     * @param m 需要实现MultiTableQuery接口
     * @param start 起始行号
     * @param pageSize 分页大小
     * @param queryParam where查询条件
     * @return 查询数据集
     */
    public static List<Map<String, Object>> queryAllByPage(MultiTableQuery m,int start,int pageSize,Map<String,Object> queryParam) {

        int startTemp = start;
        int pageSizeTemp = pageSize;
        List<Map<String, Object>> resPendingList = new ArrayList<>();
        for (int i = 0; (i < m.getShardNum()) && (startTemp>=0) && (pageSizeTemp>0); i++) {
            List<Map<String, Object>> tempList = m.queryByPageAndShard(i,startTemp, pageSizeTemp,queryParam);
            if (CollectionUtils.isEmpty(tempList) ) {
                //如果此次分页查询没有数据，且不是从表头开始查
                if (startTemp > 0) {
                    int num = m.countByShard(i,queryParam);
                    //计算下一次查询的起始位置
                    startTemp = num > 0?startTemp-num:startTemp;
                }
            } else {
                //如果此次分页查询有数据，且还没有达到分页总数
                if (resPendingList.size() + tempList.size() < pageSize) {
                    //计算下一次查询的   剩余分页的数量
                    pageSizeTemp -= tempList.size();
                    //因为此次分页区间有数据，那下一次查询直接从表头查询即可
                    startTemp = 0;
                    resPendingList.addAll(tempList);
                } else {
                    resPendingList.addAll(tempList);
                    break;
                }
            }
        }
        return resPendingList;
    }
}

用法：

在service层实现MultiTableQuery 接口，然后直接使用工具类传入该service实例即可。其他参数注释都有说明。