B TREE w strukturze danych: przykład operacji wyszukiwania, wstawiania, usuwania

Spisie treści:

Anonim

Co to jest drzewo B?

B Tree to samobalansująca się struktura danych oparta na określonym zestawie reguł wyszukiwania, wstawiania i usuwania danych w szybszy i efektywniejszy sposób. Aby to osiągnąć, należy przestrzegać następujących zasad tworzenia drzewa B.

Drzewo B to specjalny rodzaj drzewa w strukturze danych. W 1972 roku ta metoda została po raz pierwszy wprowadzona przez McCreighta, a firma Bayer nazwał ją drzewem wyszukiwania ze zrównoważoną wysokością m-way. Pomaga zachować posortowane dane i umożliwiać wykonywanie różnych operacji, takich jak wstawianie, wyszukiwanie i usuwanie w krótszym czasie.

W tym samouczku B-Tree dowiesz się:

  • Co to jest drzewo B?
  • Dlaczego warto korzystać z B-Tree
  • Historia drzewa B.
  • Operacja wyszukiwania
  • Operacja wstawiania
  • Usuń operację

Reguły dla B-Tree

Tutaj są ważne zasady tworzenia B_Tree

  • Wszystkie liście zostaną utworzone na tym samym poziomie.
  • B-Tree jest określane przez liczbę stopni, które są również nazywane „porządkami” (określane przez zewnętrznego aktora, np. Programistę), określane 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, które mogą zawierać węzeł główny, a także jego węzły podrzędne, jest obliczana według następującego wzoru: 
    m - 1
    Na przykład: 
    m = 4max keys: 4 - 1 = 3

  • Każdy węzeł, z wyjątkiem roota, musi zawierać minimum kluczy 
    [m/2]-1
    Na przykład: 
    m = 4min keys: 4/2-1 = 1
  • Maksymalna liczba węzłów podrzędnych, jakie może mieć węzeł, jest równa jego stopniowi, czyli 
    m
  • Minimalne elementy potomne, jakie może mieć węzeł, to połowa zamówienia, czyli m / 2 (przyjmowana jest wartość pułapu).
  • Wszystkie klucze w węźle są sortowane w kolejności rosnącej.

Dlaczego warto korzystać z B-Tree

Oto powody korzystania z B-Tree

  • Zmniejsza liczbę odczytów wykonywanych na dysku
  • B Drzewa można łatwo zoptymalizować w celu dostosowania ich rozmiaru (czyli liczby węzłów potomnych) 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 odczytywanie i zapisywanie dużych bloków danych

Historia drzewa B.

  • Dane są przechowywane na dysku w blokach, dane te po wprowadzeniu do pamięci głównej (lub RAM) nazywane są strukturą danych.
  • W przypadku dużej 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 indeksów, które zapisują odniesienia do rekordów w oparciu o bloki, w których się znajdują. To drastycznie redukuje czas i zużycie pamięci.
  • Ponieważ mamy ogromne dane, możemy tworzyć wielopoziomowe tabele indeksów.
  • Indeks wielopoziomowy można zaprojektować za pomocą drzewa B do przechowywania danych posortowanych w sposób samobalansujący.

Operacja wyszukiwania

Operacja wyszukiwania jest najprostszą operacją na drzewie B.

Stosowany jest następujący algorytm:

  • Niech klucz (wartość) będzie przeszukiwany przez „k”.
  • Rozpocznij wyszukiwanie od korzenia i rekurencyjnie przechodź w dół.
  • Jeśli k jest mniejsze niż wartość główna, przeszukaj lewe poddrzewo, jeśli k jest większe niż wartość główna, 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ź do dziecka z większym kluczem.
  • Jeśli k nie zostanie znalezione w drzewie, zwracamy NULL.

Operacja wstawiania

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ę elementem nadrzędnym dla pozostałych dwóch węzłów podrzędnych.
  • Węzły muszą ponownie uporządkować klucze w kolejności rosnącej.

WSKAZÓWKA

Poniższe stwierdzenie nie dotyczy algorytmu wstawiania:

Ponieważ węzeł jest pełny, zostanie podzielony, a następnie zostanie wstawiona nowa wartość

W powyższym przykładzie:

  • Wyszukaj odpowiednią pozycję w węźle dla klucza
  • Włóż klucz do węzła docelowego i sprawdź reguły
  • Czy po wstawieniu węzeł ma więcej niż równą minimalnej liczbie kluczy, która wynosi 1? W tym przypadku tak. Sprawdź następną regułę.
  • Czy po wstawieniu węzeł ma więcej niż maksymalną liczbę kluczy, czyli 3? W tym przypadku nie. Oznacza to, że drzewo B nie narusza żadnych reguł i wstawianie jest zakończone.

W powyższym przykładzie:

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

W powyższym przykładzie:

  • Węzeł ma mniej niż max kluczy
  • 1 jest wstawiane obok 3, ale zasada kolejności rosnącej jest naruszona
  • Aby to naprawić, klucze są sortowane

Podobnie 13 i 2 można łatwo wstawić do węzła, ponieważ spełniają one regułę mniejszą niż maksymalna liczba kluczy 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 przy odchyleniu w lewo jest teraz nadrzędnym dla nowych węzłów potomnych.
  • 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.

Usuń operację

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
  • Zastosowano trzy warunki 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

  • Cel znajduje się w węźle liścia, więcej niż min kluczy.
    • Usunięcie tego nie naruszy właściwości drzewa B.
  • Cel znajduje się w węźle liścia, ma minimalną liczbę kluczowych węzłów
    • Usunięcie tego spowoduje naruszenie właściwości drzewa B.
    • Węzeł docelowy może pożyczyć klucz z bezpośredniego 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 wypoż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 przesłana do węzła docelowego i usunie wartość docelową
  • Cel znajduje się w węźle liścia, ale żadne rodzeństwo nie ma więcej niż minimalną liczbę kluczy
    • Wyszukaj klucz
    • Połącz z rodzeństwem i minimalną liczbą węzłów nadrzędnych
    • Łączna 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 poprzednika w kolejności lub następcę w kolejności
  • W przypadku poprzednika w kolejności zostanie wybrany maksymalny klucz z jego lewego poddrzewa
  • W przypadku następcy w zamówieniu zostanie wybrany minimalny klucz z jego prawego poddrzewa
  • Jeśli poprzednik w kolejności klucza docelowego ma więcej niż klucze min, tylko wtedy może zastąpić klucz docelowy maksimum poprzednika w kolejności
  • Jeśli poprzednik w kolejności klucza docelowego nie ma więcej niż min kluczy, poszukaj minimalnego klucza następcy w kolejności.
  • Jeśli poprzednik i następca klucza docelowego w kolejności 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 poprzedniego poddrzewa w kolejności
  • Jeśli po usunięciu cel ma mniej niż min kluczy, węzeł docelowy pożyczy maksymalną wartość od swojego rodzica za pośrednictwem rodzica rodzica.
  • Maksymalna wartość rodzica zostanie przyjęta przez cel, ale z węzłami maksymalnej wartości rodzeństwa.

Teraz przyjrzyjmy się operacji usuwania na przykładzie.

Powyższy diagram przedstawia różne przypadki operacji usuwania w B-drzewie. To B-Drzewo jest rzędu 5, co oznacza, że ​​minimalna liczba węzłów podrzędnych, jakie może mieć każdy węzeł, to 3, a maksymalna liczba węzłów podrzędnych, jakie może mieć każdy węzeł, to 5. Zważywszy, że minimalna i maksymalna liczba kluczy w każdym węźle mogą mieć 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 liczbie kluczy minimalnej, więc nie można go usunąć bezpośrednio, ponieważ naruszy to warunki

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

  • Węzeł docelowy pożyczy klucz od bezpośredniego rodzeństwa, w tym przypadku poprzednika w kolejności (lewe rodzeństwo), ponieważ nie ma żadnego następcy w kolejności (prawe rodzeństwo)
  • Maksymalna wartość poprzednika w zamówieniu zostanie przesłana do rodzica, a rodzic prześle maksymalną wartość do węzła docelowego (patrz diagram poniżej)

Poniższy przykład ilustruje, jak usunąć klucz, który wymaga wartości z jego następcy 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 minimalnej liczbie kluczy.
  • Minimalna wartość następcy w kolejności zostanie przesłana do rodzica, a rodzic prześle maksymalną wartość do węzła docelowego.

W poniższym przykładzie węzeł docelowy nie ma żadnego elementu siostrzanego, który mógłby przekazać swój klucz węzłowi docelowemu. Dlatego wymagane jest scalanie.

Zobacz procedurę usuwania takiego klucza:

  • Scal węzeł docelowy z dowolnym jego bezpośrednim rodzeństwem wraz z kluczem nadrzędnym
    • Klucz z węzła nadrzędnego jest wybierany jako rodzeństwo między dwoma łączącymi się węzłami
  • Usuń klucz docelowy ze scalonego węzła

Usuń pseudokod operacji

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

Dane wyjściowe :

Największy element jest usuwany z B-Tree.

Podsumowanie:

  • B Tree to samobalansująca się struktura danych zapewniająca lepsze wyszukiwanie, wstawianie i usuwanie danych z dysku.
  • B Drzewo jest regulowane przez określony stopień
  • B Klucze i węzły drzewa są ułożone w porządku rosnącym.
  • Operacja wyszukiwania drzewa B jest najprostsza, która zawsze zaczyna się od katalogu głównego i rozpoczyna sprawdzanie, czy klucz docelowy jest większy, czy mniejszy niż wartość węzła.
  • Operacja wstawiania drzewa B jest dość szczegółowa, która najpierw znajduje odpowiednią pozycję wstawienia dla klucza docelowego, wstawia go, ocenia poprawność drzewa B w różnych przypadkach, a następnie odpowiednio przebudowuje węzły drzewa B.
  • Operacja usuwania drzewa B najpierw wyszukuje klucz docelowy do usunięcia, usuwa go, ocenia ważność na podstawie kilku przypadków, takich jak klucze minimum i maksimum węzła docelowego, rodzeństwa i rodzica.