Let us understand specification of $B^+$ tree first
For a non-root node
- Minimum number of keys $=d\implies$ minimum number of children $=d+1$
- Maximum number of keys $=2d\implies $ maximum number of children $=2d+1$
For a root node
- Minimum number of keys $=1$ so, minimum number of children $=2$
- Maximum number of keys $=2d$ so, maximum number of children $=2d+1$
Now, coming to our actual question
Part (A). For a given no of leaf node $(L\geq 2)$ what will be the total no of keys in internal nodes?
Will solve this in three ways:
1. Assuming maximum nodes at each level $$\begin{array}{|c|c|c|} \hline \text {Height} & \text {#nodes} & \text {#keys} \\\hline \text{0 }& \text{1} & \text{2d} \\\hline \text{1 }& \text{2d + 1} & \text{2d(2d + 1)} \\\hline \vdots & \vdots & \vdots \\\hline \text{h } & \text{${(2d + 1)}^h$} & \text{$2d[{(2d + 1)}^h]$} \\\hline \end{array}$$No. of leaf nodes $= {(2d +1 )}^ h=L$
Total no. of keys in internal nodes $= 2d +2d(2d+1)$$+2d(2d+1)^2 +\ldots+2d{(2d+1)}^{h-1}$
$\qquad \qquad= {(2d+1)}^h -1=L-1$
2. Assuming minimum nodes at each level$$\begin{array}{|c|c|c|} \hline \text {Height} & \text {#nodes} & \text {#keys} \\\hline \text{0 }& \text{1} & \text{1} \\\hline \text{1 }& \text{2} & \text{2d} \\\hline \vdots & \vdots & \vdots \\\hline \text{h } & \text{$2{(d + 1)}^{h-1}$} & \text{$2d[{(d + 1)}^{h-1}]$} \\\hline \end{array}$$So, no. of leaf nodes $=2{(d+1)}^{h-1} =L$
Total no of keys in internal nodes $=1+2d+2d(d+1)+\ldots+2d{(d+1)}^{h-2}$
$\qquad\qquad=2{(d+1)}^{h-1} -1 =L-1$
3. Whenever there is an overflow in a leaf node (or whenever no of leaf node increases by one), then we move a key in the internal node (or we can say, no of internal keys increases by one).
Now, let's start with the base case. Only $2$ leaf nodes (as given $L\geq 2$). So, no. of keys in root node $=1$ or $L-1.$
Once there is an overflow in a single leaf node then no of leaf nodes now would become $3$ and at the same the time we will have one more key in our root node.
Part (B) Maximum number of internal nodes in a $B+ $ tree of order $4$ with $52$ leaves?
Using Bulk loading approach, here we will use minimum fill factor ($d=4$ hence, min keys $=d =4$ and min children/block pointer $=d+1=5)$
So, we have $52$ leaves so and need total $52$ block pointers and one node should have minimum $5$ block pointers.
So, for $52$ leaves we require $\lfloor 52/5\rfloor = 10$ nodes
For $11$ block pointers we require $\lfloor 10/5\rfloor = 2$ nodes
For $2$ block pointers we require $1$ node "it is root node"
So, max no of internal nodes= $10+2+1= 13$ nodes
Part (C) Minimum number of leaves in a B+ tree of order $d$ and height $h(h≥1)$?
By part (A) "assuming minimum nodes at each level" case
Minimum no. of leaves $\bf{= 2 (d +1 )^{h-1}}$