## 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 ?

- search the
`min`

element. O(lg(n)) complexity (with`n=|set|`

) - 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 !