Search tools and guides ⌘K
II · Trees, with shape

Skip list

Probabilistic balance, beautifully.

1989 · William Pugh · University of Maryland
The story

Pugh's paper is a masterpiece of plain language: "Skip Lists: A Probabilistic Alternative to Balanced Trees". Instead of complex rotations, every node flips a coin for how high to be. Tall nodes form an "express lane" past short ones. Average-case all-O(log n), worst-case O(n). But the worst case has probability 2^(−n).

How it works

A linked list with extra forward pointers at exponentially decreasing densities. Lookup walks the highest level until overshooting, drops down, repeats. Insert: flip coins to determine height, splice in at all relevant levels.

Where it lives

Redis sorted sets (ZSET). LevelDB and RocksDB's in-memory MemTable. Concurrent maps in Java's ConcurrentSkipListMap. Apache Cassandra.

The key insight

Lock-free skip lists are easier to write than lock-free balanced trees. That single property is why they appear inside high-concurrency systems where red-black trees would need a global lock.

More in Trees, with shape
Binary search tree Sorted, but with shortcuts. AVL tree Always height-balanced, to within one. Red-black tree Almost balanced, much faster to maintain. B-tree / B+ tree The shape of a database index. Heap (binary heap) A priority queue you can grep. Trie (prefix tree) A tree you walk one character at a time. Segment tree Range queries in logarithmic time. Fenwick tree (BIT) Prefix sums, with constant tweaks. Treap BST and heap, secretly the same tree. Splay tree No metadata — and surprising amortised guarantees.
Across the cabinet
IV Bloom filter A set, in a thousandth of the space. IV HyperLogLog Count distinct, in 12 KB. IV Count-Min sketch Approximate frequencies, in tiny memory. IV MinHash Set similarity, in a few hashes. IV t-digest Quantiles, fairly accurate, fully streaming. V Suffix array All suffixes, sorted. V Suffix tree Every substring, in linear space. V Rope A tree of small strings.
← All data structures