Slide 15.5: B-tree worst-case search depth

B-tree Worst-case Search Depth

Note that every key appears in the leaf level of a B-tree. Analyzing the worst-case search is the same as finding the worst depth of the tree. The worst case occurs when every page of the tree has the minimum number of descendants. For an order m B-tree, the following observations are given:

The minimum number of descendants from the root page is 2.
Therefore, the second level of the tree contains only 2 pages. Each of these pages, in turn, has at least ⌈m/2⌉ descendants.
The third level, then, contains 2×⌈m/2⌉. Each of these pages, once again, has a minimum ⌈m/2⌉ descendants.

Therefore, the general pattern of the relation between depth and the minimum number of descendants takes the form on the right:

Level	Minimum Number of Descendants
1 (root)	2
2	2×⌈m/2⌉
3	2×⌈m/2⌉×⌈m/2⌉
4	2×⌈m/2⌉³
…	…
d	2×⌈m/2⌉^d-1

For an order m B-tree with N keys in its leaves, we can express the relationship between keys and the minimum height d as:

N ≥ 2 × ⌈m/2⌉^d-1

Solving for d, we arrive at the following expression:

d ≤ 1 + log_⌈m/2⌉(N/2)

For example, a tree of 1000000 keys and order of 512, we find that

d ≤ 1 + log_⌈512/2⌉(1000000/2) = 3.37

That is, the B-tree has a depth of no more than 3 levels