A B+ tree can contain a maximum of 7 pointers in a node. What is the minimum number of keys in leaves?

Category: QuestionsA B+ tree can contain a maximum of 7 pointers in a node. What is the minimum number of keys in leaves?
Editor">Editor Staff asked 4 weeks ago

A B+ tree can contain a maximum of 7 pointers in a node. What is the minimum number of keys in leaves?
 
(a) 6
 
(b) 3
 
(c) 4
 
(d) 7
 
My question is based upon B-Trees in portion B-Trees of Data Structures & Algorithms I
 
This question was addressed to me during an internship interview.

1 Answers
Editor">Editor Staff answered 4 weeks ago

The correct option is (b) 3
 
The best explanation: Maximum number of pointers in a node is 7, i.e. the order of the B+ -tree is 7. In a  B+ tree of order n each leaf node contains at most n – 1 key and at least ⌈(n − 1)/2⌉ keys. Therefore, a minimum number of keys each leaf can have = ⌈(7 – 1)/2⌉ = 3.