edited by
14,842 views
42 votes
42 votes

A $B^+$ - tree of order $d$ is a tree in which each internal node has between $d$ and $2 d$ key values. An internal node with $M$ key values has $M + 1$ children. The root (if it is an internal node) has between $1$ and $2d$ key values. The distance of a node from the root is the length of the path from the root to the node. All leaves are at the same distance from the root. The height of the tree is the distance of a leaf from the root.

  1. What is the total number of key values in the internal nodes of a $B^+$-tree with $l$ leaves ($l\geq 2$)?

  2. What is the maximum number of internal nodes in a $B^+$ - tree of order $4$ with $52$ leaves?

  3. What is the minimum number of leaves in a $B^+$-tree of order $d$ and height $h(h\geq 1)$?

edited by

5 Answers

Best answer
56 votes
56 votes

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

edited by
7 votes
7 votes

Part B) 
Given: d = 4 and leaves =52.
Min and Max keys for root  node = 1 and 2d. Therefore, min and max children for root node = (1+1) and (2d + 1) = 2 and 9 respectively.
Min and Max keys for non-root nodes = d and 2d. Therefore, min and max children for non-root node = (d+1) and (2d+1) = 5 and 9 respectively.

To solve this question, we can start from the leaf nodes and then move up. We have 52 leaf nodes.
▭=> ▭ => ▭=> ▭=> ........................=>▭  (52 leaves)
Now, nodes at level 3 should point to these 52 leaf nodes. Since we want to maximum internal nodes, for that to happen each node at level 3 should point minimum leaf nodes possible. Since minimum children a non-root node can have is 5. So, each node at the level 3 should point to 5 leaf nodes. Therefore, number of nodes at level 3 = (52 / 5) = 10.4. or in other words 10 and remainder 2. So 10 nodes at level 3 can point to 50 leaf nodes. Still, 2 leaf nodes are left. Now, we can't have an 11th node at level 3 because it will have 2 children and minimum children for non-root node is 5. But, we can make the last node at level 3 have another 2 children that will make total children for the last node at level 3 as 7, still less than maximum possible children for non-root node which is 9. So, maximum possible nodes at level 3 is 10.
Now, move to level 2, since we have 10 nodes at level 3 and we want maximum possible nodes at level 2, for that each node at level 2 should point to minimum possible nodes at level 3. Since minimum children for non-root node is 5. So, number of nodes at level 2 = (10/5) = 2. So, 2 nodes at level 2 will point to 10 nodes at level 3, with each node pointing to 5 nodes at level 3. So, the maximum possible nodes at level 2 is 2.
Now, finally at the root level, one root node will point to 2 nodes at level 1, and since minimum children for root node is 2, so no constraint is violated.
Therefore, total number of internal nodes = 1 + 2 + 10 = 13.


For maximizing internal nodes, each internal node should point minimum possible nodes at next level, if it points to maximum possible nodes then we would get minimum possible internal nodes. For level 3 then it would have been 52/9 = 5.77 which is less than 10.2.

 

 

 

 

 

4 votes
4 votes

for part  a) 

assuming max nodes at each level 

height nodes keys
0  1   2d
1 2d+1   2d (2d +1) 
...  .... ...
h-1 (2d +1 )^ (h-1) .2d [ (2d +1) ^(h-1) ]

(2d +1 ) ^h  = L thus => h =log L / log (2d+1 )

using GP 

total keys in internal nodes  ( 2d + 1 ) ^h -1   ie L-1

0 votes
0 votes

Answer to part B)

We are given that,

for internal nodes, 

  Min Max
keys d 2d
children d+1 2d+1

For this question, order = d = 4 and leaves = L = 52.

For maximum internal nodes, children of internal nodes should be minimum.

minimum children = d+1 = 4+1 = 5.

Since, B-Trees/B+ Trees are generalization of BSTs, So, We can have the following relation.

For n-ary Search Tree having I internal nodes, no. of leaves is given by $L = I(n-1)+1$

putting values, $52=I(5-1)+1   => I=ceil(51/4) = ceil(12.75)=13$

Thus, maximum number of Internal nodes = 13.

 

Related questions