雷迪斯文档对于 ZADD 来说，操作是 O(logN).
然而，有谁知道 ZADD 是否比 O(logN) 当插入的元素位于排序顺序的开头或结尾时？
例如。对于某些实现，这可能是 O(1)。
具体来说，redistutorial指出：
排序集是通过双端口数据结构实现的，其中包含
既是跳跃列表又是哈希表，所以每次我们添加一个元素
Redis 执行 O(log(N）） 手术。
修改跳过列表以支持 O(k) 在开头和结尾插入，其中k是跳跃列表的最大级别。
我在 Redis 网站上交叉发布了这个问题，Pieter Noordhuis 在那里提供了答案，我将其交叉发布在这里：
那是对的。排序集依靠 RNG 来确定每个节点的级别数（它是一种概率数据结构）。在跳表开头插入/删除元素的复杂度可能是 O(1)，而理论上最坏情况的性能是 O(N)（每个节点都具有相同的级别）。但是，当考虑节点之间级别的分布时，摊余时间复杂度为 O(log N)。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
