Comment on page

17.5 B-Tree Performance

B-Tree Runtime Analysis

To consider the runtime of B-Trees, let
LL
be the maximum items per node. Based on our invariants, the maximum height must be somewhere between
logL+1N\log_{L + 1} N
(best case, when all nodes have
LL
items) and
log2N\log_2 N
(worst case, when each node has 1 item).
The overall height, then, is always on the order of
Θ(logN)\Theta(\log N)
Worst-case B-Tree height
Best-case B-Tree height

Runtime for contains

In the worst case, we have to examine up to
LL
items per node. We know that height is logarithmic, so the runtime of contains is bounded by
O(LlogN)O(L \log N)
. Since
LL
is a constant, we can drop the multiplicative factor, resulting in a runtime of
O(logN)O(\log N)
.

Runtime for add

A similar analysis can be done for add, except we have to consider the case in which we must split a leaf node. Since the height of the tree is
O(logN)O(\log N)
, at worst, we do
logN\log N
split operations (cascading from the leaf to the root). This simply adds an additive factor of
logN\log N
to our runtime, which still results in an overall runtime of
O(logN)O(\log N)
.