Redis有序集合插入的时间复杂度

Question

3

Redis有序集合插入的时间复杂度为O(log n)，我认为这是由于在跳跃表中插入数据（为了维护集合顺序）所导致的。但是，如果我要插入的数据始终具有递增顺序的分数，插入时间复杂度仍然为O(log n)吗？我猜他们应该有一个简单的指向跳跃表末尾的指针，可以在O(1)时间内完成插入操作。

如果我错过了基本的东西，请谅解。

- Aravind

似乎您正在为您的用例建议一种优化，但是通用的跳表实现并不像那样工作。 - Guy Korland

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- LeoMurillo · Accepted Answer

跳表使用随机化级别创建。如果插入始终是按递增得分进行的，则它将遍历完整个顶层，然后遍历所有级别直到最高分界线，包括底层（就像下楼梯一样）。因此，是的，您的插入操作将始终是O(log N)。

您可以通过始终减少分数来欺骗它（乘以-1），这样您将只遍历最低分边缘上的所有级别。最多有64个级别（ZSKIPLIST_MAXLEVEL = 64），因此在您的情况下，您将获得O(1)的插入时间（常数时间）。

查看Redis Streams，它强制执行始终递增的id。您不能修改元素，但是可以存储引用到存储可修改部分的密钥。很可能它更适合您。它在内部使用基数树。