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)

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).

Last updated