The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
5k views

Consider a $B^+$-tree in which the maximum number of keys in a node is $5$. What is the minimum number of keys in any non-root node?

  1. $1$
  2. $2$
  3. $3$
  4. $4$
asked in Databases by Veteran (101k points)
edited by | 5k views

7 Answers

+37 votes
Best answer
Answer: B

Order = $5$+$1$ = $6$
Minimum children in a non root node = $\lceil$ $\frac{Order}{2}$ $\rceil$ = $\lceil$ $\frac{6}{2}$ $\rceil$ = $3$
Keys = Minimum children in a non root node - $1$ = $2$
answered by Boss (34k points)
edited by
+24 votes
In a b+ tree if a non-root node can be a leaf-node or a non-leaf-node:

case 1) when a non-root, leaf node is full and a new key is inserted in it:

a) the initial keys in the row + the newly inserted key is arranged in asc/desc order

b) the medium key is copied to an upward node without the record pointer

c) the medium key is retained in the leaf node with the record pointer

d) the keys in the leaf node are split in half and moved to two separate nodes

here there are maximum 5 keys, so when an additional key comes, the medium key is copied upwards, and a total of 6 keys are split in two nodes having 3 keys each.

case 2) when a non-root, non-leaf node is full and a new key is inserted in it:

a) the initial keys in the row + the newly inserted key is arranged in asc/desc order

b) the medium key is moved to an upward node

c) the medium key is removed from the current node

d) the keys in the current node are split in half and moved to two separate nodes

here there are maximum 5 keys, so when an additional key comes, the medium key is moved upwards, and a total of 5 remaining keys are split in two nodes having 2 keys and 3 keys respectively.

 

SO the minimum number of keys in a non-root leaf node is 3 and the minimum number of keys in a non-root non-leaf node is 2.

SO the minimum number of keys in a non-root node is 2.

Hence answer is (B)
answered by Active (3.8k points)
0
good job

thank you
0
Perfect explanation.
0
nice explanation.
+2 votes

Ans: B

order= maximum no of children = maximum number of keys + 1

                                                  = 5+1 = 6

degree, t= order/2 = 6/2= 3

max key = (2t-1) = 2*3-1=5

min key = t-1=3-1=2

answered by Loyal (7.3k points)
+1 vote

Maximum number of keys in B+ tree -> leaf node having 5 keys

order of leaf = number of key+record pointer value

order of non leaf = number of block pointers

If not given in question explicitly then 

O (leaf) = O(non leaf)

since O(leaf) = 5

max number of block pointer in nonleaf = 5

therefore minimum number of keys will be in non leaf = ceil(5/2)-1 = 3-1 = 2

Answer B

answered by Active (1.9k points)
0 votes

Given maximum number of keys in any node is 5 ...

So Order of non-leaf node(maximum number of children) is 5+1 = 6

Order of leaf node(maximum number of keys) = 5 which is given in question...

Minimum number of keys possible in any non-leaf node = [ ceil (order_of_nonleaf_node) / 2 ] - 1 = 2

Minimum number of keys possible in any leaf node =  [ ceil (order_of_leaf_node) / 2 ] = 3 

So minimum number of nodes possible in the B+ tree = min (2,3) = 2

(we have ignored the special case of root as per question which can even have 1 key, EX :when our data file has only one record)

answered by Loyal (7.3k points)
0
can u show me the resources where they mentioned this method ??
0
@PujaMishra Ankur Gupta OS notes (Refer last pages).
0 votes
answered by Loyal (8.9k points)
0 votes

This can be perceived by below diagram.

answered by Loyal (8.9k points)


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

39,530 questions
46,674 answers
139,829 comments
57,598 users