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屋！