最高效的B+Tree有序数据上下分页方法 众所周 - Assbbs

最高效的B+Tree有序数据上下分页方法 众所周知在B+树查询时指定范围，查询速度非常快，而查询有offset时需要扫描并跳过该部分，如果offset巨大则效率低。 之前我们新系统的列表页，因为存在顶贴等功能打乱排序，因此采用使用传统的翻页模式，防止在阅读过程中帖子乱序。 我们在巨大分页的实现中，使用了一个变种B+树，可以实现链表的Key查询，但需要把所有I…

最高效的B+Tree有序数据上下分页方法 众所周知在B+树查询时指定范围，查询速度非常快，而查询有offset时需要扫描并跳过该部分，如果offset巨大则效率低。 之前我们新系统的列表页，因为存在顶贴等功能打乱排序，因此采用使用传统的翻页模式，防止在阅读过程中帖子乱序。 我们在巨大分页的实现中，使用了一个变种B+树，可以实现链表的Key查询，但需要把所有ID写入内存，比较占用空间。 针对帖子回复数据，因为是是按时间排序，不会被轻易打乱，因此可以采用不同的分页方式，传入游标实现范围查询。 数据查询非常简单，就是传统的 正序 / 倒序 ，查找某个游标的 后 / 前 N条数据，比较困难的是如何实现上下翻页。 这里为了不查询额外数据行，使用了一个取巧的方式，以ASC排序为例： 因为 下页第一条数据 肯定大于 本页最后一条数据 ，因此游标设为 本页最后一条数据 +1。 上页同理，反过来查询小于 本页第一条数据 ，再把数据翻转即可。 这样无需把有序的回复数据ID做缓存，很好地节省了内存。