Balanced trees (red-black, AVL)
Why do balanced binary trees matter so little in data engineering, and what idea do they carry?
State the honest position first: these matter much less in data engineering than their place in an algorithms course suggests, and the reason is one number. A balanced binary tree is a B-tree with fanout 2. Its depth is log₂ n, and every level is an independent pointer chase: a dependent cache miss in memory, a dependent I/O on disk.
Balanced trees survive only where that cost does not dominate:
- language standard libraries (
std::map,TreeMap), where entries are individually allocated on the heap anyway and n is small; - operating-system kernels (the Linux scheduler's run queue, the tracking of memory areas), where worst-case bounds matter more than throughput;
- MVCC version chains (the list of versions of one database row), where the chain is short.
They do not survive anywhere the data is large or the medium is slow.
The one transferable idea: the balance factor
An AVL tree enforces height ≤ 1.44 log n, so it rebalances more aggressively. A red-black tree tolerates height ≤ 2 log n, so it rebalances less. A tighter invariant means faster reads and more write work. A looser invariant means slower reads and less write work. That is the read/write dial in miniature, and once you see it in this form you see it everywhere:
| Structure | What disorder is tolerated | Tight means | Loose means |
|---|---|---|---|
| AVL vs red-black | Height bound | Faster lookup | Fewer rotations |
| LSM | Size ratio T | Fewer runs to read | Less write amplification |
| Hash table | Load factor α | Fewer probes | Less memory, fewer resizes |
| B-tree | Fill factor | Less space, better scans | Fewer splits |
| Vacuum / compaction | Trigger threshold | Less bloat | Less background I/O |
Every structure that maintains an invariant exposes a parameter for how much violation it tolerates before paying to repair it, and that parameter is always the read/write dial. A rebalancing threshold and a compaction policy are the same kind of object. We call it the disorder-tolerance knob.
Whether this deserves the rank of a "law" is a fair question. It may be the mechanism by which a design moves along the RUM triangle, rather than an independent law. A law should constrain what is possible. This one describes how a choice is parameterized. So we treat it as a named mechanism, not a law. It would earn law status only if it predicted something the RUM triangle does not.