Max and min number of keys in a B-tree

Snowman picture Snowman · Apr 5, 2011 · Viewed 44.9k times · Source

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

Sukantu Barman picture Sukantu Barman · Jul 11, 2011

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