1

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

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

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

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

任何见解都将受到欢迎。

4

2 回答 2

2

注意:一旦列表增长到一定大小(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

于 2014-11-06T13:38:31.763 回答
1
  1. 在 Skip List 中,当您在 head 或 tail 中插入新元素时,您仍然需要更新O(log n)级别。前一个头部或尾部可以有O(log n)级别,每个级别都可能有需要更新的指针。

  2. @itamar-haber 已经回答了

于 2019-04-16T09:43:38.783 回答