最高效的B+Tree有序数据上下分页方法

C 2月前 802

众所周知在B+树查询时指定范围,查询速度非常快,而查询有offset时需要扫描并跳过该部分,如果offset巨大则效率低。

之前我们新系统的列表页,因为存在顶贴等功能打乱排序,因此采用使用传统的翻页模式,防止在阅读过程中帖子乱序。

我们在巨大分页的实现中,使用了一个变种B+树,可以实现链表的Key查询,但需要把所有ID写入内存,比较占用空间。

针对帖子回复数据,因为是是按时间排序,不会被轻易打乱,因此可以采用不同的分页方式,传入游标实现范围查询。

数据查询非常简单,就是传统的 正序 / 倒序 ,查找某个游标的 后 / 前 N条数据,比较困难的是如何实现上下翻页。

这里为了不查询额外数据行,使用了一个取巧的方式,以ASC排序为例:

因为[下页第一条数据]肯定大于[本页最后一条数据],因此游标设为[本页最后一条数据]+1。

上页同理,反过来查询小于[本页第一条数据],再把数据翻转即可。

这样无需把有序的回复数据ID做缓存,很好地节省了内存。

最新回复 (1)
  • C 2月前
    2

    image.webp

    做了一个细节优化,在主题表存储回复的数量(按过滤器)。

    计算出最后一页的数量,这样跳转到尾页再往前翻,也可以做到每页数量对齐。