Understanding Skip Lists and Their Implementation in Redis

Recently, while studying Redis's underlying implementation, I noticed that its sorted set uses a skip list, prompting me to record the details.

Skip List

A skip list is an ordered random data structure that maintains multiple forward pointers in each node to achieve fast access.

What is a Skip List?

For a singly linked list, even if the data is ordered, random search still requires traversing from head to tail, resulting in O(n) complexity.

By adding index layers—extracting every two nodes to a higher level—we can reduce the number of traversed nodes dramatically.

If we want to find node 8, we first search the index layer; when we encounter node 7 whose next node is 9, we know 8 lies between them and descend to the base list, reducing traversals from 8 to 5.

Adding more index layers further improves search efficiency, especially for large data sets.

Redis Skip List

Redis uses a skip list as one of the underlying implementations for sorted set keys, especially when the set contains many elements or long string members.

Why does Redis choose a skip list for large or long‑string elements? Because a skip list offers a space‑for‑time trade‑off: the extra index nodes consume memory, but the benefit grows with element count or size, while the overhead remains acceptable.

Redis Skip List Implementation

Redis defines two structures: zskiplistNode for nodes and skiplist for metadata such as header, tail, level, and length.

header: pointer to the head node (O(1) access).

tail: pointer to the tail node (O(1) access).

level: the highest level among nodes (excluding the head), obtainable in O(1).

length: number of elements (excluding the head), also O(1).

The node structure includes level, backward pointer, score, and member object, with ordering based on score and then member lexicographically.

Simple Skip List Java Implementation

public class SkipNode
{
    // data area
    public Integer score;
    public T value;

    // pointers to neighboring nodes at various levels
    public SkipNode up;
    public SkipNode down;
    public SkipNode left;
    public SkipNode right;

    public SkipNode(Integer score, T value) {
        this.score = score;
        this.value = value;
    }
}

public class SkipList {
    // node count
    public int num;

    // maximum height
    public int max_hight;

    public SkipNode head;
    public SkipNode tail;

    // random generator
    private Random random;

    public SkipList() {
        this.max_hight = 6; // set max height to 6 layers
        this.num = 0; // initially no nodes
        this.head = new SkipNode(Integer.MIN_VALUE, null);
        this.tail = new SkipNode(Integer.MAX_VALUE, null);
        this.random = new Random();
        this.head.right = tail; // link head to tail
        this.tail.left = head;
    }

    /** basic operations: add, delete, search */
    private SkipNode find(Integer score) {
        SkipNode start = this.head;
        while (true) {
            while (start.right.score <= score) {
                start = start.right;
            }
            if (start.down != null) {
                start = start.down;
            } else {
                break;
            }
        }
        return start; // start.score <= score
    }

    public Object get(Integer score) {
        if (num < 1) return null;
        SkipNode mark = find(score);
        if (mark.score.equals(score)) {
            return mark.value;
        } else {
            return null;
        }
    }

    public void put(Integer score, Object value) {
        SkipNode mark = find(score);
        if (mark.score.equals(score)) {
            mark.value = value;
            return;
        }
        SkipNode brand_new = new SkipNode<>(score, value);
        brand_new.left = mark;
        brand_new.right = mark.right;
        mark.right.left = brand_new;
        mark.right = brand_new;
        int i = 0;
        while (random.nextDouble() < 0.5) {
            if (i > max_hight) break;
            while (mark.up == null) {
                mark = mark.left;
            }
            mark = mark.up;
            SkipNode up_new = new SkipNode<>(score, null);
            up_new.left = mark;
            up_new.right = mark.right;
            mark.right.left = up_new;
            mark.right = up_new;
            up_new.down = brand_new;
            brand_new.up = up_new;
            brand_new = up_new;
            ++i;
        }
        ++num;
    }

    public boolean remove(Integer score) {
        SkipNode mark = find(score);
        if (!mark.score.equals(score)) {
            return true;
        }
        SkipNode del;
        while (mark != null) {
            del = mark.up;
            mark.left.right = mark.right;
            mark.right.left = mark.left;
            mark = del;
        }
        return true;
    }
}

Finally, the author provides a collection of interview questions from major tech companies (BAT) for readers who are interested.