Max and min number of keys in a B-tree

Question

What is the maximum and minimum number of keys that can be stored in a B-tree of order 128 and height 3?

For the maximum, here's what I did: You have a single root node. The maximum children a root node can have is m (order), so that's 128. And each of those 128 children have 128 children, so that gives us a total of 1+128+16384=16512 total nodes. According to Wikipedia, a B-tree of n nodes can store n-1 keys, so that leaves us with a maximum of 16511 keys.

For min: You have a single root node, and the minimum number of children this can have is 2, and the minimum number of children these 2 children can have are m/2, where m is the order, so 64 children each. That leaves us with 1+2+64+64=131 total children and 131-1=130 keys.

Is what I have done here correct?

Answer 1

according to wikipedia , a node can have at most n-1 keys if it has n child nodes. therefore ,

                           root [127keys]
                 128 childnodes [each having 127 keys]
             128*128 childnodes [each having 127 keys]

127+128*127+128*128*127 = total no of maximum allowed keys

Answer 2

There are lower and upper bounds on the number of keys a node can contain. These bounds are expressed in terms of a fixed integer t >= 2 called the minimum degree of the B-tree.

• Every node other than the root must have at least t - 1 keys. Every internal node other than the root has at least t children. If the tree is nonempty, the root must have at least one key.

• Every node can contain at most 2t - 1 keys. Therefore, an internal node can have at most 2t children. We say that a node is full if it contains exactly 2t - 1 keys.

Max no of keys for height 3 = (2t-1) + (2t-1) * 2t + (2t-1) * 2t * 2t
Min no of keys for height 3 = (t-1) + (t-1)*t + (t-1) * t * t