Search code examples
data-structurestreeb-tree

B+ Trees Insertion Order

How can the height of a B+ tree change in different insertion orders?

For example, given n values and 2 different insert orders. What is the maximum difference I can get between the heights of the 2 built trees?

Solution

  • The best-case height of a B+-tree (or any B-tree) is logmn. The worst-case height is logm/2n. (Per Wikipedia)

    The maximum difference you can get is worstCase - bestCase, which is logm/2n - logmn, which reduces to

    logmn ( 1 / (1 - logm2) - 1)

    (m represents the maximum number of children any one tree node can have)