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

Question

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

抱歉，如果我错过了这里的基本内容。

Answer 1

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

你可以通过使用你的分数总是减少而不是(乘以 -1)来欺骗这个，这样你将只遍历最低分数边缘的所有级别。顶部有 64 个级别 (ZSKIPLIST_MAXLEVEL = 64)，因此您在您的情况下得到 O(1) 插入(恒定时间)。

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