1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.