Redis:当插入的元素在开头或结尾时，ZADD 是否比 O(logN) 更好? [英] Redis: Is ZADD better than O(logN) when the inserted element is at the beginning or end?

问题描述

ZADD 的 redis 文档 声明操作是 O(log N).

The redis documentation for ZADD states the operation is O(log N).

但是，当插入的元素位于排序顺序的开头或结尾时，有人知道 ZADD 是否比 O(log N) 更好?

However, does anyone know if ZADD is better than O(log N) when the inserted element is at the beginning or end of the sort order?

例如对于某些实现，这可能是 O(1).

E.g. for certain implementations this could be O(1).

具体来说，redis 教程 指出:

Specifically, the redis tutorial states that:

排序集是通过双端口数据结构实现的，其中包含一个跳过列表和一个哈希表，所以每次我们添加一个元素Redis 执行 O(log(N)) 操作.

Sorted sets are implemented via a dual-ported data structure containing both a skip list and an hash table, so every time we add an element Redis performs an O(log(N)) operation.

修改跳过列表以支持 O(k) 开头和结尾插入似乎是合理的，其中 k 是跳过列表的最大级别.

It seems plausible to modify a skip list to support O(k) insert at beginning and end, where k is the max level of the skip list.

推荐答案

我在 Redis 网站上交叉发布了这个问题，Pieter Noordhuis 在那里提供了一个答案，我在这里交叉发布:

I had cross-posted this question on the Redis website, and Pieter Noordhuis provided an answer there, which I am cross-posting here:

没错.排序集依赖于 RNG 来确定每个节点的级别数(它是一种概率数据结构).在跳过列表的开头插入/删除元素可能是 O(1)，而理论上最坏情况的性能是 O(N)(每个节点具有相同的级别).然而，当您考虑节点之间的级别分布时，分摊时间复杂度为 O(log N).

That is correct. The sorted set relies on an RNG to determine the number of levels per node (it's a probabilistic data structure). Inserting/deleting an element at the beginning of the skiplist can be O(1), while the theoretical worst case performance is O(N) (with every node having the same level). However, the amortized time complexity is O(log N) when you take in account the distribution of the levels among the nodes.

这篇关于Redis:当插入的元素在开头或结尾时，ZADD 是否比 O(logN) 更好?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！