Analysis of B-Trees

So far, we’ve established that:

1. In the external memory model, the running time of find(x), add(x), and remove(x) in a $B$-tree is $O(\log_Bn)$.
2. In the word-RAM model, the running time of find(x) is $O(\log n)$, and the running time of add(x) and remove(x) is $O(B\log n)$.

The following lemma, however, shows that we have overestimated the number of merge and split operations performed by $B$-trees.

Lemma 1: Starting with an empty $B$-tree and performing any sequence of $m$ add(x) and remove(x) operations results in at most $3m/2$ splits, merges, and borrows being performed.

Proof: The proof of this has already been sketched for the special case in which $B = 2$. The lemma can be proven using a credit scheme, in ...