Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top