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

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.