2

On REDIS documentation, it states that insert and update operations on sorted sets are O(log(n)).

On this question they specify more details about the underlying data structure, the skip list.

However there are a few special cases that depend on the REDIS implementation with which I'm not familiar.

  • adding at the head or tail of the sorted set will probably not be a O(log(n)) operation, but O(1), right? this question seems to agree with reservations.
  • updating the score of a member even if the ordering doesn't change is still O(log(n)) either because you take the element out and insert it again with the slightly different score, or because you have to check that the ordering doesn't change and so the difference is only in constant operations between insert or update score. right? I really hope I'm wrong in this case.

Any insights will be most welcome.

Community
  • 1
  • 1
Daren
  • 3,337
  • 4
  • 21
  • 35

2 Answers2

2

Note: skip lists will be used once the list grows above a certain size (max_ziplist_entries), below that size a zip list is used.

Re. 1st question - I believe that it would still be O(log(n)) since a skip list is a type of a binary tree so there's no assurance where the head/tail nodes are

Re. 2nd question - according to the source, changing the score is implemented with a removing and readding the member: https://github.com/antirez/redis/blob/209f266cc534471daa03501b2802f08e4fca4fe6/src/t_zset.c#L1233 & https://github.com/antirez/redis/blob/209f266cc534471daa03501b2802f08e4fca4fe6/src/t_zset.c#L1272

Itamar Haber
  • 47,336
  • 7
  • 91
  • 117
  • from the skip-list entry in wikipedia, it seemed inserting in head was O(1) but not in tail. Thanks for the second question though. – Daren Nov 06 '14 at 14:17
1

  1. In Skip List, when you insert a new element in head or tail, you still need to update O(log n) levels. The previous head or tail can have O(log n) levels and each may have pointers which need to be updated.

  2. Already answered by @itamar-haber

hutabalian
  • 3,254
  • 2
  • 16
  • 13