From the cache line to the cluster.
The whole story in fourteen slides. Move through with the arrows or click a slide — and open the full chapter for any of them from the link below.
The constant factor, and where the data lives.
Same growth. On a real machine, often 10 to 50 times apart.
A cache hit and a cache miss are both O(1).
One is about a hundred times slower than the other. Big-O cannot see the difference.
The structure the hardware was built to love.
Contiguous memory. Elements sit end to end, so the processor prefetches the next one before you ask. Perfect cache behavior — the memory system's best case.
The one weakness: inserting in the middle means shifting everything after it. O(n).
O(1) insertion — by giving up the cache.
Scatter the elements across memory and link them with pointers, and you can splice one in anywhere in constant time.
The two most useful limits on a sequence.
The most important stack in computing is the one every program runs on: the call stack.
O(1) lookup — at the cost of all order.
Instead of searching for where a key lives, a hash table computes it. Run the key through a hash function, go straight to that slot.
The price: ask for "the smallest key" or "everything between 100 and 200" and it has no idea.
Both O(1) average. One is 2× faster.
Chaining chases a scattered pointer — a cache miss. Open addressing probes a flat array — a cache hit. Same complexity, different memory.
Ordering AND O(log n) — what hashing threw away.
A balanced binary search tree keeps data sorted and gives logarithmic search, insert, and delete — all at once. Left is smaller, right is larger, all the way down.
But a binary tree pays a cache miss on every level.
Why every database index is a B-tree.
Pack many keys into one cache-line-sized node. The tree gets shallow — 4 levels instead of 20 — and each level is one cache line. Roughly 8× faster on the same keys.
Turn every random write into a sequential append.
B-trees update in place — random writes scattered across the disk, the thing storage is worst at. The LSM tree never writes in place: buffer in memory, flush sorted files, merge in the background.
RocksDB · Cassandra · the write path of search engines
When one machine is no longer enough.
Spread the data across many machines. To decide which machine owns a key, you reach back to the very first idea: hashing.
hash(key) % N — and consistent hashing lets N change without reshuffling the world.
The machine finishes it.
Between two algorithms in the same complexity class — where most real decisions live — the constant factor and the memory access pattern break the tie. And the only way to know is to measure.
Data Structures on Systems
The full book runs these benchmarks live in your browser, on your own CPU. Read it, fork it, and watch the memory hierarchy appear on your own machine.
data-structures-on-systems.vercel.app
Each slide links to the full chapter it summarizes. Jump to any slide below, or