分页算法优化实践

核算数据的查询和涉及大量数据处理的job，对于分页查询的性能非常敏感。

正好看到Tim Yang的这篇博客，提供了优化的思路: http://timyang.net/data/key-list-pagination-ii/

Tim是新浪博客的技术总监，他的博客基本都是干货，推荐大家关注。

他博客中提到的优化方法，我就不重复了。就以报表数据的查询举个栗子吧。

报表的数据模型大致如下：

KeyID CustomerID yyyyMM Amount
1 87871 201411 1000
.. … … …
1187 87872 201412 2000
.. … … …
2787 87873 201501 3000
.. … … …

KeyID是自增，但是数据有可能被作废，所以可能不连续

建立Count index，保存每月有多少条数据

ID yyyyMM count
1 201411 502
2 201412 587
3 201501 687

建立Offset index，保存每个偏移量offset对应的KeyID

ID offset KeyID
1 500 1187
2 1000 1600
3 1500 1878
4 2000 2878
… … …

查询的流程是这样的：

比如要查询201412月份的第一页数据，查询参数是:

1
2
3
4
5
{
 "yyyyMM": 201412,
 "page": 1,
 "pageSize": 20
}

那么根据"yyyyMM": 201412 这个条件可以从Count index看到201412的上一个月201411有501条记录，那么只要从offset:502这个位置开始查找就可以，然后根据502到Offset index 可以看到 offset:500 的位置对应的主键KeyID是1187。

那么最终我们的查询条件就是:

1
WHERE KeyID > 1187 LMIT 20 OFFSET 1

而一般的分页查询：

1
WHERE yyyyMM = '201412' LIMIT 20

yyyyMM列的区分度不大，建索引意义不大

所以优化效果明显

我们写了个查询功能，测了一下，具体代码见:
https://github.com/NoahShen/mycodefactory/tree/dev/secondindex

优化后，性能比原先提高了80%~100%，测试代码以及索引的生成、管理方式还有优化空间，所以查询性能还有提升的空间

除了这个报表的例子中使用，对于经常需要翻页查询，批量数据处理的场景都可以参考，比如结算的收入成本作业，商家账单页面的查询

PS: 使用这种优化方式的前提是数据的排序结构要和B+树类似