What is the minimal degree $d$ required so a B - tree with $44*10^6$ keys will have a height $h$, such that $h\leq 5$
My attempt was to build the tallest tree possible with minimum degree $d$ and $n = 44,000,000$ keys and then solve for $d$. That would mean any other tree with a minimal degree $d'$ such that $d'\geq d$ and $n$ keys will be shorter than the one I built:
at depth 0 , we have the root and that's $1$ node
at depth 1, we got exactly $2$ nodes
at depth 2, since we're going for the tallest tree each node will have a minimal number of keys so $d-1$ keys each, that means $d$ children each so a total of $2d$ nodes.
at depth 3, following the same reasoning , $2d^2$ nodes.
...
at depth $h$, there are $2d^{h-1}$ nodes
total number of keys is :
$n = 1+ (d-1)\sum_{k=0}^{h-1} {2d^k} = 1 + (d-1) \frac{2(d^h-1)}{d-1} = 2d^h-1 = 44*10^6 $
so:
$2d^5-1=44,000,000 $
$d= 29.4 $
$d\geq 30$
is that even correct ?