ZADD的 redis文档指出该操作为 O(log N )。
但是，当插入的元素位于排序顺序的开头或结尾时，有谁知道 ZADD 是否比 O(log N ) 好？
例如，对于某些实现，这可能是 O(1)。
具体来说，redis教程指出：
排序集是通过包含跳过列表和哈希表的双端口数据结构实现的，因此每次添加元素时，Redis 都会执行 O(log( N )) 操作。
修改跳过列表以支持在开头和结尾插入O( k )似乎是合理的，其中k是跳过列表的最大级别。
问问题
1396 次
2 回答
3
我在 Redis 网站上交叉发布了这个问题，Pieter Noordhuis 在那里提供了一个答案，我在这里交叉发布：
那是对的。排序集依赖于 RNG 来确定每个节点的级别数（它是一种概率数据结构）。在跳过列表的开头插入/删除一个元素可能是 O(1)，而理论上最坏情况的性能是 O(N)（每个节点具有相同的级别）。但是，当您考虑节点之间的级别分布时，摊销时间复杂度为 O(log N)。
于 2011-08-22T16:42:45.363 回答
0
k和log( N )之间有关系吗？如果它们通过恒定因素相关，那么您实际上并没有改变任何东西。（我不知道这种关系是否存在，但考虑到关于该主题的维基百科页面显然在层构造中具有这种关系，它看起来非常合理。OTOH，该页面没有链接到证明，我不觉得就像现在手工推导一样，所以这只能是推测。）
此外，总体而言，算法总体为 O(log N ) 的事实并不能阻止特定特殊情况变得更好（例如，O(1)）。
于 2011-08-22T07:59:53.077 回答