System Design Algorithms

Skip Lists

An LSM must accept writes in key order, answer point gets, and dump a sorted stream on flush—without the rotation machinery of a red-black tree. A does that with layered linked lists and : random replace rebalancing.

This note covers structure, search/insert math, concurrency, when to prefer skip lists over trees, and the SD interview angles (memtables, sorted sets, leaderboards).

Lookup journey

Begin at the top express lane from the header.

Hop right

Advance while the next key is still ≤ target.

Drop down

When the next hop overshoots, descend one level.

Decide at base

Level 0 neighbor is the candidate; compare equality.

What actually happens

A skip list is an built from O(log N) expected levels of linked lists. Level 0 contains every key. Each higher level contains a random subset. Search cost is expected logarithmic because each level roughly halves (or quarters) the remaining search space when promotion probability is constant.

Insert walks the same path as search while remembering the predecessor at each level, samples a random height, and splices the new node into those lists. Delete unsplices. There are no rotations—only pointer updates—which is why concurrent variants are popular.

Versus a : skip lists win as an in-memory structure with simple concurrency and easy range iteration. B+ trees win on disk because one page holds hundreds of separators. Do not propose a skip list as your on-disk primary index without a paging story.

Structure and search

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.

Read the diagram definition

flowchart TD
  S["Start at top-left header"] --> R{"Next at this level\n≤ K?"}
  R -->|Yes| Adv["Advance right"]
  Adv --> R
  R -->|No| D{"Lower level exists?"}
  D -->|Yes| Drop["Drop down one level"]
  Drop --> R
  D -->|No| L["At level 0: next is successor\ncheck equality"]

plaintext

Header: sentinel with forward[0..MaxLevel]
Each node: key, value, forward[0..height-1]

Search(K):
  x = header
  for level = top downto 0:
    while x.forward[level] != null and x.forward[level].key < K:
      x = x.forward[level]
  x = x.forward[0]          # successor candidate
  return x if x and x.key == K else miss

Invariant: for every level, keys are strictly increasing
Higher levels ⊆ lower levels (as key sets)

Implementations often store an array of forward pointers sized to the node’s height. The header’s height tracks the current maximum. Caps (e.g. 32) keep towers from growing without bound if the RNG is unlucky.

Insert, delete, and random height

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.

Read the diagram definition

flowchart TD
  F["Find insert predecessors\nper level"] --> H["Sample random height h"]
  H --> L0["Splice into level 0"]
  L0 --> Up["For i in 1..h:\nsplice into level i"]
  Up --> Done["Forward pointers updated"]

plaintext

RandomHeight(p):
  h = 1
  while random() < p and h < MaxLevel:
    h += 1
  return h

Insert(K, V):
  preds[level] = predecessor of K at each level  (from search)
  h = RandomHeight(p)
  node = new Node(K, V, h)
  for i in 0..h-1:
    node.forward[i] = preds[i].forward[i]
    preds[i].forward[i] = node

Delete(K):
  preds = predecessors; node = preds[0].forward[0]
  if node.key != K: return
  for i in 0..node.height-1:
    preds[i].forward[i] = node.forward[i]

The promotion probability p is the main knob. p=1/2 is the classic Pugh choice: about half the nodes appear one level up. p=1/4 uses less pointer memory and fewer levels, with slightly different constant factors on search.

Sizing and probability math

plaintext

Let p = promotion probability (e.g. 1/2)
Expected nodes at level i ≈ N × p^i
Expected max height H ≈ log_{1/p}(N)

Expected forward pointers total ≈ N × Σ p^i ≈ N / (1-p)
  p=1/2 → ~2N pointers beyond the value payload
  p=1/4 → ~1.33N pointers

Search length (intuition):
  At each level you take a geometric number of right hops,
  then drop; ~O(log N) drops and O(1) hops per level in expectation

Worked:
  N = 10,000,000, p = 1/2
  H ≈ log2(1e7) ≈ 23
  Level 10 ≈ 1e7 / 1024 ≈ 9.8k express nodes
  Pointer memory ≈ 2 × 1e7 × 8 B ≈ 160 MB (64-bit) plus nodes

N	p	≈ max height	Pointer overhead factor
1M	1/2	20	~2× pointers / node avg
1M	1/4	10	~1.33×
100M	1/2	27	~2×

Pointer chasing vs trees

Skip-list search follows more random heap pointers than a tightly packed B-tree page. In memory that is often fine; on disk it is usually wrong. Cache-sensitive skiplist variants and arena allocators help locality for memtables.

Concurrency and production uses

ConcurrentSkipListMap-style maps

use CAS on forward pointers, marking bits for logical delete, and careful retry loops. Readers rarely block writers. Ideal for shared in-process indexes and coordination tables.

LSM memtables

RocksDB’s default skiplist memtable supports concurrent inserts and ordered iteration for flush. When the memtable freezes, a single ordered scan writes the SST. Alternative memtables (hash, vector) exist for special workloads.

Sorted sets / leaderboards

Score-ordered structures need rank, range-by-score, and fast update of one member’s score. Skip lists (sometimes paired with a hash map from member→node) give O(log N) updates without rebuilding an array.

Finger search and bulk load

from a recent node speeds nearly-sorted inserts and sequential consumers. Bulk-building from sorted input can assign heights deterministically to pack express lanes evenly.

Skip list vs balanced BST vs B+ tree

Need	Prefer	Why
In-memory concurrent ordered map	Skip list	Simple CAS inserts; no rotations
Lowest constant factors, single-threaded	Highly tuned BST / B-tree in RAM	Better locality; deterministic balance
On-disk index pages	B+ tree	Fanout matches page size
LSM memtable	Skip list (common default)	Ordered + concurrent + easy flush scan

Trade-offs

Simplicity vs locality. Algorithms are easy to explain and implement; pointer chasing can lose to packed arrays/B-trees in tight CPU loops.

Probabilistic vs deterministic bounds. Expected O(log N) is excellent; adversarial RNG or bugs can degrade. Cap height and use a solid PRNG.

Memory. Extra forward pointers (~1.3–2×) plus per-node headers. For millions of tiny keys, that overhead is visible in RSS.

p selection. Smaller p saves pointers and levels; larger p shortens some searches but adds towers. Stick to 1/2 or 1/4 unless profiling says otherwise.

Choosing and explaining skip lists

A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.

Explain the core idea

A skip list is a hierarchy of sorted linked lists where higher levels skip keys; random node heights give expected O(log N) search without rotations.

Insert finds predecessors per level, samples a height, and splices pointers—ideal for concurrent ordered maps and LSM memtables.

Prefer B+ trees for on-disk paging; prefer skip lists for in-memory concurrent sorted structures.

When it belongs

You need an in-memory ordered map with concurrent writers.

You are explaining LSM memtable internals.

Leaderboards / sorted sets need log-time score updates and range queries.

How it fails

Poor randomness or broken height caps → tall skinny towers and slow searches.

Using skip lists as a disk primary index without paging → pointer-chasing I/O disaster.

Memory blow-ups from pointer overhead at huge N with tiny values.

Trade-offs to weigh

Implementation simplicity and concurrency versus cache locality of packed trees.

p=1/2 vs p=1/4: levels and pointer memory versus hop length.

Expected bounds versus deterministic worst-case balanced trees.

Common misunderstandings

Claiming O(1) search because of express lanes.

Confusing skip lists with Bloom filters or skip graphs.

Forgetting that level 0 must still be a correct sorted linked list for ranges.

Wrap-up

Skip lists buy logarithmic ordered maps with probabilistic balancing and friendly concurrency. Size pointer memory, pick p, keep them in RAM, and reach for B+ trees when the medium is disk pages.

Primary sources

Key takeaway

Skip lists are express-lane linked lists with random towers: expected log-time ordered operations, easy concurrency, perfect for memtables and sorted sets—and the wrong default for page-oriented disk indexes.