Understanding Redis Sorted‑Set Implementation: From Linked List to Skiplist

Background : The article begins with an ordered singly linked list, demonstrating insertion and query operations whose time complexity is O(N), and then motivates the need for a more efficient structure.

1. Singly Linked List

It describes the node definition ( typedef struct node { int data; struct LinkNode *next; } LinkNode; ) and shows example code for initializing a list and inserting a value (e.g., inserting 25 between 20 and 30). The insertion and search processes are illustrated with step‑by‑step diagrams, confirming both have O(N) complexity.

2. Skiplist Formation

To improve performance, the article introduces the skiplist, a multi‑level indexed version of a linked list. By adding higher‑level index nodes (e.g., every two nodes), the search path is reduced, achieving O(log N) time. The formation process, index levels, and complexity analysis are explained.

2.1 Skiplist Time‑Complexity Derivation

Using the relation N/2^M = 2, the height M is shown to be log₂(N) − 1, leading to overall O(log N) complexity for both insertion and query.

3. Redis Skiplist Implementation

Key structures are presented:

typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode;

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

Attributes such as ele , score , forward , and span are explained.

3.2 Random Level Generation

The function int zslRandomLevel(void) generates node heights with probability p = 0.25, capping at 64 levels, ensuring a power‑law distribution.

3.3 Skiplist Creation

Source code for creating a skiplist ( zskiplist *zslCreate(void) ) allocates memory, initializes level 1, length 0, and sets up the header node.

3.4 Insertion

The insertion routine ( zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) ) performs four steps: locate the insert position, generate a random level, splice the new node into each relevant level, and update backward pointers and length. Detailed code excerpts illustrate rank calculation, span updates, and level adjustments.

3.5 Query by Rank and Score

Functions unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) and zskiplistNode *zslGetElementByRank(zskiplist *zsl, unsigned long rank) are shown, demonstrating O(log N) lookups using the multi‑level index.

3.6 Deletion

The delete operation ( int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) ) first finds the target node, then calls zslDeleteNode to adjust spans, forward pointers, backward links, and possibly reduce the skiplist height.

3.7 Comparison with Other Structures

The article compares skiplist with hash tables, balanced trees, and B‑trees, highlighting skiplist’s lower implementation complexity, better cache locality for range queries, and lower memory overhead, which explains Redis’s choice.

Conclusion

By walking through the evolution from a simple linked list to a fully‑featured skiplist and dissecting Redis’s C source, the article equips readers with a deep understanding of the Sorted‑Set’s internal mechanics and the reasons behind its design decisions.