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