Consider a B-tree that has minimum degree t and height h (note that the root is at level 0 and the leaves are at level h). Then

The number of children of a node are

0 for leaves

at least 2 and at most 2t for the root

at least t and at most 2t for internal nodes except the root.

The number of keys in a node are

at least 1 and at most 2t-1 for the root

at least t-1 and at most 2t-1 for nodes other than the root.

For the following questions, give your answer in a closed form expression:

(a) What is the minimum number of keys that can be stored in the B-tree

(b) What is the maximum number of keys that can be stored in the B-tree