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?
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