Understanding Redis Sorted Sets and Their Skiplist Implementation

Redis sorted sets (zsets) are a composite data structure that combines a hash table (dictionary) with a skiplist to provide ordered storage of string elements associated with a score.

Unlike plain sets, each element in a sorted set has a numeric score, allowing the collection to be retrieved in order of the scores. This makes sorted sets ideal for ranking scenarios such as hot topics, leaderboards, or any use‑case that requires fast range queries by score.

Implementation Overview

The skiplist implementation in Redis is based on a classic skiplist data structure, offering O(log N) average time for search, insertion, and deletion. Redis extends the basic skiplist with additional fields:

Forward pointers (as in a normal skiplist)

Backward pointer for reverse traversal

Span field in each forward pointer to compute element rank efficiently

Key Data Structures (C)

#include
#include
#define ZSKIPLIST_MAXLEVEL 32
#define ZSKIPLIST_P 0.25

// skiplist node
typedef struct zskiplistNode {
    int key;
    int value;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
    } level[1];
} zskiplistNode;

// skiplist
typedef struct zskiplist {
    struct zskiplistNode *header;
    int level;
} zskiplist;

Redis also defines a richer node used by the actual sorted‑set implementation:

typedef struct zskiplistNode {
    robj *obj;               // member object
    double score;            // member score
    struct zskiplistNode *backward; // backward pointer
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;   // distance to next node at this level
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zset {
    dict *dict;   // maps member -> score
    zskiplist *zsl;
} zset;

Core Operations

Creating an empty skiplist and a node:

zskiplistNode *zslCreateNode(int level, int key, int value) {
    zskiplistNode *zn = (zskiplistNode *)malloc(sizeof(*zn) + level * sizeof(zn->level));
    zn->key = key;
    zn->value = value;
    return zn;
}

zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl = (zskiplist *)malloc(sizeof(*zsl));
    zsl->level = 1;
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL, 0, 0);
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    return zsl;
}

Random level generation (probability 0.25, max level 32):

int zslRandomLevel(void) {
    int level = 1;
    while ((rand() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level++;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

Insertion algorithm (simplified):

zskiplistNode *zslInsert(zskiplist *zsl, int key, int value) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    int i, level;
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        while (x->level[i].forward && x->level[i].forward->key < key) {
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    level = zslRandomLevel();
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) update[i] = zsl->header;
        zsl->level = level;
    }
    x = zslCreateNode(level, key, value);
    for (i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
    }
    return x;
}

Deletion follows a similar pattern, first locating the node, then rewiring the forward pointers and adjusting the skiplist level if necessary.

Redis Sorted‑Set Commands

zadd key score member – add or update a member

zrem key member – remove a member

zincrby key increment member – increase a member’s score

zrank key member – get rank (ascending)

zrevrank key member – get rank (descending)

zrange key start stop – get members in a score range (ascending)

zrevrange key start stop – same but descending

zcard key – number of elements

zscore key member – retrieve a member’s score

Practical Example

The article demonstrates a use‑case of maintaining a “hot topics” leaderboard with a maximum of 10 entries. New topics are added with zadd , the lowest‑scored entry is removed with zremrangebyrank 0 0 , and rankings are queried with zrank or zrevrank . The example shows how the skiplist guarantees O(log N) performance even when the set grows large.

Conclusion

Redis sorted sets combine the fast lookup of a hash table with the ordered traversal of a skiplist, providing an efficient solution for ranking, leaderboards, and any scenario that requires ordered, score‑based access. Understanding the underlying skiplist implementation helps developers appreciate the performance characteristics and extend the data structure when needed.