Redis ZSET Underlying Datastructure

2013-04-08 − Maxime Biais
1 minute read

Sorted Sets: ZSET

Redis ZSETs are a very good to store ordered data like leaderboards:

  • You need to get the current score for an userid (every SQL or NOSQL
    can do that efficiently)
  • You need to get the current rank for an userid
  • You need to get a list of pairs userid/score sorted by score

Datastructure

In the Redis documentation, we can read complexity is O(lg(n)) to ZADD / ZRANK / ZREM and O(1) for ZSCORE. How are they implemented ? O(lg(n)) you said… hmmm smells like a tree or binary search. ZSCORE (a kind of search) in constant time… hmmm smells like a hashtable. So how is it implemented ? a mix of hashtable and tree ? No, but that’s close, it’s a mix of hashtable and Skip List. Skip list are an alternative to balanced binary tree.

You should read the original Skip List paper.

From the redis documentation:

ZSETs are ordered sets using two data structures to hold the same elements in order to get O(log(N)) INSERT and REMOVE operations into a sorted data structure.

The elements are added to an hash table mapping Redis objects to scores. At the same time the elements are added to a skip list mapping scores to Redis objects (so objects are sorted by scores in this “view”).

So, how to perform a ZRANGEBYSCORE in linear time ?

  1. search the min element. O(lg(n)) complexity (with n=|set|)
  2. start from min and follow links to the next element until you reach max. O(m) complexity (with m elements returned)

Also, there is a modification from the original skip list implementation, level 1 list is doubly linked, so it gives you: ZREVRANGE, yeah !