Performance guarantees for B-trees with different-sized atomic keys
Michael A. Bender, Haodong Hu, Bradley C. Kuszmaul · 2010
Most B-tree papers assume that all N keys have the same size K, that F = B/K keys fit in a disk block, and therefore that the search cost is O(logf+1 N) block transfers. When keys have variable size, however, B-tree operations have no nontrivial performance guarantees.