Min/max height of B-tree

Problem Detail: 

I have a question asking for the minimum and maximum height $h$ of a B-Tree with 1000 elements under following conditions:

• each block can save 1 to 4 records,
• the number of internal nodes is between 3 and 5 and
• the root has between 3 and 5 children.

The solution is given as $4\leq h \leq7$. How this is reached?

Asked By : T. Jzmod

Answered By : user3100381

In the worst case you will store 1 record per node, so you will need 1000 nodes.

In the best case you will store 4 record per node, so you only need 1000/4 = 250 nodes.

In the worst case you will have 3 children per node, so your tree will only grow by multiples of 3 for each level. So we can say that $3^h \geq 1000$, where $h$ is the height. So $h=\lceil\log_3 1000\rceil=7$

In the best case you will have 5 children per node, so your tree will be $h=\lceil\log_5 250\rceil=4$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/31990