4

The redis documentation for ZADD states the operation is 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?

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

Specifically, the redis tutorial states that:

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.

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.

Donal Fellows
  • 133,037
  • 18
  • 149
  • 215
Peter Skirko
  • 695
  • 7
  • 14

2 Answers2

3

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

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.

Peter Skirko
  • 695
  • 7
  • 14
0

Is there a relationship between k and log(N)? If they're related by a constant factor, you've not actually changed anything. (I don't know if that relationship exists, but it looks highly plausible given that the wikipedia page on the topic has apparently that relationship in the layer construction. OTOH, the page doesn't link to a proof and I don't feel like deriving it by hand right now, so this can only be conjecture.)

Also, in general the fact that the algorithm overall is O(log N) doesn't stop particular special cases from being better (e.g., O(1)).

Donal Fellows
  • 133,037
  • 18
  • 149
  • 215
  • I also found it interesting that skip lists can have problems with memory locality (according to http://resnet.uoregon.edu/~gurney_j/jmpc/skiplist.html). Goes to show that you should _always measure_, not guess. – Donal Fellows Aug 22 '11 at 08:01
  • a long time has passed since this, however I find the question really interesting, if i want to insert into redis an existing sorted set which is built sorted, it might be interesting to know in which way it is better to send commands: reverse, direct, as if I was building a binary tree...? – Daren Jul 08 '14 at 13:18