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$

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 ?

• At least we got the same answer. – Yola Sep 4 '19 at 10:33

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$$

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$$