增强 B+ 树排名忽略与 RESP Inline 命令注入

部分 A: 排序集的渐近性能下降

Dragonfly 的 BPTree 是一个增强的秩统计 B+ 树: 每个内部节点都维护子树元素计数(GetChildTreeCount), 可在 $O(\log N)$ 时间内通过 FromRank() 进行排名查找。然而,在 SortedMap::GetRange 和 SortedMap::GetLexRange 中:

while (offset--) {
  if (!path.Prev())
    return arr;
}

跳过 offset 个元素时,代码不是在 $O(\log N)$ 时间内计算 target_rank = path.Rank() - offset,然后直接通过 FromRank(target_rank) 跳转,而是执行一个 $O(\text{offset})$ 的顺序性叶节点遍历。例如,ZREVRANGEBYSCORE key +inf -inf LIMIT 10000000 1 命令在单个线程调用中执行 10000000 次指针跳转,而不会进行上下文切换。