当值的分数大于目标排序集中的最高分数时 zadd 的时间复杂度 [英] Time complexity of zadd when value has score greater than highest score present in the targeted sorted set

问题描述

如果添加到排序集合(redis)的每个值都是得分最高的一个，那么每个zaddO(log(N))>?

If every value one adds to a sorted set (redis) is one with the highest score, will the time complexity be O(log(N)) for each zadd?

OR，对于这种边缘情况，redis 执行优化(例如，在 score 高于集合中最高的 score 的情况下，只需添加值在最高点)?

OR, for such edge cases, redis performs optimizations (e.g. an exception that in such cases where score is higher than the highest score in the set, simply add the value at the highest spot)?

实际上，我问是因为我在我的应用程序中保留了一个全局排序集，其中值是 zAdded 以自纪元以​​来的时间作为分数.我想知道这是否仍然是 O(log(N))，还是会更快?

Practically, I ask because I keep a global sorted set in my app where values are zadded with time since epoch as the score. And I'm wondering whether this will still be O(log(N)), or would it be faster?

推荐答案

一旦 Sorted Set 增长超过 zset-max-ziplist-* 配置指令设置的阈值，它被编码为跳过列表.由于需要维护跳过列表的上层，因此优化这种边缘情况的插入似乎是不可能的.对源代码的粗略审查表明，正如预期的那样，这并没有以任何特殊方式处理.

Once a Sorted Set has grown over the thresholds set by the zset-max-ziplist-* configuration directives, it is encoded as a skip list. Optimizing insertion for this edge case seems impossible due to the need to maintain the skip list's upper levels. A cursory review of the source code shows that, as expected, this isn't handled in any special way.

这篇关于当值的分数大于目标排序集中的最高分数时 zadd 的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！