Skip Lists: Probabilistic Alternative to Balanced Trees


Skip lists offer an elegant alternative to balanced tree structures like AVL trees or red-black trees, achieving similar logarithmic search performance through probabilistic layering rather than deterministic rebalancing. While they never became the default choice for most systems, skip lists power production databases like Redis and LevelDB, where their simpler implementation and lock-free potential outweigh the theoretical advantages of trees.

How Skip Lists Work

A skip list starts as a sorted linked list, then adds express lanes. Each element has a random tower height: some nodes appear only in the base layer, while others extend upward through multiple levels. Higher layers skip over many elements, letting searches traverse the structure faster before dropping down to find the exact position.

When searching for a key, you start at the top layer and move right until the next node would overshoot. Then you drop down one level and continue. This descent-and-advance pattern repeats until you reach the target or confirm it doesn’t exist. The expected number of steps is O(log n) because each level approximately halves the remaining distance, just like binary search on an array.

The probabilistic construction is what makes skip lists distinctive. When inserting a node, you flip a coin (or check a random bit) to decide whether it promotes to the next level. With probability 1/2, it stops at level 1. With probability 1/4, it reaches level 2, and so on. This randomization distributes tall towers throughout the structure without requiring global rebalancing operations.

Why Systems Choose Skip Lists

Skip lists shine in concurrent environments. Unlike binary trees, which require complex lock coupling or hand-over-hand locking during rotations, skip lists allow multiple threads to traverse and modify the structure with simpler coordination. Each level is just a linked list, so lock-free insertions using compare-and-swap become tractable. Redis uses skip lists for sorted sets precisely because the concurrent modifications remain manageable without heavyweight locking.

The implementation complexity is another draw. A skip list requires no rotation logic, no color tracking, and no subtree height calculations. The core operations fit in a few hundred lines of straightforward code. For systems where maintainability matters and the theoretical constant factors aren’t critical, this simplicity is a practical advantage.

Memory locality is skip lists’ weakness. Trees pack related nodes near each other in memory, while skip list nodes scatter across the heap with their random tower heights. Each node stores multiple forward pointers, increasing per-element overhead. Traversing levels means chasing pointers through unpredictable memory locations, which hurts cache performance compared to a well-packed B-tree.

Where Skip Lists Appear

LevelDB and RocksDB use skip lists for their in-memory memtable—the write buffer before data flushes to disk. Here, skip lists provide fast insertion and ordered traversal during compaction. The structure lives briefly enough that memory fragmentation doesn’t accumulate, and the write-heavy workload benefits from the low contention.

Redis implements sorted sets with skip lists rather than balanced trees. The probabilistic structure handles the mix of insertions, deletions, and range queries while keeping the codebase manageable. Redis also avoids the worst-case rebalancing pauses that trees can introduce during heavy write bursts.

Outside these examples, skip lists remain niche. Most systems default to B-trees for disk-based storage or hash tables for key-value lookups. The probabilistic guarantees make skip lists harder to reason about in latency-sensitive contexts where tail behavior matters, since an unlucky sequence of coin flips could degrade performance temporarily.

Probabilistic vs. Deterministic Tradeoffs

Skip lists expose a fundamental tradeoff in data structure design: deterministic worst-case bounds versus simpler implementations with high-probability guarantees. Red-black trees promise O(log n) operations in every case, while skip lists deliver O(log n) expected performance with a small chance of degradation. For most workloads, the probabilistic behavior averages out, but systems with strict latency requirements may prefer the predictability of trees.

The randomization also complicates testing and debugging. A skip list might work correctly in development and fail under production load because the random seed produces pathological tower distributions. Reproducibility requires careful control of the random number generator, which tree structures avoid entirely.

Skip lists remain a valuable tool in specific contexts—concurrent in-memory indexes, systems where code simplicity reduces operational risk, and environments where probabilistic guarantees suffice. They demonstrate that sometimes a simpler algorithm with slightly weaker guarantees wins in practice, even when theory suggests a more complex deterministic structure should dominate.