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.



Your Answer

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

Browse other questions tagged or ask your own question.