The Skip List: Probabilistic Sorted Index

A skip list is the canonical memtable implementation in LevelDB, RocksDB, and many other LSM engines. It's a sorted linked list with extra "express lanes" at higher levels that let you skip over many nodes per step. Average lookup, insert, and delete are all O(log n).

The Structure

L3:  head ----------> 25 ----------------------> NULL
L2:  head ----------> 25 ----> 60 -------------> NULL
L1:  head ----> 12 -> 25 ----> 60 -> 75 -------> NULL
L0:  head -> 3 -> 12 -> 25 -> 41 -> 60 -> 75 -> 88 -> NULL

Every node lives at level 0 (the base list). Each node randomly "promotes" itself upward with probability p (typically 0.5 or 0.25). Higher levels are sparser. Searches start at the top-left and walk right-then-down, halving the search space at each promotion.

Why Skip Lists Over Balanced Trees?

• Simpler code. Insertion is ~25 lines vs hundreds for a red-black tree.
• Lock-friendly concurrency. Reads can be lock-free. Writes lock only the predecessor nodes at each level.
• Cache behaviour. Each node is fixed size; no tree rotations move data around.
• Expected performance. O(log n) with extremely small constants in practice.

The trade-off: worst-case is O(n) (a long run of unlucky coin flips). For ~10^9 elements with p=0.5, the probability of pathological behaviour is astronomically small.

Operations

Search(k):

1. Start at the head, top level.
2. While current.next[level] is not None and its key < k: advance right.
3. Otherwise drop down one level. Repeat until level 0.
4. Then current.next[0] is the candidate; check if its key == k.

Insert(k, v):

1. Run a Search, recording the predecessor at every level.
2. If key already exists at level 0, just update the value.
3. Otherwise pick a random level (geometric distribution) for the new node.
4. Splice it in at every level up to its random height.

Random level:

Memory Cost

Each node has on average 1 / (1 - p) forward pointers. For p=0.5 that's 2 pointers — about the same overhead as a doubly-linked list.

Why Memtables Love It

Concurrent writers can insert without blocking each other (as long as they touch different keys). Readers see a consistent snapshot. That's why every serious LSM engine uses a skip list memtable.