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

Question

Redis zrank .

Returns the rank of member in the sorted set stored at key, with the scores ordered from low to high. The rank (or index) is 0-based, which means that the member with the lowest score has rank 0.

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

更新

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

一个。当zset由ziplist实现时

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

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

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

typedef struct zset {

    zskiplist *zsl;

    dict *dict;

} zset;

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

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

所以，zrank 是这样的:

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

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

Answer 1

成员键很可能存储在某种搜索树中(增加了分支大小，如 this )。

所以元素搜索和排名计算都在 O(logN) 中执行。上面的链接显示了这些操作的示例实现。