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.

  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Oct 4 '17 at 16:31

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.

  • $\begingroup$ I don't think this is true, look at my subsequent added counterexample above. $\endgroup$ – racc44 Oct 4 '17 at 8:20
  • $\begingroup$ @racc44, You're right. I realize I had an error in my reasoning. See updated answer. $\endgroup$ – D.W. Oct 4 '17 at 16:31
  • $\begingroup$ That makes sense! Can you explain why $L/K$ and would a formula be possible without $L$, since $K$ relates to $L$? $\endgroup$ – racc44 Oct 5 '17 at 11:30
  • $\begingroup$ @racc44, that's because every leaf has between $\lceil b/2 \rceil -1$ and $b-1$ keys in it. See Wikipedia. $\endgroup$ – D.W. Oct 5 '17 at 17:48
  • $\begingroup$ 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. $\endgroup$ – racc44 Oct 6 '17 at 17:09

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.