CODEWITHSUNDEEP
data-structurestreeb-tree
user550413
user550413

Reputation: 4819

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?

Upvotes: 0

Views: 1376

Answers (1)

Pops
Pops

Reputation: 30828

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)

Upvotes: 3

Related Questions