Data Structures, Algorithms, & Applications in C++
Chapter 15, Exercise 61
When the B-tree order is 2m, the worst-case
height is log m ((n+1)/2) + 1.
Since the retrieval of each node requires 2
disk accesses,
the maximum number of disk accesses required to preform a search
is 2 log m ((n+1)/2) + 2.
When the B-tree order is m, the worst-case
height is log d ((n+1)/2) + 1,
where d = ceil(m/2).
Since the retrieval of each node requires only 1 disk access,
the maximum number of disk accesses required to preform a search
is log d ((n+1)/2) + 1 =
log m ((n+1)/2) * (log m / log d) + 1.
Since (log m / log d) <= 2 for m
>= 3, as far as worst-case search complexity is concerned,
we are better off
using a B-tree of order m rather than one
of order 2m.