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

Question

Redis 排序集插入的时间复杂度为 O(log n)，我假设这是由于在跳过列表中插入数据（为了维护集顺序）。但是如果我要插入的数据总是以递增的顺序得分，它仍然是 O(log N) 吗？我猜他们应该有一个指向跳过列表尾部的简单指针，它可以在 O(1) 中进行插入。

对不起，如果我在这里错过了一个基本的东西。

标签： redisredis-clusterskip-lists

Answer 1

跳过列表使用随机级别创建。如果您的插入总是分数增加，它将遍历完整的顶层，然后一直遍历所有级别到最高分边界，包括底层（如从楼梯上掉下来）。所以，是的，你的插入总是 O(log N)。

您可以通过使用始终递减的分数（乘以 -1）来欺骗这一点，这样您将只遍历最低分数边缘的所有级别。有 64 个级别最高（ZSKIPLIST_MAXLEVEL = 64），因此在您的情况下您会得到 O(1) 插入（恒定时间）。

看看 Redis Streams，它总是强制增加 id。您不能修改元素，但可以存储对存储元素可修改部分的键的引用。有可能它更适合你。它在内部使用基数树。