# Skip list

A skip list is a probabilistic ordered map built from stacked linked lists. The bottom list contains every key in sorted order. Each higher list samples roughly half the nodes of the one below, giving an expected O(log n) search by descending from the top: scan forward at the current level until the next key overshoots the target, drop down one level, repeat. Insertions and deletions are also O(log n) expected.

Compared to a balanced BST (red-black, AVL), the appeal is simplicity and concurrency. No rotations, no recoloring, no recursive rebalance. The data structure is local — an insert only touches the nodes on its search path. That locality is why most lock-free ordered-map implementations are skip lists rather than balanced trees: the Fraser/Harris algorithm builds a concurrent skip list with marked-pointer logical deletion and bottom-up CAS-chain insertion, and there's no equivalently practical lock-free balanced BST.

The MemTable in an [[lsm-tree]] is usually a skip list. RocksDB and LevelDB both use one. The combination of ordered iteration (for flushing to a sorted SSTable), O(log n) insert (for accepting writes), and amenability to concurrent readers makes it the standard fit for write-buffered storage engines.

Variants worth knowing:

- **Doubly-linked level 0** — adds back pointers at the bottom level for O(1) reverse iteration. Plain skip lists need an O(log n) search to walk backwards.
- **Deterministic skip list** — replaces the coin-flip height with a fixed pattern, giving worst-case rather than expected bounds at the cost of harder concurrent updates.
- **[[splay-list]]** — adaptively raises hot keys toward the top, reducing search depth from log n to log(1/p) where p is the key's hit ratio (Aksenov 2020).
- **MVCC skip list** — versions each node with a timestamp range; readers see a snapshot at a chosen time. Common in databases that want point-in-time queries on the in-memory write buffer.

[[skiplist|gregburd/skiplist]] is a header-only C library covering most of these: lock-free Fraser/Harris by default, optional splay, MVCC snapshots, doubly-linked level 0, optional single-threaded mode that drops atomics entirely.