Skip Lists & Merkle Trees

Two Structures, One Instinct

This lesson closes §8 with two structures that look unrelated — one makes an ordered set fast to search, the other makes a dataset cheap to verify — but they're built on the same instinct, and it's an instinct you've now met several times in this section: beat O(n) by building a logarithmic-height hierarchy of shortcuts, so you climb instead of walk.

A skip list stacks express lanes of extra pointers over a sorted linked list. A plain linked list must be scanned one node at a time — O(n) — but the express lanes let a search skip huge spans and drop down only when it gets close, so it finishes in about log n hops. A Merkle tree stacks extra hashes over data blocks, up to a single root hash. Comparing two big datasets, or proving a piece belongs to one, would naively cost O(n) — but the tree of hashes lets you climb, so you can find exactly what differs, or prove inclusion, in about log n hashes.

That's the whole connection: a skip list keeps a few extra pointers; a Merkle tree keeps a few extra hashes; both spend that small redundancy to turn a linear walk into a logarithmic climb. One is the structure behind Redis sorted sets and the memtable of every LSM engine; the other is behind Git, Bitcoin, Cassandra's repair, and your filesystem's integrity checks. Let's take them one at a time.

Skip Lists: Express Lanes over a Sorted List

Start with an ordinary sorted linked list. It's simple and it's easy to insert into, but searching it is a slog: to find a value you walk from the front, one node at a time, until you reach it — O(n). A balanced binary tree fixes the search cost but pays for it in complexity (rotations, rebalancing). The skip list (William Pugh, 1990) gets the O(log n) search without the tree's machinery, using a beautifully simple idea: build express lanes over the list.

Picture the full sorted list as the bottom lane, level 0. Above it, add sparser lanes: level 1 contains maybe half the nodes, level 2 half of those, and so on. Each node is present on level 0 up to some height, and — here's the trick — that height is chosen by flipping a coin: when a node is inserted, keep flipping, and promote it one lane for each heads until the first tails. Since each extra lane needs another heads (probability ½), about half the nodes reach level 1, a quarter reach level 2, an eighth reach level 3 — a tower only about log n lanes tall.

Searching rides those lanes. Start at the head on the top lane and move right while the next node is smaller than your target; when the next node would overshoot, drop down one lane and keep going. Up high you leap over large spans; down low you refine. In the picture, searching for 42 takes just 3 hops — head to 25 on the top lane, 25 to 38 one lane down, then 38 to 42 on the bottom — versus scanning all 10 as a linked list would. Measured over a small list the average was 3.6 hops against a linked list's 8, and the gap only widens: at a million keys a skip-list search is about 20 hops, not a million. Play with the lab — insert values and watch each new node roll its coin-flip tower, then search and watch the path skip down the lanes.

A live skip list. Insert any number and watch its new node roll a random coin-flip level and splice into those express lanes. Then search for a value and the path animates: it rides the top lane to the right, drops down a level whenever the next node would overshoot, and lands on the target — with the hop count shown against what a plain linked list would scan. The taller the value’s tower, the farther a search can skip. Real skip-list math, so the hops really do stay near log n while a linked list would walk all n.

A skip list, a sorted linked list made fast by stacking express lanes of pointers over it. Every value lives on the bottom lane, level 0, the full sorted list; each node also rises to higher lanes based on coin flips, so about half the nodes reach level 1, a quarter reach level 2, and so on — a structure only about log n levels tall. To search, start at the head on the top lane and move right while the next node is smaller than the target; when it would overshoot, drop down a lane. Searching for 42 here takes just three hops — head to 25 on the top lane, 25 to 38 one lane down, then 38 to 42 on the bottom — instead of scanning all ten nodes. It is the same idea as the skip pointers in a search index, generalized, and unlike a balanced tree it needs no rotations. At a million keys a search costs about twenty hops rather than a million.

No Rotations Required — and Where Skip Lists Run

The coin flip isn't a gimmick; it's the whole reason skip lists are loved. A balanced tree keeps its O(log n) height by enforcing balance — every insert may trigger rotations and recoloring to keep the tree from leaning, and getting that logic exactly right (AVL rotations, red-black invariants) is famously fiddly. A skip list keeps its height by probability instead: it just rolls a random level and splices the node into those lanes. No rotations, no rebalancing, no global invariant to maintain. Yes, a pathological run of coin flips could make it tall, but no particular input triggers the worst case every time — unlike a naive binary search tree, which degrades to a linked list on already-sorted input. In exchange for accepting probabilistic balance instead of guaranteed balance, you get code that's dramatically simpler to write correctly.

That trade is exactly why skip lists show up in production systems that value simplicity and concurrency:

Redis implements its sorted set (ZSET) as a skip list paired with a hash table — the skip list gives O(log n) rank and range queries (ZRANGE, ZRANK), the hash table gives O(1) score lookup by member. (Small sets use a compact listpack encoding and Redis promotes them to the real skip-list encoding once they grow past a threshold — you can watch OBJECT ENCODING flip from listpack to skiplist.) Antirez chose skip lists over balanced trees precisely because they're simpler to implement and debug for the same performance.
The memtable of an LSM engine like RocksDB or LevelDB is typically a skip list — it keeps the most recent writes sorted in memory before they're flushed to an SSTable (the sorted structure the storage lessons relied on).
Java's ConcurrentSkipListMap is a lock-friendly concurrent ordered map: because an insert only touches local pointers and never rebalances the whole structure, skip lists are far easier to make concurrent than balanced trees.

Simple to write, easy to make concurrent, O(log n) in practice — that's a skip list.

How a skip list stays balanced without a balanced tree’s machinery: coin flips instead of rotations. When a node is inserted it keeps flipping a fair coin, rising one lane for each heads and stopping at the first tails, so it reaches level 1 with probability one half, level 2 with one quarter, level 3 with one eighth. The picture shows this geometric halving: the bottom lane holds all sixteen nodes, the next about eight, then four, then two — a structure about log-base-2-of-n lanes tall, and no particular input triggers the worst case every time. The payoff is simplicity: a balanced AVL or red-black tree must rotate and recolor on every insert to stay balanced, which is easy to get wrong, while a skip list just rolls a random level and splices in, with no rotations and no rebalancing. This is why Redis sorted sets are built on a skip list.

Merkle Trees: One Root for a Mountain of Data

Now the second structure, aimed at a completely different question: not how do I search fast? but how do I know this data hasn't changed — and prove it — without rereading all of it? The answer is a Merkle tree (Ralph Merkle, 1979), also called a hash tree, and it's a hierarchy of hashes.

Build it bottom-up. Chop your data into blocks and hash each one — those are the leaves, leaf = H(block). Then hash each pair of leaves together to get their parent, parent = H(left ‖ right) (‖ means concatenate). Hash pairs of parents, and so on, until you're left with a single hash at the top: the Merkle root. That one root is a fingerprint of the entire dataset. Here eight blocks collapse to eight leaf hashes, then four, then two, then one root.

The magic property falls out of how hashing works: change any single bit of any block, and its leaf hash changes; that changes the leaf's parent, which changes its parent, all the way up — so the root changes. In the figure, tampering with block 4 flips its leaf hash and the three hashes on the path to the top, and the root goes from 2343b to df60d. The contrapositive is the useful part: if two copies of a dataset have the same root, every block is identical; if the roots differ, something was altered. A single hash tells you whether a mountain of data is intact. That's tamper-evidence, and it's the foundation of Git commits, blockchain blocks, and filesystem checksums. Open the lab, edit a block, and watch the change ripple up to the root.

A live Merkle tree over eight blocks. In tamper mode, edit any block and watch its leaf hash change and the change cascade up the path to the root, which flips — and a compare-and-descend readout names the single differing block and how few hash comparisons it took to find it. Switch to prove mode and pick a block: its log-base-2-of-n sibling hashes light up, recompute the root, and verify that the block is genuinely included — the exact proof a Bitcoin light client checks. One flipped character anywhere changes the root; that is the whole idea.

The structure of a Merkle tree and why it detects tampering. Each data block is hashed into a leaf; every parent is the hash of its two children concatenated; this continues up to a single root hash that fingerprints the entire dataset. Here eight blocks b0 through b7 become eight leaf hashes, then four, then two, then one root. Changing any single block changes its leaf hash, which changes that leaf’s parent, and so on to the root: tampering with block 4 flips its leaf and the three hashes on the path to the root, so the root changes from 2343b to df60d. Because one flipped bit anywhere alters the root, comparing a single root hash reveals whether any block has been altered — the root is a commitment to every block beneath it, which is what makes a Merkle tree tamper-evident.

Find the Diff, Prove Inclusion

"The root changed" is useful, but the two things that make Merkle trees genuinely powerful are what you can do cheaply next — and both work by climbing the tree instead of scanning it.

Find the diff (anti-entropy). Two servers each hold a copy of a dataset and want to know where they disagree. They exchange root hashes. If the roots match, they're already identical — done, with a single hash compared. If not, they compare the roots' children: wherever a child hash matches, that entire subtree is identical and can be skipped; wherever it differs, they descend into it. Recursing down only the differing branches isolates the exact blocks that differ in about log n comparisons — roughly 5 compares for an eight-block tree, not 8 — and then only those blocks need to be transferred. This is precisely how Cassandra and DynamoDB run anti-entropy repair (the deep-background sync you met in the replication lessons): build a Merkle tree per replica, compare, and ship only the diffs.

Prove inclusion (audit proof). Suppose you want to prove that a particular block belongs to a dataset whose root you trust, without handing over the whole dataset. The proof — the audit path — is just the sibling hash at each level from your block's leaf up to the root. To prove block 3 is present you supply 3 sibling hashes (fd25a, bd294, bc427); the verifier hashes them together with the block in order and checks that the result equals the known root. That's log₂ n hashes — for a tree of a billion items, about 30 hashes prove membership. This is exactly how a Bitcoin light client (SPV wallet) confirms a transaction is in a block without downloading the blockchain, and how Certificate Transparency lets anyone verify a certificate was logged. In both moves, O(log n) hashes replace an O(n) transfer or download.

The two things a Merkle tree lets you do cheaply, both by climbing the tree rather than scanning it. First, finding what differs between two copies: compare the two root hashes, and if they differ descend only into the children whose hashes disagree, skipping every matching subtree, until you isolate the differing block — about five hash comparisons for an eight-block tree instead of eight, then sync only that one block, which is how Cassandra and DynamoDB do anti-entropy repair. Second, proving a block belongs: an inclusion proof is the sibling hash at each level from the block’s leaf up to the root, log-base-2-of-n hashes. To prove block 3 you supply three siblings — fd25a, bd294, bc427 — and recompute the root; if it matches, the block is included. A Bitcoin light client verifies a transaction this way without the whole chain. O(log n) hashes replace O(n) transfer or download.

Where Merkle Trees Run, and §8 Closes

Once you see the shape, Merkle trees are everywhere data must be verified at scale. Git is a Merkle DAG: every blob, tree, and commit is named by the hash of its contents, and a commit's hash covers the tree that covers the blobs — so git fetch compares roots and ships only the objects that differ, and any tampering changes every hash up the chain. Bitcoin and Ethereum put a Merkle root in each block header so light clients can verify transactions with tiny proofs. ZFS and Btrfs hash every block into a filesystem-wide Merkle tree, so a scrub detects silent corruption. Certificate Transparency keeps an append-only Merkle log of every TLS certificate issued. BitTorrent and IPFS address content by its Merkle hash. One structure, one root hash, a world of integrity guarantees.

And with that, §8 is complete. Step back and most of the section resolves into two roads out of the B-tree's blind spot. Route A — change the geometry, stay exact, pay in space: the spatial curves and trees (geohash, quadtrees, R-trees, S2/H3), the inverted index, and the skip list here (another exact ordered index, reached for when you want O(log n) search without a balanced tree's rotations). Route B — trade exactness for space, accept a bounded error: the probabilistic sketches (Bloom, Cuckoo, HyperLogLog, Count-Min, MinHash). The Merkle tree rounds out the section with a third kind of power neither road is about — not faster queries but verifiable integrity: proving in a single hash that a mountain of data is intact. Every one of them is a specialized structure a plain B-tree couldn't be, reached for when the query, the scale, or the guarantee demanded it.

What's left of §8 is to make sure it all stuck. The next item is the §8 checkpoint — a chance to prove you can reach for the right specialized structure when a design problem calls for one: spatial when the key is a location, a sketch when exactness can bend, an inverted index when the query is text, a skip list when you need an ordered set, a Merkle tree when you need to verify. See you there.