Wiem, że jest ładowanie zbiorcze w drzewie b +. Chciałem tylko wiedzieć, czy istnieje algorytm ładowania zbiorczego w B-Tree. Na przykład, podając tablicę danych, jaki jest najlepszy sposób tworzenia B-Tree?Czy istnieje algorytm ładowania zbiorczego w drzewie B?
Właściwie Odpowiedź brzmi: tak.
Główna różnica między znakami B + i zwykłymi drzewami B polega na tym, że wartości są faktycznie zapisywane w liściach dla pierwszych, podczas gdy w późniejszych wartościach są wartości w każdym węźle. Stąd też tony B + umożliwiają przechowywanie danych w niemal ciągły sposób, przy czym każdy liść zawiera ciągły kawałek całości posortowanych danych. Nie może to być prawda w przypadku drzewek B: wewnętrzny węzeł będzie zawierał kilka elementów, ale nie będą one przylegać do siebie. cały posortowany zbiór danych.
Ta właściwość ma podstawowe znaczenie przy ładowaniu zbiorczym: ten proces działa na już posortowanym zbiorze danych, wycinając go w tablice, które utworzą liście z drzewa B +. Tak więc dla drzewa B wygląda na to, że nie może działać.
Jeśli możemy posortować dane w sposób, który grupuje elementy wewnętrznych węzłów, problem zostanie rozwiązany. Aby to zrobić, trzeba z góry wiedzieć, jak elementy zostaną pogrupowane. Okazuje się to możliwe.
Zadzwońmy pod numer o (kolejność) minimalnej liczby dzieci w węźle (zgodnej z pierwotną definicją kolejności drzewa B). Uważamy, że węzeł główny znajduje się na najwyższym stopniu drzewa, a liście są najniższe (etap 0). Dla dobrze zbalansowanego drzewa wszystkie liście będą rzeczywiście na tym samym etapie.
Etap k elementów grup drzew rozmieszczonych co najmniej na elementach k-1 w co najmniej pozycji o. Po początkowym sortowaniu, musimy wyodrębnić elementy z posortowanej tablicy, która stanowi etap 0, i pogrupować je w inną tablicę, aby zbudować stage 1, a następnie zrobić to ponownie z tą tablicą do nowej tablicy dla etapu 2 i powtórzyć proces dopóki nie będzie mniej niżelementów w najnowszej tablicy, która będzie podstawowym etapem. Od tego momentu możliwe jest zbudowanie drzewa bezpośrednio od scenografii:
o elementówWynikowe drzewo niekoniecznie będzie dobrze zrównoważone. To zależy od liczby wpisów w zbiorze danych i od o. Powinno być możliwe dostrojenie interwału używanego do budowy etapów, aby mieć lepiej rozłożone drzewo.
W sumie praca potrzebna do masowego załadowania drzewa B jest bardziej żmudna niż w przypadku B +, ale jest to możliwe.