Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

In what order should you insert a set of known keys into a B-Tree to get minimal height?

Tags:

People also ask

What is order of B-tree in data structure?

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.

What is the minimum number of keys for a B+ tree of height h and order M?

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?