Bagaimana caranya, dengan sekumpulan kunci yang telah ditentukan sebelumnya, menyusun ulang kunci sedemikian rupa sehingga jumlah minimum node yang digunakan saat memasukkan ke dalam B-Tree?

Algoritme di bawah ini seharusnya berfungsi untuk B-Trees dengan jumlah kunci minimum di node = d dan maksimum = 2*d. Saya kira ini dapat digeneralisasi untuk 2*d + 1 kunci maks jika cara memilih median diketahui.

Algoritma di bawah ini dirancang untuk meminimalkan jumlah node, bukan hanya tinggi pohon.

Metode ini didasarkan pada gagasan untuk meletakkan kunci ke dalam daun yang tidak penuh atau jika semua daun penuh untuk meletakkan kunci di bawah simpul tidak penuh yang paling bawah.

Lebih tepatnya, pohon yang dihasilkan oleh algoritma yang diusulkan memenuhi persyaratan berikut: Memiliki ketinggian minimum yang mungkin; Ia memiliki tidak lebih dari dua node nonfull pada setiap level. (Itu selalu merupakan dua simpul paling kanan.)

Karena kita tahu bahwa jumlah node pada level apa pun kecuali root sama dengan jumlah jumlah node dan total jumlah kunci pada level di atas, kita dapat membuktikan bahwa tidak ada penataan ulang node yang valid antar level yang mengurangi jumlah total node. Misalnya peningkatan jumlah kunci yang disisipkan di atas level tertentu akan menyebabkan peningkatan node pada level tersebut dan akibatnya meningkatkan jumlah total node. Meskipun upaya apa pun untuk mengurangi jumlah kunci di atas level tertentu akan menyebabkan penurunan jumlah node pada level tersebut dan gagal untuk menyesuaikan semua kunci pada level tersebut tanpa menambah tinggi pohon. Jelas juga bahwa susunan kunci pada level tertentu merupakan salah satu yang optimal. Dengan menggunakan alasan di atas, pembuktian yang lebih formal melalui induksi matematika juga dapat dibangun.

Idenya adalah untuk menyimpan daftar penghitung (ukuran daftar tidak lebih besar dari tinggi pohon) untuk melacak berapa banyak kunci yang ditambahkan pada setiap level. Setelah saya menambahkan kunci d ke level tertentu, itu berarti node terisi setengahnya dibuat di level itu dan jika ada cukup kunci untuk mengisi setengah lagi dari node ini, kita harus melewati kunci ini dan menambahkan root untuk level yang lebih tinggi. Dengan cara ini akar akan ditempatkan tepat di antara paruh pertama subpohon sebelumnya dan paruh pertama subpohon berikutnya, hal ini akan menyebabkan perpecahan, ketika akar akan menggantikan tempatnya dan dua paruh subpohon akan terpisah. Tempat untuk kunci yang dilewati akan aman saat kita melewati kunci yang lebih besar dan dapat diisi nanti.

Ini kode (semu) yang hampir berfungsi, array perlu diurutkan:

PushArray(BTree bTree, int d, key[] Array)
{
    List<int> counters = new List<int>{0};
    //skip list will contain numbers of nodes to skip 
    //after filling node of some order in half
    List<int> skip  = new List<int>();
    List<Pair<int,int>> skipList = List<Pair<int,int>>();

    int i = -1;
    while(true)
    {     
       int order = 0;
       while(counters[order] == d) order += 1;
       for(int j = order - 1; j >= 0; j--) counters[j] = 0;

       if (counters.Lenght <= order + 1) counters.Add(0);
       counters[order] += 1;

       if (skip.Count <= order)
              skip.Add(i + 2);    
       if (order > 0)
           skipList.Add({i,order}); //list of skipped parts that will be needed later
       i += skip[order];

       if (i > N) break;

       bTree.Push(Array[i]);
    }

    //now we need to add all skipped keys in correct order
    foreach(Pair<int,int> p in skipList)
    {
        for(int i = p.2; i > 0; i--)
            PushArray(bTree, d, Array.SubArray(p.1 + skip[i - 1], skip[i] -1))
    }
}

Contoh:

Berikut adalah bagaimana angka dan kunci penghitung yang sesuai harus diatur untuk d = 2 saat pertama kali melewati array. Saya menandai kunci yang dimasukkan ke dalam B-Tree selama lintasan pertama (sebelum loop dengan rekursi) dengan 'o' dan dilewati dengan 'x'.

                                                              24
        4         9             14             19                            29 
0 1 2 3   5 6 7 8   10 11 12 13    15 16 17 18    20 21 22 23    25 26 27 28    30 ...
o o x x o o o x x o  o  o  x  x  x  x  x  x  x  x  x  x  x  x  o  o  o  x  x  o  o ...
1 2     0 1 2     0  1  2                                      0  1  2        0  1 ...
0 0     1 1 1     2  2  2                                      0  0  0        1  1 ...
0 0     0 0 0     0  0  0                                      1  1  1        1  1 ...
skip[0] = 1 
skip[1] = 3 
skip[2] = 13

Karena kita tidak mengulangi kunci yang dilewati, kita memiliki kompleksitas waktu O(n) tanpa menambahkan ke B-Tree itu sendiri dan untuk array yang diurutkan;

Dalam formulir ini mungkin tidak jelas cara kerjanya ketika tidak ada cukup kunci untuk mengisi paruh kedua node setelah blok yang dilewati tetapi kita juga dapat menghindari melewatkan semua kunci lewati[order] jika total panjang array kurang dari ~ i + 2 * lewati[pesanan] dan lewati untuk kunci lewati[pesanan - 1] sebagai gantinya, string tersebut setelah mengubah penghitung tetapi sebelum mengubah variabel i mungkin ditambahkan:

while(order > 0 && i + 2*skip[order] > N) --order;

itu akan menjadi benar karena jika jumlah total kunci pada level saat ini kurang atau sama dengan 3*d, kunci tersebut masih dibagi dengan benar jika ditambahkan dalam urutan asli. Hal ini akan menyebabkan penataan ulang kunci yang sedikit berbeda antara dua node terakhir pada tingkat tertentu, namun tidak akan melanggar persyaratan yang dijelaskan, dan mungkin akan membuat perilaku lebih mudah dipahami.

Mungkin masuk akal untuk menemukan beberapa animasi dan melihat cara kerjanya, berikut adalah urutan yang harus dihasilkan pada rentang 0..29: 0 1 4 5 6 9 10 11 24 25 26 29 /akhir lintasan pertama< /em>/ 2 3 7 8 14 15 16 19 20 21 12 13 17 18 22 23 27 28