What is the best case height of a B-tree of order n and which has k keys?

Category: QuestionsWhat is the best case height of a B-tree of order n and which has k keys?
Editor">Editor Staff asked 4 weeks ago

What is the best case height of a B-tree of order n and which has k keys?
 
(a) logn (k+1) – 1
 
(b) nk
 
(c) logk (n+1) – 1
 
(d) klogn
 
The origin of the question is B-Trees topic in portion B-Trees of Data Structures & Algorithms I
 
This question was addressed to me in my homework.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Right choice is (a) logn (k+1) – 1
 
Easiest explanation – B-tree of order n and with height k has best case height h, where h = logn (k+1) – 1. The best case occurs when all the nodes are completely filled with keys.