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 $4leq 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=lceillog_3 1000rceil=7$ In the best case you will have 5 children per node, so your tree will be $h=lceillog_5 250rceil=4$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/31990
