Comment on page

# 17.5 B-Tree Performance

To consider the runtime of B-Trees, let

$L$

be the maximum items per node. Based on our invariants, the maximum height must be somewhere between $\log_{L + 1} N$

(best case, when all nodes have $L$

items) and $\log_2 N$

(worst case, when each node has 1 item). The overall height, then, is always on the order of

$\Theta(\log N)$

Worst-case B-Tree height

Best-case B-Tree height

In the worst case, we have to examine up to

$L$

items per node. We know that height is logarithmic, so the runtime of `contains`

is bounded by $O(L \log N)$

. Since $L$

is a constant, we can drop the multiplicative factor, resulting in a runtime of $O(\log N)$

.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(\log N)$

, at worst, we do $\log N$

split operations (cascading from the leaf to the root). This simply adds an additive factor of $\log N$

to our runtime, which still results in an overall runtime of $O(\log N)$

.Last modified 9mo ago