The order of a B-tree is that maximum. A Binary Search Tree, for example, has an order of 2. The degree of a node is the number of children it has. So every node of a B-tree has a degree greater than or equal to zero and less than or equal to the order of the B-tree.
2. What is the MINIMUM number of KEYS in a B-Tree of order m of height h? a. In such a tree, the root would have only 2 children (1 key), since this is the minimum allowed for a root.
Given a fixed number of keys or values(stored either in array or in some data structure) and order of b-tree, can we determine the sequence of inserting keys that would generate a space efficient b-tree.
To illustrate, consider b-tree of order 3. Let the keys be {1,2,3,4,5,6,7}. Inserting elements into tree in the following order
for(int i=1 ;i<8; ++i) { tree.push(i); }
would create a tree like this
4 2 6 1 3 5 7
see http://en.wikipedia.org/wiki/B-tree
But inserting elements in this way
flag = true; for(int i=1,j=7; i<8; ++i,--j) { if(flag) { tree.push(i); flag = false; } else { tree.push(j); flag = true; } }
creates a tree like this
3 5 1 2 4 6 7
where we can see there is decrease in level.
So is there a particular way to determine sequence of insertion which would reduce space consumption?
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With