如何高效聚合Redis分片有序集合？分页查询效率优化问询

问题背景 #

基于Redis ZSET构建的分片排行榜，按key哈希分片实现扩容，前N条查询可通过聚合各分片前N条实现，但带skip的深分页查询效率极低。

问题1：是否存在对数时间复杂度的查询方案？ #

有两种核心思路可实现对数时间的深分页查询：

1. 按Score范围分片（替代哈希分片） #

放弃按key哈希分片，改为将Score划分为固定/动态区间，每个分片负责一个区间的ZSET数据：

• 查询时，先通过全局元数据估算出skip到skip+limit对应的Score范围，直接从对应分片拉取数据，仅需对少量分片的结果做聚合排序，时间复杂度为O(log k + log m)（k为分片数，m为单分片元素数）。
• 缺点：若Score分布不均会导致热点分片，需定期调整区间平衡负载。

2. 全局分层索引分片（保留哈希分片+新增元数据） #

在现有哈希分片基础上，新增一层全局索引ZSET和分片元数据：

• 全局索引ZSET：每个成员为分片ID，Score设为该分片的最小/最大Score，同时每个分片维护自身的元素总数（用Redis计数器或ZCARD实时获取）。
• 查询时：
  1. 遍历全局索引ZSET，累加各分片的元素总数，定位到skip对应的分片范围；
  2. 在目标分片内用ZREVRANGEBYRANK直接获取对应偏移量的元素；
  3. 若跨分片则拉取相邻分片的部分数据聚合。
• 整体时间复杂度为O(log k + log m)，属于对数时间范畴。

问题2：能否通过插入阶段维护元数据优化查询，且插入时间控制在O(log n)？ #

可以，以下方案满足插入时间从O(1)提升至O(log n)的要求：

1. 范围分片的元数据维护 #

插入时，通过二分查找确定元素Score所属的分片区间（时间O(log k)），再将元素插入对应分片的ZSET（O(log m)），整体插入时间O(log k + log m) = O(log n)（n为全局总元素数）。

2. 全局分层索引的元数据维护 #

插入时：

• 将元素插入对应哈希分片的ZSET（O(log m)）；
• 更新该分片的元素总数计数器（O(1)）；
• 若该元素的Score是分片的新极值（最大/最小），则更新全局索引ZSET中对应分片的Score（O(log k)）。
• 整体插入时间O(log m + log k) = O(log n)，符合要求。

3. 分段全局索引维护 #

每隔固定数量（如1000条）的元素，在全局ZSET中记录该元素的Score、所在分片及全局排名：

• 插入时，若元素的全局排名落在分段点上，就将其加入全局索引ZSET（O(log (n/M))，M为分段间隔）；
• 查询时，通过全局索引快速定位到skip附近的分段点，再从对应分片拉取数据，大幅减少需要聚合的分片数量。
• 插入时间为O(log m + log (n/M)) = O(log n)。

内容的提问来源于stack exchange，提问作者underflow