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
In the Redis documentation, we can read complexity is O(lg(n)) to
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
minelement. O(lg(n)) complexity (with
- start from
minand 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 !