3k 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 | 3k views
0
Plz explain..

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 ??
+1

@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...

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