分页器是应用程序中一个非常常见的功能，本文对比了PC和APP时代下，对分页器的不同要求，从而找出一种适合当下需求的优化方案。
传统SQL分页
SQL在设计的时候就考虑了分页器这种场景，那就是LIMIT OFFSET语句，下面例子就是每页十个，分别查询1、2、3页的场景。
SELECT * FROM users ORDER BY id LIMIT 10 OFFSET 0; SELECT * FROM users ORDER BY id LIMIT 10 OFFSET 10; SELECT * FROM users ORDER BY id LIMIT 10 OFFSET 20; ...
我们很容易把他公式化，第N页的条件就是 LIMIT PageSize OFFSET (N-PageBase)*PageSize。这里两个变量PageSize好理解，表示分页长度，PageBase表示起始页，正常情况都是1，如果有分表的场景，比如前100页在一个表，100页之后在另一个表，那就在查100页之后的时候设置PageBase为100即可无缝衔接而不需要其他处理。
LIMIT OFFSET的分页方式在PC时代大行其道，好处一是分页的概念也符合纸张时代的习惯，二是实现简单，而且可以支持直达，比如直接转到第100页都很容易。但是他也有一个弊端，那就是对于一张超大表来说，分页越往后查询时间会越长。因为OFFSET永远都是从0开始数的，比如你执行LIMIT 10 OFFSET 100000数据库会根据查询条件筛出数据，然后从第0个开始，找到第100000个，然后拿出10个，这部分基本无法优化，因为索引基本只能优化到WHERE和ORDER部分，OFFSET基本靠遍历。所以OFFSET等于0是最快的，数据库直接返回开头的数据，OFFSET越大，数据库需要遍历的数据也越多，意味着无谓的开销越大。
一种冷门的优化方式
同样基于主键索引，SELECT只查询主键或索引中的字段效率会高：
SELECT * FROM users ORDER BY id LIMIT 1 OFFSET 500000; # 1197ms SELECT id FROM users ORDER BY id LIMIT 1 OFFSET 500000; # 307ms
以上两个查询是基于我的一个数据库测得，相差3倍，原理与Inno DB的索引存储有关。如何利用这个特性来提升速度就不再赘述了。但其实3倍的提升，对数据库来讲只能说还行吧。下面重点分析一种百倍以上的优化方式。
让OFFSET也用上“索引”
这里的索引打引号，其实OFFSET无法使用索引，但是我们可以利用索引避免OFFSET，下面咱们用WHERE条件结合索引来实现前面例子的效果。可以用下面方式：
SELECT * FROM users WHERE id>0 ORDER BY id LIMIT 10 OFFSET 0; SELECT * FROM users WHERE id>10 ORDER BY id LIMIT 10 OFFSET 0; SELECT * FROM users WHERE id>20 ORDER BY id LIMIT 10 OFFSET 0; ... SELECT * FROM users WHERE id>10000 ORDER BY id LIMIT 10 OFFSET 0;
因为id这个字段是有主键索引的，因此在WHERE条件里面可以很快的定位，这个时间复杂度不会大于O(logN)，而分页条件这里，全部避免了OFFSET，直接拿出符合条件的前十个。
但是这个例子显然太特别了，必须要按照id排序，同时结果中的id必须连续才可以准确实现传统的分页器效果。假设WHERE条件里面加一个只查女生的条件，我要直达第十页，id应该从哪里开始？的确，分页直达的实现是这种方案的最大缺陷，但是在APP时代这个问题就显得不那么重要，因为你很少会看到哪个APP做了跳转到第十页这种功能，APP永远是feed流，所有的分页都必须是连续的1、2、3、4、5....。所以APP的分页参数就不必用page了，这个例子中，我们只需要把上一页的结尾id带过来即可，当然这里依然有一个必要条件就是结果必须按照id排序，而且id必须唯一才可以。
上面例子中id是主键，肯定具有唯一性。我们看下面这个表，尝试用不唯一的字段score倒序排序。这时候问题来了，如果每页两个，那么第二页的score条件应该怎么设置呢，如果score<2那么可能会漏掉一个人，如果score<=2就会有一个重复。
id | name | score
1 | alice | 2
2 | bob | 1
3 | coder | 2
4 | david | 3
因此，用这种分页方式，必须要保证排序字段的唯一。那么这个例子是不是就无法优化呢，其实也是可以的。
处理不唯一字段和多维排序
那么我们想想用传统的LIMIT OFFSET语句怎么处理score排序的场景，其实用这种方式要想确保不出问题也得引入多维排序，否则某些数据库对相同值的排序结果可能每次也不尽相同。
SELECT * FROM users ORDER BY score DESC, id DESC LIMIT 2 OFFSET 2;
我们继续用上面的思想对这个查询优化，基于score, id两个排序字段，构造一个新的排序字段score_sort。他的值由score和id生成。
id | name | score | score_sort
1 | alice | 2 | 2001
2 | bob | 1 | 1002
3 | coder | 2 | 2003
4 | david | 3 | 3004这样我就可以用上面的方式对分页做优化了
SELECT * FROM users WHERE score_sort<MAX_INT ORDER BY score_sort DESC LIMIT 2 OFFSET 0; SELECT * FROM users WHERE score_sort<2003 ORDER BY score_sort DESC LIMIT 2 OFFSET 0;
这里我只给id留了3位数，id作为自增字段不可能只有3位的。因为我做了一个预估，同一个score的用户最多的情况也远小于1000，因此我们只需要把id对1000取余，只要能避免重复即可，因为我们主需求是对score排序，id的引入基本是为了避免排序出错。如果数据库不支持bigint，留给id的位置越少那就留给score的越多，我们要优先满足第一排序的字段。在数据库允许的情况下，我们尽量保证每个参与排序的字段都完整加入。
当然，避免溢出更保险的做法是把score_sort转成字符串，字符串的排序请自行了解字典序。score_sort用字符串的话要求你必须对第一排序字段也要预估范围，事先固定好字符串的长度才行，否则可能出现"9">"10"的情况。下面例子我预估score和id都在7位整型以内。
id | name | score | score_sort
1 | alice | 2 | "00000020000001"
2 | bob | 1 | "00000010000002"
3 | coder | 2 | "00000020000003"
4 | david | 3 | "00000030000004"预估越大，字符串越长，带来的存储空间浪费和性能损失也越多，越小则越容易溢出，所以这个预估务必准确平衡。另外，还可以使用进制转换，把10进制转成62进制[0-9A-Za-z]，这样可以很大的节省字符串长度，优化存储和查询效率。
其实，现在最新的数据库大都可以支持big int了，换算成十进制可以有20位以上，因此大部分场景都应该尽量避免用字符串。其实上面例子使用十进制的拼接只是为了方便解说，但是对计算机来说并不友好，我们完全可以用二进制，令score_sort = (score << 32) + id，就可以实现二进制的拼接，计算更快，bit利用率更高。
NoSQL分页
NoSQL为了性能，没有SQL那么多的查询特性，但是基本上都支持range或scan的查询方式，其实也就是上面那种设置值大于或小于某个值的形式。有兴趣的朋友可以查看我的另一篇文章《理解redis SCAN》。
没有银弹
没有银弹就是说没有一种方式可以解决所有问题，我们在制定编程方案的时候，也要认识到这个问题，下面总结一下LIMIT语句和RANGE两种分页的优缺点：
LIMIT OFFSET: 方便，可以任意指定排序字段和排序方式，任意指定跳转的页数。缺点是偏移量offset的处理需要耗费较多的计算资源，传统的分页器通常还会有一个COUNT查询，获取总的记录条数和页数，这也是容易产生瓶颈的地方。
RANGE：快速，通常会基于索引快速定位数据，也可以不必计算总结果数，因为分页到结果数小于PageSize的时候就是分页结束的时候。缺点灵活度不够，不能任意排序，必须专门针对排序场景，对字段做组合唯一处理；不支持任意页数的跳转，必须基于前一页的分页结果递推下一页。
其实这个规律也是计算机世界的普遍规律，就像空间时间的互换规律一样，要满足灵活性，就不能满足高性能，满足高性能就一定会损失灵活性。
值得一提的是在APP的影响之下，许多面向PC的分页方式也逐步换成feed流的形式而去掉了分页直达这种功能。