edited by
32,690 views
56 votes
56 votes

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$
edited by

8 Answers

2 votes
2 votes

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

1 votes
1 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)

Answer:

Related questions

12 votes
12 votes
5 answers
1
go_editor asked Sep 30, 2014
6,495 views
$25$ persons are in a room. $15$ of them play hockey, $17$ of them play football and $10$ of them play both hockey and football. Then the number of persons playing neithe...
7 votes
7 votes
1 answer
2
go_editor asked Sep 30, 2014
3,874 views
Choose the most appropriate word from the options given below to complete the following sentence:If we manage to __________ our natural resources, we would leave a better...
41 votes
41 votes
2 answers
4