Analysis of B-Trees

This lesson is about analysis of the B-trees.

We'll cover the following...

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 BB-tree is O(logBn)O(\log_Bn).
  2. In the word-RAM model, the running time of find(x) is O(logn)O(\log n), and the running time of add(x) and remove(x) is O(Blogn)O(B\log n).

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

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

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