redis - 使用 REDIS 排序集，某些特殊操作的时间复杂度是多少？

Question

在 REDIS 文档中，它指出对排序集的插入和更新操作是 O(log(n))。

在这个问题上，他们指定了有关底层数据结构的更多细节，即跳过列表。

但是，有一些特殊情况取决于我不熟悉的 REDIS 实现。

在排序集的头部或尾部添加可能不是 O(log(n)) 操作，而是 O(1)，对吧？这个问题似乎同意保留意见。
即使排序没有改变，更新成员的分数仍然是 O(log(n)) 或者因为您取出元素并以稍微不同的分数再次插入它，或者因为您必须检查排序是否'不改变，因此差异仅在于插入或更新分数之间的持续操作。正确的？我真的希望我在这种情况下是错的。

任何见解都将受到欢迎。

score 2 · Accepted Answer

注意：一旦列表增长到一定大小（max_ziplist_entries）以上，将使用跳过列表，低于该大小使用压缩列表。

回覆。第一个问题 - 我相信它仍然是 O(log(n)) 因为跳过列表是一种二叉树，所以不能保证头/尾节点在哪里

回覆。第二个问题 - 根据消息来源，更改分数是通过删除和读取成员来实现的：https ://github.com/antirez/redis/blob/209f266cc534471daa03501b2802f08e4fca4fe6/src/t_zset.c#L1233 & https://github .com/antirez/redis/blob/209f266cc534471daa03501b2802f08e4fca4fe6/src/t_zset.c#L1272

score 1 · Accepted Answer

在 Skip List 中，当您在 head 或 tail 中插入新元素时，您仍然需要更新O(log n)级别。前一个头部或尾部可以有O(log n)级别，每个级别都可能有需要更新的指针。
@itamar-haber 已经回答了

2 回答 2