algorithm - 为什么redis zrank的复杂度是O(log(N))

Redis zrank。



为什么复杂度是O(log(N))？成员按分数排序，但zrank按成员查询。

更新资料

我找到了可能的答案。

A.当zset由ziplist实现时

大小小于128

每个成员的大小小于64个字节。

因此，ziplist的大小很小，所以这不是我讨论的问题。

B.当zset由skiplist实现时
zset的实现是:

typedef struct zset {

    zskiplist *zsl;

    dict *dict;

} zset;

zset同时保留一个字典和一个跳过列表。

dict保持成员到得分的映射。

zsl是按分数排序的对象的排序列表。该对象包含成员和得分。

因此，zrank是这样的:

使用O(1)时间来查找成员的分数。如果未找到，则返回nil。

用找到的分数在zsl中搜索，花费O(log(N))时间。

最佳答案

Redis对排序集使用两种编码之一:ziplists和skip list。

较小的集是ziplist，它们的排名复杂度实际上是O(N)。但是，由于ziplist阈值是恒定的，因此将其视为O(1)。

使用跳过列表编码时，排名为O(LogN)，因为搜索的复杂性-有关更多信息，请引用Wikipedia article about skiplists。