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.
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.