1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.