B TREE w strukturze danych: Wyszukaj, wstaw, usuń OperaPrzykład

Zasady dla B-Tree

Oto ważne zasady tworzenia B_Tree

• Wszystkie liście zostaną utworzone na tym samym poziomie.
• B-Tree wyznaczane jest przez liczbę stopni, zwaną także „porządkiem” (określanym przez zewnętrznego aktora, np. programistę), określaną jako

  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.
• Maksymalna liczba węzłów podrzędnych, jaką może zawierać węzeł główny i jego węzły podrzędne, jest obliczana 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 roota, 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 korzystania z B-Tree

• Zmniejsza liczbę odczytów dokonywanych na dysku
• B Drzewa 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. Dane te po przeniesieniu do pamięci głównej (lub RAM) nazywane są strukturą danych.
• W przypadku ogromnych ilości danych przeszukanie jednego rekordu na dysku wymaga 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 indeksowe, w których zapisywane są odniesienia do rekordów w oparciu o bloki, w których się one znajdują. To drastycznie zmniejsza czas i zużycie pamięci.
• Ponieważ mamy ogromne dane, możemy tworzyć wielopoziomowe tabele indeksowe.
• Indeks wielopoziomowy można zaprojektować przy użyciu drzewa B w celu uporządkowania danych w sposób samorównoważący.

Szukaj Operacja

Operacja wyszukiwania jest najprostszą operacją w drzewie B.

Zastosowano następujący algorytm:

• Niech klucz (wartość) będzie wyszukiwany przez „k”.
• Rozpocznij wyszukiwanie od korzenia i rekurencyjnie przechodź w dół.
• Jeśli k jest mniejsze niż wartość korzenia, przeszukaj lewe poddrzewo, jeśli k jest większe niż wartość pierwiastka, przeszukaj 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ż B Tree jest drzewem samobalansującym, nie można wymusić wstawienia klucza do dowolnego węzła.

Zastosowano 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.

TIP	Poniższe stwierdzenie nie jest prawdziwe w odniesieniu do algorytmu wstawiania: Ponieważ węzeł jest pełny, dlatego zostanie podzielony, a następnie zostanie wstawiona nowa wartość

W powyższym przykładzie:

• Wyszukaj klucz w odpowiedniej pozycji w węźle
• Włóż klucz do węzła docelowego i sprawdź reguły
• Czy po wstawieniu węzeł ma większą niż minimalną liczbę kluczy, czyli 1? W tym przypadku tak. Sprawdź następną regułę.
• Czy po wstawieniu węzeł ma więcej niż maksymalna liczba kluczy, czyli 3? W tym przypadku nie, tak nie jest. Oznacza to, że drzewo B nie narusza żadnych zasad i wstawianie zostało 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 kluczy niż maksymalna
• 1 wstawia się obok 3, ale zostaje naruszona zasada kolejności rosnącej
• Aby temu zaradzić, klucze są sortowane

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

W powyższym przykładzie:

• Węzeł ma klucze równe maksymalnej liczbie kluczy.
• Klucz jest wstawiany do węzła docelowego, ale narusza zasadę 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.

Zastosowano następujący algorytm:

• Uruchom operację wyszukiwania i znajdź klucz docelowy w węzłach
• Trzy warunki stosowane w zależności od lokalizacji klucza docelowego, 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łasności B Tree
• Target znajduje się w węźle liścia, ma minimalne węzły kluczowe
• Usunięcie tego spowoduje naruszenie własności B Tree
• Target węzeł może pożyczyć klucz od najbliższego lewego węzła lub bezpośredniego prawego węzła (rodzeństwo)
• Rodzeństwo powie tak jeśli ma więcej niż minimalną liczbę kluczy
• Klucz zostanie pożyczony z węzła nadrzędnego, maksymalna wartość zostanie przesłana do węzła nadrzędnego, maksymalna wartość węzła nadrzędnego zostanie przeniesiona do węzła docelowego i usunie wartość docelową
• Target znajduje się w węźle liścia, ale żadne rodzeństwo nie ma więcej niż minimalna liczba kluczy
• Wyszukaj klucz
• Scal z rodzeństwem i minimalną liczbą węzłów nadrzędnych
• Całkowita liczba kluczy będzie teraz większa niż min
• Klucz docelowy zostanie zastąpiony minimum węzła nadrzędnego

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

• Wybierz albo w kolejności poprzednika, albo w kolejności następcy
• W przypadku poprzednika w kolejności wybrany zostanie klucz maksymalny z jego lewego poddrzewa
• W przypadku następcy w kolejności wybrany zostanie klucz minimalny z jego prawego poddrzewa
• Jeśli poprzednik klucza docelowego ma więcej kluczy niż min, tylko wtedy może zastąpić klucz docelowy maksimum poprzednika w kolejności
• Jeśli poprzednik klucza docelowego w kolejności nie ma więcej niż kluczy min, poszukaj klucza minimalnego następcy 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 maksymalnym elementem poddrzewa poprzednika w kolejności
• Jeśli po usunięciu cel ma mniej niż min kluczy, wówczas węzeł docelowy pożyczy maksymalną wartość od swojego rodzeństwa za pośrednictwem rodzica rodzeństwa.
• Maksymalna wartość rodzica zostanie pobrana przez cel, ale z węzłami maksymalnej wartości 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 podrzędnych, jaką może mieć dowolny węzeł, wynosi 3, a maksymalna liczba węzłów podrzędnych, jaką może mieć dowolny węzeł, wynosi 5. Podczas gdy minimalna i maksymalna liczba kluczy, jaką może mieć dowolny węzeł, wynosi 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ż 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żna go usunąć bezpośrednio, ponieważ naruszy 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 (lewe rodzeństwo), ponieważ nie ma żadnego następcy w kolejności (prawe rodzeństwo)
• Maksymalna wartość poprzednika inorder zostanie przekazana do rodzica, a rodzic przekaże maksymalną wartość do węzła docelowego (patrz diagram poniżej)

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ępcy w kolejności (prawe rodzeństwo), ponieważ jego poprzednik w kolejności (lewe rodzeństwo) ma klucze równe minimalnym kluczom.
• 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 rodzeństwa, które mogłoby przekazać swój klucz węzłowi docelowemu. Dlatego konieczne jest połączenie.

Zobacz procedurę usuwania takiego klucza:

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

Usunięcia OperaPseudokod

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

Wydajność:

Największy element zostanie usunięty z drzewa B.

Podsumowanie

• B Tree to samorównoważąca się struktura danych ułatwiająca wyszukiwanie, wstawianie i usuwanie danych z dysku.
• B Drzewo jest regulowane według określonego stopnia
• B Klucze i węzły drzewa są ułożone w porządku rosnącym.
• Operacja wyszukiwania w drzewie B jest najprostsza i zawsze zaczyna się od korzenia, a następnie sprawdza, czy klucz docelowy jest większy, czy mniejszy od wartości węzła.
• Operacja wstawiania w drzewie B jest dość szczegółowa. Najpierw znajduje się odpowiednią pozycję wstawiania dla klucza docelowego, wstawia go, ocenia poprawność drzewa B w różnych przypadkach, a następnie odpowiednio restrukturyzuje węzły drzewa B.
• Operacja usuwania w drzewie B najpierw wyszukuje klucz docelowy przeznaczony do usunięcia, usuwa go, a następnie ocenia jego poprawność na podstawie kilku przypadków, takich jak minimalna i maksymalna liczba kluczy węzła docelowego, rodzeństwa i węzła nadrzędnego.