为什么redis zrank的复杂性是O（log（N））

Question

Redis zrank。

返回存储在key处的排序集中成员的排名，分数从低到高排序。排名（或指数）是基于0的，这意味着得分最低的成员排名为0。

为什么复杂度是O（log（N））？成员按分数排序，但zank按成员查询。

我找到了一些可能是答案的东西。

A.zset由ziplist实现时

1. 大小小于128
2. 每个成员的大小小于64字节

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

B.当zset由skiplist实现时，zset的实现是：

typedef struct zset {

    zskiplist *zsl;

    dict *dict;

} zset;

zset同时保存一个dict和一个skiplist。

1. dict保持成员到分数的映射
2. zsl是按分数排序的对象列表。对象包含成员和分数

所以，zrank是这样的：

>

用O（1）时间求成员的分数。如果找不到，返回nil。

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

Answer 1

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

较小的集合是ziplists，它们的排序复杂度实际上是O（N）。然而，这被认为是O（1），因为ziplist阈值是恒定的。

当使用跳过列表编码时，排名是O（LogN），因为搜索的便利性——参考维基百科关于跳过列表的文章了解更多信息。

Answer 2

成员键很可能存储在某种搜索树中（通过这样的分支大小进行扩展）。

因此，元素搜索和秩计算都是在O（logN）中进行的。上面的链接显示了这些操作的示例实现。