Analysis of B-Trees
This lesson is about analysis of the B-trees.
So far, we’ve established that:
- In the external memory model, the running time of
find(x)
,add(x)
, andremove(x)
in a -tree is . - In the word-RAM model, the running time of
find(x)
is , and the running time ofadd(x)
andremove(x)
is .
The following lemma, however, shows that we have overestimated the number of merge and split operations performed by -trees.
Lemma 1: Starting with an empty -tree and performing any sequence
of add(x)
and remove(x)
operations results in at most splits, merges,
and borrows being performed.
Proof: The proof of this has already been sketched for the special case in which . The lemma can be proven using a credit scheme, in ...