Expected behaviour of \(B^+\)-trees under random insertions (Q1105354)

Fringe analysis is used to study the behaviour of B \(+\)-trees (B-trees where all the records are stored in the leaves) under random insertions. We obtain bounds for the expected memory utilization and the expected number of accesses to secondary memory per insertion of trees built using the usual insertion algorithm, the B * overflow handling technique, and other techniques derived from the latter. Several other performance measures are also derived, such as bounds for the number of index nodes, the expected height, the expected number of splits per insertion, and the probabilities of 0, 1 and 2 or more splits per insertion. Special emphasis is placed on 2-3 trees. A technique for concurrency in B \(+\)- trees is also analyzed.