The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 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)$?

asked in Databases by Veteran (59.6k points)
edited by | 3k views
Plz explain..

4 Answers

+19 votes
Best answer

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

answered by Boss (12.4k points)
edited by

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

@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 it should be 11 ....isn't it?/
Got it !

 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.


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

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

@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


i agree with your solution........

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

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.
+3 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

answered by Junior (783 points)
–1 vote
b 17

c (m-1)*n+1

where m is order n is total internal nodes
answered by Active (1.1k points)
please explain?
–1 vote

For b)

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

answered by Active (1.5k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,599 questions
48,598 answers
63,721 users