Analysis of B-Trees

An estimate about B-trees is 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 shows that, so far, 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 which

1. each split(), merge(), or borrow() operation is paid for with two credits, i.e., a credit is removed each time one of these operations occurs; and
2. at most three credits are created during any add(x) or remove(x) operation.

Since at most 3 m credits are ever created and each split, merge, and borrow is paid for with two credits, it follows that at most $3m/2$ splits, merges, and borrows are performed. These credits are illustrated using the $¢$ symbol.

To keep track of these credits the proof maintains the following credit invariant: Any non-root node with $B − 1$ ...