Yao's classical analysis of B-tree space utilization assumes keys arrive one at a time, uniformly at random. Under this model, even splitting — the standard strategy where a full node splits into two half-full nodes — achieves roughly ln(2) ≈ 69% utilization. The result is elegant and well-understood.
Note (2026-11-15; read against the paper's full text): the paper does not report that even splitting keeps its 69 percent utilization under batching. Its summary table, for a fixed batch size r on nodes of capacity B, gives the fill achieved by even splitting as a range that falls as the batch grows relative to the node: between 0.664 and 0.693 only for very small batches (r/B up to about 0.0058), between 0.583 and 0.664 for r/B up to 0.21, and 0.583 for r/B up to 7/18, with other strategies (deferred even splitting, a form of uneven splitting) used for larger batches, since even splitting achieves only about 50 percent fill around r = B/2. The paper says it first demonstrates 'the surprisingly erratic behavior' of these simple algorithms across batch sizes. The essay's 'for many batched scenarios, even splitting maintains its 69% utilization' and its closing claim that the classical result is more robust than its proof are not what the paper reports; its own claim is that even splitting 'works well for many workloads in our extended class' and that simple alternative strategies provably maintain good utilization for the rest.
Real workloads arrive in batches (arXiv:2603.12211). A database receives a bulk import, a log ingests a burst, an index absorbs a merge. The question is whether the classical utilization guarantee survives batching.
For many batched scenarios, even splitting maintains its 69% utilization — the classical result is more robust than its assumptions. But there exist batch patterns where even splitting falters, and alternative splitting strategies become necessary. The analysis separates the cases: the structural property of the splitting rule determines which workload patterns preserve utilization and which destroy it.
The structural observation: a result proved under idealized assumptions can be more robust than the proof. Yao's analysis required uniform random insertion; the result holds for a broader class of inputs than the proof technique could reach. The assumption was sufficient but not necessary. The gap between “conditions under which we can prove the result” and “conditions under which the result holds” is itself informative — it reveals that the mechanism driving utilization is simpler than the mechanism driving the proof.