What is the maximum number of keys that a B+ -tree of order 3 and of height 3 have?

Category: QuestionsWhat is the maximum number of keys that a B+ -tree of order 3 and of height 3 have?
Editor">Editor Staff asked 1 month ago

What is the maximum number of keys that a B+ -tree of order 3 and of height 3 have?
 
(a) 3
 
(b) 80
 
(c) 27
 
(d) 26
 
I’m obligated to ask this question of B-Trees topic in chapter B-Trees of Data Structures & Algorithms I
 
I got this question in a job interview.

1 Answers
Editor">Editor Staff answered 1 month ago

Correct option is (d) 26
 
To explain: A B+ tree of order n and height h can have at most n^h – 1 keys. Therefore maximum number of keys = 3^3 -1 = 27 -1 = 26.