Redis:当插入的元素在开头或结尾时，ZADD 是否优于 O(logN)？

Question

redis documentation对于 ZADD 状态，操作是 O(log N)。

但是，有谁知道当插入的元素位于排序顺序的开头或结尾时，ZADD 是否优于 O(log N)？

例如对于某些实现，这可能是 O(1)。

具体来说，redis tutorial指出:

Sorted sets are implemented via a dual-ported data structure containing both a skip list and an hash table, so every time we add an element Redis performs an O(log(N)) operation.

修改跳跃列表以支持在开头和结尾插入 O(k) 似乎是合理的，其中 k 是跳跃列表的最大级别。

Answer 1

我在 Redis 网站上交叉发布了这个问题，Pieter Noordhuis 在那里提供了一个答案，我在这里交叉发布:

---

没错。排序集依赖于 RNG 来确定每个节点的级别数(这是一种概率数据结构)。在 skiplist 的开头插入/删除一个元素可以是 O(1)，而理论上最坏情况下的性能是 O(N)(每个节点都具有相同的级别)。但是，当您考虑节点之间级别的分布时，摊销时间复杂度为 O(log N)。