1
$\begingroup$

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 ?

$\endgroup$
1
  • $\begingroup$ At least we got the same answer. $\endgroup$
    – Yola
    Sep 4, 2019 at 10:33

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.