thank you

The Gateway to Computer Science Excellence

+47 votes

Best answer

+37 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)

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)

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

+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**

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)

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,644 questions

56,505 answers

195,555 comments

101,055 users