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?

Solution 1

It really depends on how you define order. According to Knuth, the order of a b-tree is the maximum number of children, which would mean that the max answer is 129. If the definition of order is the minimum number of keys of a non-root node, then the answer to the max is unknown.

Using this definition, your calculation of minimum is correct, but your maximum is not, because every node, including the leaves, contains m-1 keys. This is also consistent with the definition of B-Tree in Cormen. if n is 16512, and each n stores 127 keys, the answer is definitely not 16511.

Solution 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

Solution 3

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