Day 19: Skip Lists

Phase 1 · Jun 7, 2026

Agenda (2–3 hours)

• Read (45 min): Pugh "Skip Lists: A Probabilistic Alternative to Balanced Trees" (1990) §1–3
• Study (45 min): Trace insert and search operations; derive the expected O(log n) search complexity
• Practice (45 min): Implement a skip list in Rust (sequential, not concurrent); test insert, search, delete
• Challenge (30 min): How does ConcurrentSkipListMap in Java achieve lock-free concurrent access? What Rust concurrency primitives would you need?

What Is a Skip List?

A layered linked list that provides O(log n) average-case search, insert, and delete — like a balanced tree, but simpler to implement and amenable to concurrent access.

Invented by William Pugh (1990) as an alternative to balanced BSTs.

Level 3: ----1----------------9----
Level 2: ----1----3--------7--9----
Level 1: ----1--2-3--4--5--7--9--10
Level 0: --0-1--2-3--4--5--7--9--10

Search starts at the highest level and descends.

Probabilistic Structure

Each node has a height determined at insertion time:

• Height 1: probability 1
• Height 2: probability p (e.g., 1/2)
• Height 3: probability p²
• Height k: probability p^(k-1)

With p=1/2 and n elements, the expected maximum height is log₂(n).

No rebalancing needed — the probabilistic distribution maintains the invariant on average without deterministic rotation operations (unlike AVL or red-black trees).

Why Skip Lists for MemTable?

RocksDB and LevelDB use a skip list as the MemTable:

1. Ordered: keys are sorted → efficient sequential scan → fast SSTable writes
2. Lock-free variants: CAS on node pointers enables concurrent insert + read without full locking
3. Simple compaction: a sorted skip list can be iterated sequentially to write a sorted SSTable
4. Good cache behavior: compared to pointer-heavy B-trees, skip list nodes are compact

Concurrent Skip Lists

The key insight: inserting a node only modifies a small, contiguous set of forward pointers.

Lock-free insert (Java's ConcurrentSkipListMap approach):

1. Find predecessor nodes at each level
2. Allocate new node (not yet visible)
3. CAS the bottom-level forward pointer (mark as "being inserted")
4. Link remaining levels with CAS — partially linked is OK during search

Searches and partially-inserted nodes: searches that encounter a node being inserted simply ignore it or help complete it.

Key Takeaways

• Skip lists provide balanced-tree performance with simpler implementation
• Probabilistic height assignment eliminates the need for rebalancing
• Used as the MemTable in LSM storage engines (RocksDB, LevelDB) due to sorted ordering and lock-free potential
• Redis's sorted set (ZSET) is implemented as a skip list + hash map

Tomorrow: Distributed Hash Tables (DHTs) — how peer-to-peer systems locate data without a central directory.