Analysis of B-Trees
This lesson is about amortized analysis of B-trees.
An estimate about -trees is that
- In the external memory model, the running time of
find(x)
,add(x)
, andremove(x)
in a B-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 shows that, so far, we have overestimated the number of merge and split operations performed by B-trees.
Lemma 1: Starting with an empty -tree and performing any sequence
of m 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 which
- each
split()
,merge()
, orborrow()
operation is paid for with two credits, i.e., a credit is removed each time one of these operations occurs; and - at most three credits are created during any
add(x)
orremove(x)
operation.
Since at most credits are ever created and each split, merge, and borrow is paid for with with two credits, it follows that at most ...