# Maximum depth of a B+ tree

Given $K$...# key values, $n$...# pointers in a node.

I read somewhere, that the maximum depth is defined as $\lceil\log_{\lceil\frac{n}{2}\rceil}(K)\rceil$. However, it is not correct, as I can come up with a counterexample. When the tree is minimum filled, it won't work. E.g.:

This is a valid $B^+$-tree, the root has at least two childs, each inner node has at least $\lceil n/2 \rceil$ childs and each leaf has at least $\lceil \frac{n-1}{2}\rceil$ record. So, $n=3$ and $K=4$, then $\log_2(4) = 2$. Now, when you fill up the leafs: [1,1,2,2,3,3,4,4], then it is again a valid tree and $K=8$, hence $\log_2(8) = 3$, but same depth.

Notice: I am looking for a formula or explanation but for a $B^+$-tree not a $B$-tree. A source would be nice.

• Where did you read that? Can you give a citation? Can you check the surrounding context to see whether that's actually what it said? – D.W. Oct 4 '17 at 16:31

## 1 Answer

Since you're not sure where you read it, is it possible you are misremembering slightly what the result was?

In a B+ tree, we require that every node has between $n/2$ and $n$ children. In other words, every node is required to have at least $\lceil n/2 \rceil$ children. This means that any tree of depth $d$ where all leaves are at depth $d$ must have at least $\lceil n/2 \rceil^d$ leaf nodes. Thus, any such tree must have depth at most $\lceil \log_{\lceil n/2 \rceil} L \rceil$, where $L$ is the number of leaf nodes. Perhaps this is what you read.

Note that the number of key value is related to the number of leaf nodes: $\lceil b/2 \rceil -1 \le L/K \le b-1$. This would let you get a similar result in terms of $K$, for a full tree with all leaves at the same level.

Detail: Here I have ignored that the root is usually allowed to have as few as 2 children. This has only a small effect on the answer.

• I don't think this is true, look at my subsequent added counterexample above. – racc44 Oct 4 '17 at 8:20
• @racc44, You're right. I realize I had an error in my reasoning. See updated answer. – D.W. Oct 4 '17 at 16:31
• That makes sense! Can you explain why $L/K$ and would a formula be possible without $L$, since $K$ relates to $L$? – racc44 Oct 5 '17 at 11:30
• @racc44, that's because every leaf has between $\lceil b/2 \rceil -1$ and $b-1$ keys in it. See Wikipedia. – D.W. Oct 5 '17 at 17:48
• I can come up with another counterexample. Consider the same tree as above, so depth is 2 or 3 (according to whether you count it with or without the root), but assume that the root and the inner nodes have 3 pointers, hence we have 9 leaf nodes. The key values do not matter. Now with your formula the depth would be $\lceil \log_2(9) \rceil = 4$, but that is wrong. – racc44 Oct 6 '17 at 17:09