Comment on page
17.5 B-Tree Performance
To consider the runtime of B-Trees, let
be the maximum items per node. Based on our invariants, the maximum height must be somewhere between
(best case, when all nodes have
items) and
(worst case, when each node has 1 item).
The overall height, then, is always on the order of

Worst-case B-Tree height

Best-case B-Tree height
In the worst case, we have to examine up to
items per node. We know that height is logarithmic, so the runtime of
contains
is bounded by . Since
is a constant, we can drop the multiplicative factor, resulting in a runtime of
.
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 , at worst, we do
split operations (cascading from the leaf to the root). This simply adds an additive factor of
to our runtime, which still results in an overall runtime of
.
Last modified 9mo ago