Wenn eine feste Anzahl von Schlüsseln oder Werten (entweder in einem Array oder in einer Datenstruktur gespeichert) und die Reihenfolge des B-Baums gegeben sind, können wir die Reihenfolge des Einfügens von Schlüsseln bestimmen, die einen platzsparenden B-Baum erzeugen würden.

Betrachten Sie zur Veranschaulichung den B-Baum der Ordnung 3. Die Schlüssel seien {1,2,3,4,5,6,7}. Einfügen von Elementen in den Baum in der folgenden Reihenfolge

for(int i=1 ;i<8; ++i)
{
 tree.push(i);  
}

würde einen Baum wie diesen schaffen

        4
     2      6
   1  3   5   7

sehenhttp://en.wikipedia.org/wiki/B-tree

Aber Elemente auf diese Weise einfügen

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;
    }   
}

schafft einen Baum wie diesen

    3 5
1 2  4  6 7

Wo wir sehen können, sinkt das Niveau.

Gibt es also eine bestimmte Möglichkeit, die Einfügefolge zu bestimmen, um den Platzbedarf zu senken?