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 是跳跃列表的最大级别。
最佳答案
我在 Redis 网站上交叉发布了这个问题,Pieter Noordhuis 在那里提供了一个答案,我在这里交叉发布:
没错。排序集依赖于 RNG 来确定每个节点的级别数(这是一种概率数据结构)。在 skiplist 的开头插入/删除一个元素可以是 O(1),而理论上最坏情况下的性能是 O(N)(每个节点都具有相同的级别)。但是,当您考虑节点之间级别的分布时,摊销时间复杂度为 O(log N)。
关于Redis:当插入的元素在开头或结尾时,ZADD 是否优于 O(logN)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7140527/