\(B\)-trees with inserts and deletes: Why free-at-empty is better than merge-at-half (Q686641)

\(B\)-trees are a well-known and widely used data structure which allows efficient search in very large databases. A \(B\)-tree of parameter \(p\) is a balanced tree in which the distance between the root and any leaf is the same and any non-leaf mode has between 1 and \(2p-1\) children. The paper investigates the space utilization (i.e. the expected percentage of a node used to store data) under insertions and two policies of deletions: (1) free-at-empty, when a node is deleted when it becomes empty and the deletions are propagated upwards, and (2) merge-at-half, when a node becoming half empty after a deletion is merged with its neighbor. Analytical results are proved and simulation data is reported for these two strategies. The paper provides a simple rule of thumb, depending on the comparative rate of delete vs. insert operations, which indicates when one of the strategy is to be preferred.