GATE CSE 1999 | Question: 21

Question

Consider a B-tree with degree $m$, that is, the number of children, $c$, of any internal node (except the root) is such that $m \leq c \leq 2m-1$. Derive the maximum and minimum number of records in the leaf nodes for such a B-tree with height $h, h \geq 1. ($Assume that the root of a tree is at height $0).$

Comments

For maximum no of records in leaf node-

Root can have a max of m child Thus at h=1 no of leaf nodes would be m

 Each of internal node can have a maximum of 2*m-1 child thus for h=2 no of leaf nodes would be m*(2m-1)

For h=3 max no of leaf nodes=m*((2m-1)^2)

So for a general expression max no of leaf nodes =m *((2m-1)^h-1)

Please correct me if i am wrong...

---

How is it possible for a node of B-Tree to have a children more than m?

---

A​nswer I am getting is -

        minimum records in leaf nodes  =  2 * (m) ^{h - 1} * (m-1)

        maximum records in leaf nodes =  (2m-1)^h * (2m-2)

---

@monanshi

Degree of B tree: Minimum number of children a B tree node should have

Order: Maximum number of children a B tree node can have.

The question is saying that the B tree has degree m. So max children is 2m-1

Answer 1

Given a $B$ tree :

• max children at a node $: 2m - 1 \implies$  max keys : $2m -2$
• min children at a node $:  m \implies$ min keys :   $m -1$

---

At Root node :   min keys $: 1 \implies $ min children $: 2$

Here, leaf level is at level $\bf{h}$ (because root is at level $\bf{0}$)

Now, we have to find

1. Minimum keys at leaf level(complete bottommost level, not just a node ) -  
   • For this, we have to consider minimum everywhere.
   • Firstly we will count the minimum possible nodes at the leaf level.
   • At Root Node (level $\bf{0}$) : It can have minimum $2$ child (mean $2$ nodes minimum for next level)
   • At level 1: It has $2$ nodes, each can have a minimum of $m$ child (so, this gives  $2 \ast m$  minimum possible nodes at next level )
   • At level $2:$ min $2 \ast m^2$  Child and so on.
   • At level $(h-1)$ $: 2 \ast (m)^{h-1}$   child (these are min number of leaf nodes possible )
   • At level $h$(leaf level) $:  2 \ast (m)^{h-1}$  nodes each having minimum $(m-1)$ keys. So, this gives the answer as  $\bf{2 \ast (m)^{h-1} \ast (m-1)}$ minimum keys possible at leaf level.                             

2.  Maximum keys at leaf level(complete bottommost level, not just a node ) -   
   •  For this, we have to count max everywhere.
   • At root (level 0) : max child possible  $2m-1$   (nodes for next level)
   • At level $1$ $:  2m-1$ nodes give  $(2m-1)^2$  child
   • At level $(h-1)$ $: (2m-1)^h$  child (these are maximum possible nodes at leaf level)
   • At level $h$ (leaf level) $: (2m-1)^h$  nodes  each having a maximum of $(2m-2)$ keys. Giving a total of - $\bf{(2m-1)^h * (2m-2) } $  maximum keys at leaf level. 

Comments

When the question already says "Consider a B-tree with degree m, that is, the number of children, c, of any internal note (except the root) is such that m≤c≤2m−1. "

I want to downvote this answer, because the answer assumes same degree for the root node for the maximum case, it doesn't make sense. if you don't agree please explain why it's correct.

---

@Satbir @chirudeepnamini @`JEET

What do you suggest.

Height	Nodes	Min $B_{p}$	Min keys
0	1	2	1
1	2	2m	2(m-1)
2	2m	$2m^2$	2m(m-1)
3	$2m^2$	$2m^3$	$2m^2$(m-1)
.	.	.	.
h	$2m^{h-1}$	---	$2m^{h-1}$(m-1)

Height	Nodes	Max $B_{p}$	Max keys
0	1	2	1
1	2	2(2m-1)	2(2m-2)
2	2(2m-1)	2$(2m-1)^2$	2(2m-1)(2m-2)
3	2$(2m-1)^2$	2$(2m-1)^3$	2$(2m-1)^2$(2m-2)
.	.	.	.
h	2$(2m-1)^{h-1}$	---	2$(2m-1)^{h-1}$(2m-2)

---

I think for Max this might be the table. As for Maximum no information for root node is given, so considering this might be valid. 

---

@Kushagra गुप्ता

Height	Nodes	Min $B_{p}$	Min keys
0	1	2	1
1	2	2m	2(m-1)
2	2m	$2m^2$	2m(m-1)
3	$2m^2$	$2m^3$	$2m^2$(m-1)
.	.	.	.
h	$2m^{h-1}$	---	$2m^{h-1}$(m-1)

This is correct. Put minimum keys everywhere. 

---

For maximum, At root node, you can put maximum $2m-2$ keys Or $2m-1$ Pointers. This will give you maximum possibility.  

So, this will be correct for maximum possibility. 

Height	Nodes	Max $B_{p}$	Max keys
0	1	2m-1	2m-2
1	2m-1	(2m-1)(2m-1)	(2m-1)(2m-2)
2	(2m-1)(2m-1)	(2m-1)$(2m-1)^2$	(2m-1)(2m-1)(2m-2)
3	$(2m-1)^3$	$(2m-1)^4$	$(2m-1)^3$(2m-2)
.	.	.	.
h	$(2m-1)^{h}$	---	$(2m-1)^{h}$(2m-2)

---

 

Answer 2

as per me -

 

for max records- max no of leaf nodes and max no of records per node -

so ( 2m-1 )^h * (2m-2)

 

for min nodes- min no fo leaf nodes * min no of records per node

 

for min nodes - all nodes at height h-1 and just 1 node at height h

so ( m^(h-1) -1 +1 ) * ( m -1) = m^(h-1) * (m-1)

 

Any mistake in this?