Drzewo B w strukturze danych: wyszukiwanie, wstawianie, usuwanie

Co to jest drzewo B?

Drzewo B to samorównoważąca się struktura danych oparta na określonym zestawie reguł wyszukiwania, wstawiania i usuwania danych w szybszy i bardziej efektywny sposób. Aby to osiągnąć, stosuje się poniższe reguły, aby utworzyć drzewo B.

B-drzewo to specjalny rodzaj drzewa w strukturze danych. W 1972 roku McCreight i Bayer po raz pierwszy wprowadzili tę metodę, nazywając ją Height Balanced m-way Search Tree (Drzewem Wyszukiwania Wysokości Zrównoważonych m-kierunków). Pomaga ona zachować posortowane dane i umożliwia wykonywanie różnych operacji, takich jak wstawianie, wyszukiwanie i usuwanie, w krótszym czasie.

Zasady dla B-Tree

Oto ważne zasady tworzenia drzewa B:

• Wszystkie liście zostaną utworzone na tym samym poziomie.
• Drzewo B jest określone przez liczbę stopni, zwaną również „kolejnością” (określoną przez aktora zewnętrznego, np. programistę), zwaną m dalej. Wartość m zależy od rozmiaru bloku na dysku, na którym głównie znajdują się dane.
• Lewe poddrzewo węzła będzie miało mniejsze wartości niż prawa strona poddrzewa. Oznacza to, że węzły są również sortowane w kolejności rosnącej od lewej do prawej.
• Maksymalną liczbę kluczy, jaką może zawierać węzeł główny i jego węzły podrzędne, oblicza się według następującego wzoru: m − 1. Na przykład:

  m = 4
  max keys: 4 − 1 = 3

• Każdy węzeł, z wyjątkiem węzła głównego, musi zawierać minimalną liczbę kluczy [m/2] − 1. Na przykład:

  m = 4
  min keys: 4/2 − 1 = 1

• Maksymalna liczba węzłów podrzędnych, jakie może mieć węzeł, jest równa jego stopniowi, tj m.
• Minimalne dzieci, jakie może mieć węzeł, to połowa rzędu, czyli m/2 (przyjmowana jest wartość górna).
• Wszystkie klucze w węźle są sortowane w kolejności rosnącej.

Dlaczego warto używać B-Tree

Oto powody, dla których warto używać drzewa B:

• Zmniejsza liczbę odczytów wykonywanych na dysku.
• Drzewa B można łatwo zoptymalizować, dostosowując ich rozmiar (czyli liczbę węzłów podrzędnych) do rozmiaru dysku.
• Jest to specjalnie zaprojektowana technika obsługi dużych ilości danych.
• Jest to przydatny algorytm dla baz danych i systemów plików.
• Dobry wybór, jeśli chodzi o odczyt i zapis dużych bloków danych.

Historia drzewa B

• Dane są przechowywane na dysku w blokach. Po przeniesieniu do pamięci głównej (RAM) nazywane są strukturą danych.
• W przypadku ogromnych ilości danych przeszukanie jednego rekordu na dysku wiąże się z koniecznością odczytania całego dysku. Zwiększa to czas i zużycie pamięci głównej ze względu na dużą częstotliwość dostępu do dysku i rozmiar danych.
• Aby temu zaradzić, tworzone są tabele indeksów, które zapisują odniesienia do rekordów na podstawie bloków, w których się znajdują. To radykalnie skraca czas i zmniejsza zużycie pamięci.
• Ponieważ mamy ogromne dane, możemy tworzyć wielopoziomowe tabele indeksowe.
• Indeks wielopoziomowy można zaprojektować, używając drzewa B do keeping dane posortowano w sposób samobalansujący.

Szukaj Operacja

Operacja wyszukiwania jest najprostszą operacją na drzewie B. Zastosowano następujący algorytm:

• Niech kluczem (wartością) do przeszukania będzie „k”.
• Rozpocznij wyszukiwanie od korzenia i rekurencyjnie przechodź w dół.
• Jeśli k jest mniejsze od wartości pierwiastka, przeszukujemy lewe poddrzewo; jeśli k jest większe od wartości pierwiastka, przeszukujemy prawe poddrzewo.
• Jeśli węzeł ma znalezione k, po prostu zwróć węzeł.
• Jeśli k nie zostanie znalezione w węźle, przejdź w dół do dziecka z większym kluczem.
• Jeśli k nie zostanie znalezione w drzewie, zwracamy NULL.

wstawka Operacja

Ponieważ drzewo B jest drzewem samobalansującym, nie można wymusić wstawienia klucza do dowolnego węzła. Obowiązuje następujący algorytm:

• Uruchom operację wyszukiwania i znajdź odpowiednie miejsce wstawienia.
• Wstaw nowy klucz we właściwym miejscu, ale jeśli węzeł ma już maksymalną liczbę kluczy:
• Węzeł wraz z nowo wstawionym kluczem oddzieli się od środkowego elementu.
• Środkowy element stanie się rodzicem dla pozostałych dwóch węzłów podrzędnych.
• Węzły muszą ponownie ułożyć klucze w kolejności rosnącej.

W powyższym przykładzie:

• Wyszukaj odpowiednią pozycję w węźle, aby znaleźć klucz.
• Wprowadź klucz do węzła docelowego i sprawdź reguły.
• Czy po wstawieniu węzeł ma co najmniej 1 minimalną liczbę kluczy? W tym przypadku odpowiedź brzmi: tak. Sprawdź kolejną regułę.
• Czy po wstawieniu węzeł ma więcej kluczy niż maksymalna liczba, która wynosi 3? W tym przypadku odpowiedź brzmi: nie. Oznacza to, że drzewo B nie narusza żadnych reguł, a wstawianie jest zakończone.

W powyższym przykładzie:

• Węzeł osiągnął maksymalną liczbę kluczy.
• Węzeł zostanie podzielony, a środkowy klucz stanie się węzłem głównym pozostałych dwóch węzłów.
• W przypadku parzystej liczby kluczy, środkowy węzeł zostanie wybrany poprzez odchylenie w lewo lub w prawo.

W powyższym przykładzie:

• Węzeł ma mniej niż maksymalną liczbę kluczy.
• Obok 3 wstawiono 1, ale naruszono zasadę kolejności rosnącej.
• Aby rozwiązać ten problem, klucze zostały posortowane.

Podobnie, 13 i 2 można łatwo wstawić do węzła, ponieważ spełniają one regułę „kluczy mniejszych od maks.” dla węzłów.

W powyższym przykładzie:

• Węzeł ma klucze równe maksymalnej liczbie kluczy.
• Klucz został wstawiony do węzła docelowego, ale narusza to regułę maksymalnej liczby kluczy.
• Węzeł docelowy jest podzielony, a środkowy klawisz z odchyleniem w lewo jest teraz rodzicem nowych węzłów podrzędnych.
• Nowe węzły są ułożone w kolejności rosnącej.

Podobnie, w oparciu o powyższe zasady i przypadki, pozostałe wartości można łatwo wstawić do drzewa B.

Usunięcia Operacja

Operacja usuwania ma więcej reguł niż operacje wstawiania i wyszukiwania. Obowiązuje następujący algorytm:

• Uruchom operację wyszukiwania i znajdź klucz docelowy w węzłach.
• W zależności od lokalizacji klucza docelowego stosowane są trzy warunki, jak wyjaśniono w poniższych sekcjach.

Jeśli klucz docelowy znajduje się w węźle liścia

• Target znajduje się w węźle liścia, więcej niż min kluczy. Usunięcie tego nie naruszy właściwości drzewa B.
• Target znajduje się w węźle liścia i ma węzły o minimalnym kluczu. Usunięcie tego elementu naruszy właściwość drzewa B.
• Węzeł docelowy może pożyczyć klucz od najbliższego węzła lewego lub najbliższego węzła prawego (rodzeństwa).
• Rodzeństwo powie tak jeśli ma więcej niż minimalną liczbę kluczy.
• Klucz zostanie pożyczony od węzła nadrzędnego, wartość maksymalna zostanie przesłana do węzła nadrzędnego, wartość maksymalna węzła nadrzędnego zostanie przesłana do węzła docelowego, a wartość docelowa zostanie usunięta.
• Target znajduje się w węźle liściastym, ale żadne z rodzeństwa nie ma większej liczby kluczy niż minimalna: wyszukaj klucz, połącz z rodzeństwem i minimalną liczbą węzłów nadrzędnych, całkowita liczba kluczy będzie teraz większa niż minimalna, a klucz docelowy zostanie zastąpiony minimalną liczbą węzłów nadrzędnych.

Jeśli klucz docelowy znajduje się w węźle wewnętrznym

• Wybierz poprzednika lub następcę w kolejności chronologicznej.
• W przypadku poprzednika o kolejności in-order wybrany zostanie maksymalny klucz z jego lewego poddrzewa.
• W przypadku następnika uporządkowanego zostanie wybrany minimalny klucz z jego prawego poddrzewa.
• Tylko wtedy, gdy poprzednik klucza docelowego ma więcej kluczy niż klucze min, można zastąpić klucz docelowy kluczem maksimum poprzednika w kolejności.
• Jeśli poprzednik klucza docelowego w kolejności nie ma więcej niż min kluczy, należy poszukać minimalnego klucza następnika w kolejności.
• Jeśli poprzednik i następnik klucza docelowego mają mniej niż min kluczy, połącz poprzednika i następcę.

Jeśli klucz docelowy znajduje się w węźle głównym

• Zastąp elementem maksymalnym poddrzewa poprzedniego rzędu.
• Jeżeli po usunięciu węzeł docelowy ma mniej niż min kluczy, wówczas węzeł docelowy pożyczy wartość max od swojego rodzeństwa za pośrednictwem węzła nadrzędnego rodzeństwa.
• Maksymalna wartość elementu nadrzędnego zostanie przejęta przez element docelowy, ale z węzłami o maksymalnej wartości elementu rodzeństwa.

Teraz wyjaśnimy operację usuwania na przykładzie.

Powyższy diagram przedstawia różne przypadki operacji usuwania w drzewie B. To drzewo B jest rzędu 5, co oznacza, że ​​minimalna liczba węzłów potomnych, jaką może mieć każdy węzeł, to 3, a maksymalna liczba węzłów potomnych, jaką może mieć każdy węzeł, to 5. Natomiast minimalna i maksymalna liczba kluczy, jaką może mieć każdy węzeł, to odpowiednio 2 i 4.

W powyższym przykładzie:

• Węzeł docelowy ma klucz docelowy do usunięcia.
• Węzeł docelowy ma więcej kluczy niż wynosi minimalna liczba kluczy.
• Po prostu usuń klucz.

W powyższym przykładzie:

• Węzeł docelowy ma klucze równe minimalnej liczbie kluczy, więc nie możemy go usunąć bezpośrednio, gdyż naruszyłoby to warunki.

Poniższy diagram wyjaśnia, jak usunąć ten klucz:

• Węzeł docelowy pożyczy klucz od bezpośredniego rodzeństwa, w tym przypadku od poprzednika w kolejności (lewego rodzeństwa), ponieważ nie posiada żadnego następcy w kolejności (prawego rodzeństwa).
• Maksymalna wartość poprzednika w kolejności zostanie przekazana do węzła nadrzędnego, a węzeł nadrzędny przekaże maksymalną wartość do węzła docelowego (patrz poniższy diagram).

Poniższy przykład ilustruje sposób usuwania klucza, który wymaga wartości z jego następnika w kolejności.

• Węzeł docelowy pożyczy klucz od bezpośredniego rodzeństwa, w tym przypadku następnika w kolejności (prawego rodzeństwa), ponieważ jego poprzednik w kolejności (lewy rodzeństwo) ma klucze równe kluczom minimalnym.
• Minimalna wartość następnika w kolejności zostanie przesłana do elementu nadrzędnego, a element nadrzędny przekaże wartość maksymalną do węzła docelowego.

W poniższym przykładzie węzeł docelowy nie ma żadnego węzła siostrzanego, który mógłby przekazać mu swój klucz. W związku z tym wymagane jest scalenie. Zobacz procedurę usuwania takiego klucza:

• Połącz węzeł docelowy z dowolnym z jego bezpośrednich rodzeństwa i kluczem nadrzędnym.
• Wybierany jest klucz z węzła nadrzędnego, który znajduje się pomiędzy dwoma łączonymi węzłami.
• Usuń klucz docelowy ze scalonego węzła.

Usunięcia Operacja Pseudo Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

Wyjście: Największy element zostanie usunięty z drzewa B.

FAQ