The big picture: a data structure is a bet

Why is a data structure a bet, and why does Big-O no longer tell us which one wins?

A different kind of constraint

In the physical parts of a systems course, the constraint is the same for everybody. A page is 16 KB whether you like it or not. A hop between two cloud datacenters costs 0.5 ms whether you like it or not. These are physical constraints.

This mechanism is different because the constraint is no longer physical. It is informational. A data structure is a precommitment about what questions will be asked. You choose, in advance and with no way back, which queries get one probe (one lookup step) and which queries need a full scan. The hardware sets the exchange rate. The structure decides what you buy with it.

Two consequences follow immediately. Both are invisible in an algorithms course.

Consequence 1 — Big-O stops being the judge

A skip list and a B+tree are both O(log n). One runs almost every transactional database on earth. The other runs the in-memory write buffer of a few databases. Big-O counts comparisons. The hardware charges for dependent fetches, at its own granularity.

The whole design space of this mechanism is a search for structures whose branching factor (how many children a node has, also called fanout) matches the transfer unit of the level where they live. This is why the same idea, the B-tree, appears with fanout 4 in an in-memory index tuned for cache lines, and with fanout 680 on a 16 KB disk page. The idea is the same. The constant is set by the layer below.

We call this the Batch-size law:

Consequence 2 — Three currencies, and you cannot underspend all three

Every structure spends the three currencies (see "Before you start" on the overview): read amplification, write amplification and space amplification. The classic statement is the RUM conjecture (Read, Update, Memory; Athanassoulis et al., 2016): optimize any two and the third gets worse.

Be precise about what kind of claim this is. It is not a proved theorem like some results in distributed systems. It is a well-supported empirical framing, and nobody has found a counterexample in practice. It is best used as a forcing question: "Which of the three did this design just spend?" It is a less safe tool as a law you cite to win an argument.

Example. Suppose you want fast reads. You keep data sorted and add extra indexes. Reads are cheap now, but every write must update the sorted order and every index (write amplification up) and the indexes use space (space amplification up). You cannot get all three low at once.

---

Two more dimensions: order and mutability

Besides the three currencies, there are two properties that decide what a structure can do at all.

What the structure preserves: order or not. This is a deeper split than the textbook's "tree versus hash". It decides the class of question you can answer, not just how fast. A hash table destroys order, so it can never answer a range question ("all scans between 9:00 and 10:00") at any price. A B+tree preserves order and pays for that on every single write. Nothing here lets you buy order after the fact for less than the cost of a sort.

Mutability: edit in place or rebuild. Some structures can be edited in place. Others must be rebuilt. If a layout cannot be updated in place, it grows two companions: an indirection layer (a lookup table that says where the current version of each thing lives) and a collector (a background job that frees old versions). An SSD's FTL is one example. An LSM-tree's compaction is another. We call this the Immutability law:

It recurs three times here (LSM compaction, copy-on-write B-trees, perfect-hash rebuilds). But immutability has a second face: it is not only a cost, it is also a resource. A structure that knows its contents will never change can spend two bits per key where a mutable structure spends forty. Lookup structures shows how.

---

What the five groups are about

This mechanism has five groups of structures, each answering a different kind of question: