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$
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 &lt; 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$$