高效的 `SkipList::range().count()`
作者: FiV0创建于 2026年4月16日更新于 2026年4月20日
标签featurecrossbeam-skiplist
SkipList 实现被用于 SlateDB 内存表中。为了基于范围进行估算,最好能知道范围的大小(而不需要逐个迭代)。这与平均键大小一起,可以对范围进行近似大小估算。我主要想做的算法也描述在了这里: https://GitHub.com/facebook/rocksdb/wiki/Approximate-Size#skiplist-memtable-size-estimation。我不知道如何最好地展示我想要的信息(你可能更了解)。也可能是 SkipList::lower_bound 和 SkipList::upper_bound 返回的 Entry 中的信息。如果对这个功能有兴趣,我可以写一些更加深思熟虑的内容。如果觉得太过小众,也可以关闭。
内容来源: crossbeam-rs/crossbeam