B-drzewo - słownik na dysku
Drzewa BST, nawet w takich jak opisane powyżej wersjach zrównoważonych, nie najlepiej nadają się do przechowywania na dysku komputera. Specyfika pamięci dyskowej polega na tym, że czas dostępu do niej jest znacznie (o kilka rzędów wielkości) dłuższy niż do pamięci wewnętrznej (RAM), a odczytu i zapisu danych dokonuje się większymi porcjami (zwanymi blokami lub stronami). Chaotyczne rozmieszczenie węzłów drzewa BST na dysku bez brania pod uwagę struktury tego rodzaju pamięci prowadzi do większej niż to naprawdę konieczne liczby dostępów.
Wynalezione na początku lat sześćdziesiątych XX wieku przez Bayera i MacCreighta [BM] B-drzewa to drzewa poszukiwań wyższych rzędów. W węźle drzewa BST mamy dwa wskaźniki do lewego i prawego syna i jeden klucz, który rozdziela wartości przechowywane w lewym i prawym poddrzewie. W węźle drzewa poszukiwań rzędu \( l \) jest \( l \) wskaźników do synów \( p_1, p_2, \ldots, p_l \) oraz \( l-1 \) kluczy \( k_1 < k_2 < \ldots < k_{l-1} \), które rozdzielają elementy poszczególnych poddrzew: wartości w poddrzewie wskazywanym przez \( p_i \) muszą mieścić się w przedziale otwartym \( (k_{i-1}..k_i) \) dla \( 1\le i\le j \) (przyjmując, że \( k_0 = -\infty \) oraz \( k_l = \infty \)). Rozmiar węzła w B-drzewie dobiera się zwykle tak, aby możliwie dokładnie wypełniał on stronę na dysku - pojedynczy węzeł może zawierać nawet kilka tysięcy kluczy i wskaźników. Zachowanie zrównoważenia umożliwione jest dzięki zmiennemu stopniowi wypełnienia węzłów. Dokładna definicja B-drzewa rzędu \( m \) (\( m\ge 3 \)) jest następująca:
(1) Korzeń jest liściem, albo ma od 2 do \( m \) synów.
(2) Wszystkie liście są na tym samym poziomie.
(3) Każdy węzeł wewnętrzny oprócz korzenia ma od \( \lceil m/2\rceil \) do \( m \) synów. Węzeł mający \( l \) synów zawiera \( l-1 \) kluczy.
(4) Każdy liść zawiera od \( \lceil m/2\rceil-1 \) do \( m-1 \) kluczy.
Warunki (3) i (4) gwarantują wykorzystanie przestrzeni dysku przynajmniej w ok. \( 50\% \), a warunek (2) - niewielką wysokość drzewa (w najgorszym razie ok. \( \log_{m/2} n/(m/2) \), a w najlepszym ok. \( \log_m n/m \) dla drzewa zawierającego \( n \) kluczy). Ponieważ, jak się zaraz przekonamy, koszt operacji słownikowych na B-drzewach jest co najwyżej proporcjonalny do wysokości drzewa, oznacza to na przykład, że dla \( m = 101 \) możemy znaleźć jeden spośród miliona kluczy w drzewie przy pomocy trzech odwołań do węzłów.
Oto przykładowe B-drzewo rzędu 3, zwane też 2-3 drzewem (1-2 klucze i 2-3 synów w węźle):
Operacja Find w B-drzewie jest analogiczna jak w drzewach BST. Poszukiwanie klucza \( x \) rozpoczynamy od korzenia. W aktualnym węźle zawierającym klucze \( k_1 < k_2 < \ldots < k_{l-1} \) szukamy klucza \( x \) (sekwencyjnie lub binarnie). Jeśli to poszukiwanie kończy się niepowodzeniem, to albo - jeśli aktualny węzeł jest liściem - klucza \( x \) w ogóle nie ma w drzewie, albo, mając wyznaczony indeks \( i \) o tej własności, że \( k_{i-1} < x < k_i \) (przy założeniu, że \( k_0 = -\infty \) oraz \( k_l = \infty \)), rekurencyjnie poszukujemy klucza \( x \) w poddrzewie o korzeniu wskazywanym przez \( p_i \).
Operacja Insert\( (S,x) \) zaczyna się od odszukania (jak w operacji Find) liścia, w którym powinien znaleźć się wstawiany klucz. Jeśli ten liść nie jest całkowicie wypełniony (czyli zawiera mniej niż \( m-1 \) kluczy), po prostu wstawiamy \( x \) w odpowiednie miejsce w węźle, przesuwając część kluczy (koszt tego zabiegu jest pomijalnie mały w porównaniu z kosztem odczytu i zapisu węzła na dysk). W przeciwnym razie po dołożeniu nowego klucza węzeł jest przepełniony i będziemy musieli przywrócić warunek zrównoważenia.
Najpierw próbujemy wykonać przesunięcie kluczy: ta metoda daje sie zastosować, jeśli któryś z dwóch sąsiednich braci przepełnionego węzła (który nie musi koniecznie być liściem) ma mniej niż \( m-1 \) kluczy. Dla ustalenia uwagi przyjmijmy, że jest to lewy brat i oznaczmy go przez \( p \), sam przepełniony węzeł przez \( q \), a klucz rozdzielający wskaźniki do \( p \) i \( q \) w ich ojcu przez \( k \). Klucz \( k \) przenosimy z ojca do \( p \) jako największy klucz w tym węźle, w jego miejsce w ojcu przenosimy najmniejszy klucz z \( q \), po czym skrajnie lewe poddrzewo \( q \) czynimy skrajnie prawym poddrzewem \( p \). Przesunięcie kluczy w prawo wykonuje się symetrycznie. Po takim zabiegu warunki równowagi zostają odtworzone i cała operacja się kończy.
Jeśli przepełniony węzeł nie ma niepełnego sąsiada, to wykonujemy rozbicie węzła. Listę kluczy dzielimy na trzy grupy: \( \lceil(m-1)/2\rceil \) najmniejszych kluczy, jeden klucz środkowy oraz \( \lfloor(m-1)/2\rfloor = \lceil m/2\rceil-1 \) największych kluczy. Z pierwszej i trzeciej grupy tworzymy nowe węzły, a środkowy klucz wstawiamy do ojca (co może spowodować jego przepełnienie i konieczność kontynuowania procesu przywracania zrównoważenia o jeden poziom wyżej) i odpowiednio przepinamy poddrzewa. Kiedy następuje przepełnienie korzenia, rozbijamy go na dwa węzły i tworzymy nowy korzeń mający dwóch synów (to jest właśnie powód, dla którego korzeń stanowi wyjątek w warunku (3)) - to jest jedyna sytuacja, w której wysokość B-drzewa się zwiększa.
Operację Delete\( (S,x) \) również zaczynamy od odszukania węzła z kluczem do usunięcia. Poddrzewa rozdzielane przez klucz \( x \) oznaczmy przez \( p \) i \( q \). Tak jak przy usuwaniu z BST, w miejsce \( x \) przenosimy - znajdujący się w liściu - największy klucz z \( p \) (albo największy z \( q \)). Lukę po przeniesionym kluczu niwelujemy zsuwając pozostałe. Jeśli jest ich co najmniej \( \lceil m/2\rceil-1 \), cała operacja jest zakończona, natomiast w razie niedoboru w celu przywrócenia równowagi musimy dokonać przesunięcia kluczy albo sklejenia węzłów. Jeśli któryś z dwóch sąsiednich braci węzła z niedoborem ma co najmniej o jeden klucz więcej niż dozwolone minimum, to - podobnie jak przy wstawianiu - przesuwamy skrajny klucz z niego do ojca w miejsce klucza rozdzielającego braci, który z kolei wędruje do węzła z niedoborem. Niemożność wykonania przesunięcia kluczy oznacza, że brat węzła z niedoborem ma dokładnie \( \lceil m/2\rceil-1 \) kluczy. Sklejamy te dwa węzły w jeden, wstawiając jeszcze pomiędzy ich klucze klucz rozdzielający z ojca i odpowiednio przepinając poddrzewa. Powstaje w ten sposób węzeł o \( 2\lceil m/2\rceil-2 \le m-1 \) kluczach, a z ojca ubywa jeden klucz, co może spowodować w nim niedobór i konieczność kontynuowania procesu przywracania zrównoważenia wyżej w drzewie. Jeśli korzeń traci swój jedyny klucz, usuwamy ten węzeł, a jego jedynego syna czynimy nowym korzeniem - to jest jedyna sytuacja, w której wysokość B-drzewa maleje.