I came across this paper (page 16) which explains how to calculate the size of B+ trees.

According to it the maximum number of nodes at level $i$ is $2(n/2)^{i-1}$ for a B+ tree of order $n$. Thus a B+ tree of $l$ levels will contain at most $\sum_{i=0}^{l} 2(n/2)^{i-1}$ nodes (*).

But we also know that for example for a B+ tree which stores $N$ records there're at most $\frac{N}{\lceil n/2 \rceil-1}$ leaves (**).

The height of a B+ tree can be calculated by this formula: $\lceil \log_{\lceil n/2 \rceil}N \rceil$.

But then the formulas * and ** contradict each other. For example a B+ tree has $1024$ records and is of order $16$. The depth of the tree will be $4$.

According to ** there're at most $146$ leaves in the tree.

But according to * there're at most $2\cdot 8^3=1024$ nodes at level $4$ which is where the leaves are.

Please help me understand where this contradiction is coming from and what is the correct way to calculate the max size of B+ tree.


1 Answer 1

  1. Compute the size of nodes A, B of the following tree enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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