What is the minimal degree $d$ required for a B tree with $44*10^6 $ keys so that it's height is less than or equal to $5$

Question

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 ?

Answer 1

Having degree $d$ tree has $1$, $d$, $d^2$, $d^3$, $d^4$ nodes per level. So, we must have that:

$$1+d+d^2+d^3+d^4 \ge 44\ 000\ 000$$

Let's consider just $d^4 = 44\ 000\ 000$. This has solution $d\approx 81.4$ but real $d$ must be bigger because we threw away some summands. So, we need to try $82$:

$$1+82+82^2+82^3+82^4=45\ 770\ 351$$

And let as check $81$ just to be sure:

$1+81+81^2+81^3+81^4 = 43\ 584\ 805 < 44\ 000\ 000$

So, the answer is 82.

---

Ups, you are asking about B-tree, so having branching factor $d$ we have at most $2d-1$ keys inside a node. Then we have different equation:

$$(2d-1) + d(2d-1) + d^2(2d-1) + d^3(2d-1) + d^4(2d-1) \ge 44\ 000\ 000$$ $$2d + 2d^2 + 2d^3 + 2d^4 + 2d^5 - (1 + d + d^2 + d^3 + d^4) \ge 44\ 000\ 000$$ $$d + d^2 + d^3 +d^4 + 2d^5 - 1 \ge 44\ 000\ 000$$ Let's solve $2d^5 = 44\ 000\ 000$, $d \approx 29.4$, so we need to try both $29$ and $30$: $$29+29^2+29^3+29^4+2*29^5 = 41\ 754\ 838$$ So, we have to choose $30$, but lets check: $$30+30^2+30^3+30^4+2*30^5 = 49\ 437\ 930$$