A Cost Model for the Internal Organization of B + -Tree Nodes
Wilfred J. Hansen · ACM Transactions on Programming Languages and Systems · 1981
Not only must an entire B+-tree support the operations of key insertion, deletion, and lookup, but the organization of keys within each tree node must support these same operations.Choice of the appropriate internal node organization for the keys involves typical space-time trade-offs.This paper presents a cost model for examining these trade-offs and illustrates it by analyzing four promising organizations: binary search, sequential search, square root search, and "partitioned pages."Evaluation of the model for a set of typical parameters shows that binary search is the most economical if all keys are the same length, and square root search is preferable when the key length varies.One interesting result is that space overhead for organizations like linked lists exacts a much higher penalty during some stages of tree growth than during others.