In the landscape of in-memory data structures, the skip list occupies a unique niche. While balanced binary search trees like AVL or Red-Black trees are the standard for maintaining ordered data, their rebalancing operations—involving complex tree rotations—can be computationally expensive and difficult to implement in concurrent environments. Redis, by design, favors simplicity and performance, opting for the skip list to implement its Sorted Sets (ZSETs).

A skip list is essentially a layered, multi-level linked list. By maintaining multiple levels of forward pointers, it allows for logarithmic search complexity, effectively mimicking the performance characteristics of a binary search tree while relying on randomization rather than structural rotations to maintain balance.

The Anatomy of a Skip List

At its base layer (Level 0), a skip list is a standard sorted linked list. This level contains every element in the set. Above this base layer, additional levels are constructed where each node has a probability ‘p’ of being promoted. If a node is promoted to Level 1, it exists in both Level 0 and Level 1. This continues until a maximum height is reached.

This hierarchy allows search algorithms to ‘skip’ large segments of the list. When searching for a target key, the algorithm starts at the highest level and moves forward until the next node’s value exceeds the target. It then drops down a level and repeats the process. This ‘leapfrog’ traversal provides an average search time of O(log n).

Probabilistic Balancing

Unlike Red-Black trees that enforce strict invariants, skip lists use a random number generator to decide the height of a new node during insertion. A common implementation uses a geometric distribution where the probability of a node reaching height ‘h’ is p^(h-1).

function randomLevel(p: number, maxLevel: number): number {
  let level = 1;
  while (Math.random() < p && level < maxLevel) {
    level++;
  }
  return level;
}

The beauty of this approach is that it is self-balancing on average. While a pathological case could theoretically result in a degenerate list, the probability of this occurring in a reasonably sized dataset is statistically negligible. This simplifies insertion significantly, as the structure does not require global rebalancing operations.

Why Redis Prefers Skip Lists

Redis chose the skip list over balanced trees primarily for two reasons: implementation complexity and range query performance. Implementing a thread-safe, non-blocking Red-Black tree is notoriously difficult. Skip lists, by contrast, can be updated using atomic operations more gracefully, and their structure is inherently more flexible for range-based lookups.

In a Sorted Set, Redis needs to perform two types of operations efficiently: point lookups and range scans. Once the skip list finds the starting node for a range query, it can simply traverse the base level (Level 0) horizontally. Because Level 0 is a standard linked list, this scan is extremely cache-friendly and requires no further tree traversal overhead.

Trade-offs and Limitations

• Memory Overhead: Each node in a skip list requires multiple pointers, which can consume more memory than a standard tree node.
• Cache Locality: While the base level is linear, the higher levels involve jumping across memory, which can lead to cache misses compared to compact arrays or static structures.
• Randomness Dependency: Performance is probabilistic; while extremely reliable at scale, it does not provide the same worst-case guarantees as a rigid tree structure.

Conclusion

The skip list is an elegant testament to the power of randomized algorithms in systems programming. By trading strict structural invariants for probabilistic balance, it achieves O(log n) performance with significantly lower implementation overhead than traditional balanced trees. For Redis, this design choice has proven to be the correct one, offering the necessary throughput and flexibility to handle millions of operations per second in real-world production environments.