3.5k views

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 | 3.5k views
0
Plz explain..
0
Is any shortcut equation available?

Let us understand specification of B+ tree first
For a non-root node

•  min no. of keys $=d\implies$ minimum no. of children $=d+1$
•  max no of keys $=2d\implies$ maximum no of children $=2d+1$

For a root node

•   min no. of keys $=1$ so, minimum no. of children $=2$
•   max no. of keys $=2d$ so, maximum no. 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 max nodes at each level

 height nodes keys $0$ $1$ $2d$ $1$ $2d+1$ $2d (2d +1)$ $\vdots$ $\vdots$ $\vdots$ $h$ ${(2d +1 )}^h$ $2d [ {(2d +1)} ^h ]$

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 min nodes at each level

 height nodes keys $0$ $1$ $1$ $1$ $2$ $2d$ $\vdots$ $\vdots$ $\vdots$ $h$ $2{(d +1 )}^ h$ $2d [ {(d +1)} ^h ]$

So, no. of leaf nodes $=2{(d+1)}^h =L$
Total no of keys in internal nodes $=1+2d+2d(d+1)+\ldots+2d{(d+1)}^{h-1}$
$\qquad\qquad=2{(d+1)}^{h} -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
+1

i found some mistakes in above (correct if they are indeed)

part a) assuming max nodes at each level

nodes at height h will be $(2d+1)^{h}$ and keys will be $2d*(2d+1)^{h}$, not )h-1). just put small values for h and find it out.

part b) leaves can contain 4 children(block pointers), out of which rightmost 1 is sibling node pointer, so actual number of elements it can contain is 3. so number of leaf nodes: $\left \lceil \frac{52}{3} \right \rceil$ = 18

now, each internal node has order 4 -> the number of children (tree pointers) that is it contains 4 keys. so on level 2 number of internal nodes are :  $\left \lceil \frac{18}{4} \right \rceil$ = 5

on next level: $\left \lceil \frac{5}{4} \right \rceil$ = 2

and finally to accomodate 2 keys we need 1 root node.

so total number of internal nodes are: 5+2+1 = 8

0
@Bikram why floor it shouldn't ceiling ..

52/5 =10 and remainder 2 so 2 nodes to be stored...if we take 10 so 2 nodes losts ...so it should be 11 ....isn't it?/
0
Got it !
+11

The maximum number of internal nodes in a B+  tree of order 4 with 52 leaves ??

This order 4 is the least value for each node except root. Each node can store at most 8 keys.

To find the maximum internal order of node should be 4 i.e. no of keys so the pointer is 5.

52/5 =10 and 2 is remainder

now we need to store 2 nodes for that if we want to add another node that is not possible because each node requires at least 4 keys. So these 2 nodes can be distributed among the 10 nodes.

so here we can take floor value for division purpose.

Let me twist the question:

The minimum number of internal nodes in a B+  tree of order 2 with 51 leaves ??

what you can do ??

for the minimum value, we have to take order =2d +1 =5

52 / 5 = 10 and 1 is remainder

But here can you distribute 1, among 10 nodes?? No, not possible since in each of 10 nodes there is no space for extra key value.

So we can create one extra node with 1 key value, but least value must be 2. In this case, we can distribute keys from 10 nodes to newly created extra node.

so here we need to take Ceiling.

+1

@saurabh rai sir i think there is something wrong in (2.  assuming min nodes at each level) part bcoz min nodes should be 2(d+1)^(h-1) and min keys should be 2d(d+1)^(h-1).

0
min node in a) part .. floor(p/2) -1 =d . so p = 2d ??
+2

@Saurabh-in (a) part second subpart

assuming min nodes at each level,

shouldn't number of leaves be 2(d+1)h-1  ?

because if we consider height as 1(which is just below root) so it should contain only 2 leaves considering min nodes as root can have min 1 key so min 2 child pointers and hence only 2 min leaves at height 1.

so at h=1, this should evaluate to 2.

And so similarly ans to (c) part must be 2(d+1)h-2

0

but my doubt is how it is possible

A  B+ - tree of order d is a tree in which each internal node has between d and 2d key.....  this line confuse me.... i think this should be ( ciel( d/2) -1)  to (d-1) keys in internal node...

+3
For part(B): Given 52 leaves so there are 51 keys in internal nodes.

Maximum number of internal nodes will be $\left \lceil \frac{51}{4} \right \rceil$ (to get maximum internal nodes fill nodes with minimum keys which is 4 here

ie, 13 internal nodes.

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

+1 vote

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.

–1 vote
b 17

c (m-1)*n+1

where m is order n is total internal nodes
0
–1 vote

For b)

If node occupancy is minimum, then no of nodes are maximum and vice- versa. Now refer below link.

http://www.techtud.com/doubt/b-tree

1
2