B-trees and B+trees

Why is a B-tree's fanout set by the page size, and where does its write bill arrive?

B-tree and B+tree

The constraint, derived

A block device moves a minimum unit (a page). So any comparison structure should have a branching factor that fills exactly one unit: a node smaller than a page wastes the transfer, and a node larger than a page costs two transfers. The fanout is:

That is the whole argument for the B-tree. It is not an asymptotic argument. It is that log base 680 of anything you will ever store is a small number.

Move the medium and the fanout moves with it. In memory the transfer unit is a 64-byte cache line, so the best in-memory B-tree has a fanout in the single digits and looks nothing like the disk version. This is why cache-conscious B+trees and ART beat red-black trees in memory for exactly the reason B-trees beat them on disk. The structure is invariant. The constant is set by the layer below. (Batch-size law again.)

B+ versus B: a range-query argument

In a plain B-tree every node holds keys and values. In a B+tree values are stored only in the leaves (the bottom level), and the leaves are linked into a sorted list. Two gains: internal nodes have higher fanout (no payload competes for page space), and a range scan becomes a sequential walk over linked pages instead of repeated descents from the root. Sequential I/O is one to two orders of magnitude cheaper than random I/O, and range predicates are the majority of real query load, so there is no remaining case for a plain B-tree in storage.

The write path is where the bill arrives

In-place update means each row update is a read-modify-write of a full page. The write amplification is page size ÷ row size.

Key order relocates cost

Key order is a lever that moves cost. It is not a detail.

• Random keys (for example UUIDv4 as the primary key) land everywhere in the tree. Pages split all over the place and in steady state are only about 69% full (the classic ln 2 result; ln 2 = 0.693). To store the same data you need 1/0.69 ≈ 1.45× the pages: a 45% space overhead. Your working set (the pages you must keep in memory) inflates by the same factor.
• Sequential keys (auto-increment numbers, UUIDv7, ULID: identifiers that begin with a timestamp) append at the right edge of the tree. Pages fill completely and fragmentation disappears. In exchange, you create one hot page and its latch that every concurrent inserter must pass through.

You did not fix the problem. You converted a space cost into a contention cost. That is Conservation of cost.

Concurrency is why B-trees are hard, not why they are slow

Latch coupling (also called crabbing) means: take the child's latch before you release the parent's. A split that propagates upward then serializes against the root. B-link trees add a pointer from each node to its right sibling, so a reader that arrives in the middle of a split can follow the pointer sideways instead of holding the parent. This removes the need for a top-down exclusive latch in the common case. The root latch is a coherency term (the cost of keeping many cores consistent): a fixed serial fraction that no number of extra cores dissolves.

Copy-on-write B-trees

Copy-on-write B-trees (LMDB, ZFS, Btrfs) write a new path from leaf to root on every update instead of changing pages in place. This gives crash safety without a WAL and MVCC snapshots (consistent views of old data) for free: a reader simply holds an old root pointer. It costs space amplification and needs a collector to free pages that are no longer reachable. That is the Immutability law, now inside a structure rather than a storage device.

The honest boundary condition

B-trees are best when the internal nodes fit in memory and updates are not the dominant operation. They lose badly when (update rate × page/row ratio) exceeds the device's write bandwidth. That is precisely the regime the LSM-tree was invented for.