W poniższym samouczku poznamy strukturę danych B Tree i rozważymy jej wizualizację.
Więc zacznijmy.
Co to jest drzewo B?
The Drzewo B jest specjalny typ wielostronnego drzewa wyszukiwania , powszechnie znany jako Droga M drzewo, które samo się równoważy. Ze względu na zrównoważoną strukturę drzewa te są powszechnie wykorzystywane do obsługi i zarządzania ogromnymi bazami danych oraz do upraszczania wyszukiwania. W drzewie B każdy węzeł może mieć co najwyżej n węzłów podrzędnych. B Tree jest przykładem wielopoziomowego indeksowania w systemie zarządzania bazami danych (DBMS). Zarówno węzeł liścia, jak i węzeł wewnętrzny będą miały odniesienia do rekordów. Drzewo B jest znane jako drzewo zrównoważone, ponieważ wszystkie węzły liściowe znajdują się na tym samym poziomie.
Poniższy diagram jest przykładem drzewa B:
Rysunek 1. A B Drzewo z rozkazem 3
Zrozumienie zasad drzewa B
Poniżej przedstawiono ważne właściwości drzewa B:
- Wszystkie węzły liściowe znajdują się na tym samym poziomie.
- Strukturę danych B Tree definiuje się mianem minimalnego stopnia „d”. Wartość „d” zależy od rozmiaru bloku dysku.
- Każdy węzeł, z wyjątkiem korzenia, musi składać się z co najmniej kluczy d-1. Węzeł główny może składać się z minimum 1 klucza.
- Wszystkie węzły (w tym węzeł główny) mogą składać się z co najwyżej (2d-1) Klucze.
- Liczba dzieci węzła jest równa dodanie liczby znajdujących się w nim kluczy i .
- Wszystkie klucze węzła są sortowane w kolejności rosnącej. Dziecko pomiędzy dwoma kluczami, k1 i k2, składa się ze wszystkich kluczy z zakresu odpowiednio pomiędzy k1 i k2.
- W przeciwieństwie do drzewa wyszukiwania binarnego, struktura danych drzewa B rośnie i kurczy się od korzenia. Podczas gdy drzewo wyszukiwania binarnego rośnie w dół i kurczy się w dół.
- Podobnie jak w przypadku innych samobalansujących się binarnych drzew wyszukiwania, złożoność czasowa struktury danych drzewa B dla operacji takich jak wyszukiwanie, wstawianie i usuwanie wynosi O(log?n) .
- Wstawienie węzła do drzewa B następuje tylko w węźle liścia.
Rozważmy następujący przykład drzewa B o minimalnym rzędzie 5.
Rysunek 2. A B Drzewo porządku 5
Uwaga: Wartość minimalnego zamówienia jest znacznie większa niż 5 w praktycznych drzewach B.
Na powyższym diagramie możemy zaobserwować, że wszystkie węzły-liście są na tym samym poziomie, a wszystkie węzły niebędące liśćmi nie mają pustego poddrzewa i składają się z kluczy o jeden mniej niż liczba ich dzieci.
Zestaw sformułowań reguł B Tree:
Każde drzewo B zależy od dodatniej stałej liczby całkowitej znanej jako MINIMUM , który służy do określenia liczby elementów danych, które mogą być przechowywane w jednym węźle.
Zasada nr 1: Korzeń może mieć tylko jeden element danych (lub nawet nie mieć żadnych elementów danych, jeśli nie jest również dzieckiem); co najmniej każdy inny węzeł MINIMUM elementy danych.
Zasada 2: Maksymalna liczba elementów danych przechowywanych w węźle jest dwukrotnie większa od wartości MINIMUM .
Ciąg Java z formatem
Zasada 3: Elementy danych każdego węzła drzewa B są przechowywane w częściowo wypełnionej tablicy, posortowanej od najmniejszego elementu danych (w indeksie 0 ) do największego elementu danych (w ostatecznie wykorzystanej pozycji tablicy).
Zasada 4: Całkowita liczba poddrzew poniżej węzła innego niż liść jest zawsze o jeden większa niż liczba elementów danych w tym węźle.
- poddrzewo 0, poddrzewo 1,...
Zasada 5: W odniesieniu do dowolnego węzła innego niż liść:
- Element danych w indeksie jest większy niż wszystkie elementy danych w numerze poddrzewa I węzła oraz
- Element danych w indeksie jest mniejszy niż wszystkie elementy danych w numerze poddrzewa ja+1 węzła.
Zasada 6: Każdy liść w drzewie B ma tę samą głębokość. W ten sposób zapewnia, że drzewo B zapobiega problemowi niezrównoważonego drzewa.
Operacje na strukturze danych B Tree
Aby mieć pewność, że podczas operacji nie zostaną naruszone żadne właściwości struktury danych B Tree, B Tree można podzielić lub połączyć. Oto niektóre operacje, które możemy wykonać na drzewie B:
- Wyszukiwanie elementu danych w B Tree
- Wstawienie elementu danych do B Tree
- Usuwanie elementu danych w drzewie B
Operacja wyszukiwania na drzewie B
Wyszukiwanie elementu w drzewie B jest podobne do wyszukiwania w drzewie wyszukiwania binarnego. Zamiast jednak podejmować dwukierunkową decyzję (w lewo lub w prawo), jak w drzewie wyszukiwania binarnego, drzewo B podejmuje m-kierunkową decyzję w każdym węźle, gdzie m jest liczbą dzieci węzła.
Kroki wyszukiwania elementu danych w drzewie B:
Krok 1: Wyszukiwanie rozpoczyna się od węzła głównego. Porównaj element wyszukiwania k z pierwiastkiem.
Krok 1.1: Jeśli węzeł główny składa się z elementu k, wyszukiwanie zostanie zakończone.
Krok 1.2: Jeśli element k jest mniejszy niż pierwsza wartość w pierwiastku, przejdziemy do dziecka znajdującego się najbardziej na lewo i przeszukamy je rekurencyjnie.
Krok 1.3.1: Jeśli korzeń ma tylko dwoje dzieci, przejdziemy do dziecka znajdującego się najbardziej na prawo i rekurencyjnie przeszukamy węzły podrzędne.
Krok 1.3.2: Jeśli root ma więcej niż dwa klucze, przeszukamy resztę.
Krok 2: Jeżeli po przejściu całego drzewa element k nie zostanie znaleziony, to szukanego elementu nie ma w drzewie B.
1 do 100 rzymski nr
Zwizualizujmy powyższe kroki na przykładzie. Załóżmy, że chcemy poszukać klucza k=34 w następującym Drzewie B:
Rysunek 3.1. Dane drzewo B
- Najpierw sprawdzimy, czy klucz k = 34 znajduje się w węźle głównym. Ponieważ klucz nie znajduje się w katalogu głównym, przejdziemy do jego węzłów podrzędnych. Możemy również zaobserwować, że węzeł główny ma dwoje dzieci; dlatego porównamy wymaganą wartość między dwoma kluczami.
Rysunek 3.2. Klucz k nie jest obecny w katalogu głównym - Teraz, gdy możemy zauważyć, że klucz k jest większy niż węzeł główny, tj. 30, przejdziemy do prawego dziecka korzenia.
Rysunek 3.3. Klawisz k > 30, przejdź do prawego dziecka - Porównamy teraz klucz k z wartościami obecnymi w węźle, czyli odpowiednio 40 i 50. Ponieważ klucz k jest mniejszy niż lewy klucz, tj. 40, przejdziemy do lewego dziecka węzła.
Rysunek 3.4. Klucz k<40, move to left child< li> - Ponieważ wartość w lewym potomku liczby 40 wynosi 34, co jest wartością wymaganą, możemy stwierdzić, że klucz został znaleziony i operacja wyszukiwania została zakończona.
Rysunek 3.4. Klucz k = 34, lewe dziecko 40
W powyższym przykładzie porównaliśmy klucz z czterema różnymi wartościami, aż go znaleźliśmy. Zatem złożoność czasowa wymagana do operacji wyszukiwania w drzewie B wynosi O(log?n) .
Wstawianie operacji na drzewie B
Wstawiając element danych do drzewa B, musimy najpierw sprawdzić, czy ten element jest już obecny w drzewie, czy nie. Jeśli element danych zostanie znaleziony w drzewie B, wówczas operacja wstawiania nie zostanie wykonana. Jeśli jednak tak nie jest, będziemy kontynuować wstawianie. Podczas wstawiania elementu w węźle liścia należy uwzględnić dwa scenariusze:
Kroki, aby wstawić element danych do drzewa B:
Krok 1: Zaczniemy od obliczenia maksymalnej liczby kluczy w węźle na podstawie kolejności Drzewa B.
Krok 2: Jeżeli drzewo jest puste, przydzielany jest węzeł główny i wstawiamy klucz pełniący rolę węzła głównego.
Krok 3: Przeszukamy teraz odpowiedni węzeł w celu wstawienia.
Krok 4: Jeśli węzeł jest pełny:
Krok 4.1: Elementy danych będziemy wstawiać w kolejności rosnącej.
Krok 4.2: Jeśli elementy danych są większe niż maksymalna liczba kluczy, podzielimy pełny węzeł po medianie.
Krok 4.3: Przesuniemy klawisz środkowy w górę i rozdzielimy lewy i prawy klawisz jako lewe i prawe dziecko.
wyszukiwanie kontradyktoryjne
Krok 5: Jeżeli węzeł nie jest pełny, wstawimy go w kolejności rosnącej.
Zwizualizujmy powyższe kroki na przykładzie. Załóżmy, że mamy utworzyć drzewo B rzędu 4. Elementy danych, które należy wstawić do drzewa B, to 5,3,21,11,1,16,8,13,4 i 9 .
- Ponieważ m jest równe 3, jest to maksymalna liczba kluczy dla węzła = m-1 = 3-1 = 2 .
- Zaczniemy od wstawienia 5 w pustym drzewie.
Rysunek 4.1. Wkładanie 5 - Teraz wstawimy 3 do drzewa. Ponieważ 3 jest mniejsze niż 5, wstawimy 3 na lewo od 5 w tym samym węźle.
Rysunek 4.2. Wkładanie 3 - Wstawimy teraz do drzewa liczbę 21, a ponieważ liczba 21 jest większa niż 5, zostanie ona wstawiona na prawo od liczby 5 w tym samym węźle. Ponieważ jednak wiemy, że maksymalna liczba kluczy w węźle wynosi 2, jeden z tych kluczy zostanie przeniesiony do węzła powyżej w celu jego podziału. Zatem 5, środkowy element danych, przesunie się w górę, a 3 i 21 staną się odpowiednio jego lewym i prawym węzłem.
Rysunek 4.3. Wstawianie 21 - Teraz czas na wstawienie kolejnego elementu danych, czyli 11, który jest większy od 5, ale mniejszy od 21. Zatem 11 zostanie wstawione jako klucz po lewej stronie węzła składającego się z 21 jako klucza.
Rysunek 4.4. Wkładanie 11 - Podobnie wstawimy do drzewa kolejny element danych 1 i jak możemy zaobserwować, 1 jest mniejsze niż 3; dlatego zostanie wstawiony jako klucz po lewej stronie węzła składającego się z 3 jako klucza.
Rysunek 4.5. Wstawianie 1 - Teraz wstawimy do drzewa element danych 16, który jest większy niż 11, ale mniejszy niż 21. Jednak liczba kluczy w tym węźle przekracza maksymalną liczbę kluczy. Dlatego węzeł zostanie podzielony, przesuwając środkowy klawisz do korzenia. Zatem 16 zostanie wstawione na prawo od 5, dzieląc 11 i 21 na dwa oddzielne węzły.
Rysunek 4.6. Wstawianie 16 - Element danych 8 zostanie wstawiony jako klucz na lewo od 11.
Rysunek 4.7. Wkładanie 8 - Do drzewa wstawimy liczbę 13, która jest mniejsza niż 16 i większa niż 11. Dlatego też element danych 13 należy wstawić na prawo od węzła składającego się z 8 i 11. Ponieważ jednak maksymalna liczba kluczy w drzewie może będzie wynosić tylko 2, nastąpi podział, przenosząc środkowy element danych 11 do powyższego węzła oraz 8 i 13 na dwa oddzielne węzły. Teraz powyższy węzeł będzie składał się z 5, 11 i 16, co ponownie przekracza maksymalną liczbę kluczy. Dlatego nastąpi kolejny podział, w wyniku którego element danych 11 stanie się węzłem głównym, a jego elementami podrzędnymi będą elementy 5 i 16.
Rysunek 4.8. Wkładanie 13 - Ponieważ element danych 4 jest mniejszy niż 5, ale większy niż 3, zostanie wstawiony na prawo od węzła składającego się z 1 i 3, co ponownie przekroczy maksymalną liczbę kluczy w węźle. Dlatego rozlanie nastąpi ponownie, przesuwając 3 do górnego węzła obok 5.
Rysunek 4.9. Wkładanie 4 - Na koniec element danych 9, który jest większy niż 8, ale mniejszy niż 11, zostanie wstawiony na prawo od węzła składającego się z 8 jako klucz.
Rysunek 4.10. Wkładanie 9
W powyższym przykładzie przeprowadziliśmy różne porównania. Pierwsza wartość została bezpośrednio wstawiona do drzewa; następnie każdą wartość należało porównać z węzłami dostępnymi w tym drzewie. Złożoność czasowa operacji wstawiania do drzewa B zależy od liczby węzłów i .
Usuwanie operacji na drzewie B
Usunięcie elementu danych w drzewie B obejmuje trzy podstawowe zdarzenia:
- Przeszukanie węzła, w którym istnieje klucz do usunięcia,
- Usuwanie klucza i
- Jeśli to konieczne, zrównoważenie drzewa.
Podczas usuwania elementu z drzewa może wystąpić stan zwany niedomiarem. Niedomiar występuje, gdy węzeł składa się z mniejszej liczby kluczy niż minimalna; powinno trzymać.
Poniżej przedstawiono niektóre terminy, które należy zrozumieć przed wizualizacją operacji usuwania/usuwania:
Poniżej przedstawiono trzy najważniejsze przypadki operacji usuwania w drzewie B:
Przypadek 1: Usunięcie/Usunięcie klucza leży w węźle Liść - Przypadek ten dzieli się dalej na dwa różne przypadki:
1. Usunięcie/usunięcie klucza nie narusza właściwości minimalnej liczby kluczy, jaką powinien posiadać węzeł.
Zwizualizujmy ten przypadek na przykładzie, w którym usuniemy klucz 32 z poniższego drzewa B.
Rysunek 4.1: Usuwanie klucza węzła liścia (32) z drzewa B
Jak możemy zaobserwować, usunięcie 32 z tego drzewa nie narusza powyższej właściwości.
2. Usunięcie/usunięcie klucza narusza właściwość minimalnej liczby kluczy, jaką powinien posiadać węzeł. W tym przypadku musimy pożyczyć klucz od najbliższego węzła rodzeństwa w kolejności od lewej do prawej.
Najpierw odwiedzimy najbliższego lewicowego rodzeństwa. Jeśli węzeł lewego rodzeństwa ma więcej niż minimalną liczbę kluczy, pożyczy klucz z tego węzła.
W przeciwnym razie sprawdzimy pożyczkę z najbliższego prawego węzła rodzeństwa.
Zwizualizujmy teraz ten przypadek na przykładzie, w którym usuniemy 31 z powyższego Drzewa B. W tym przypadku pożyczymy klucz z lewego węzła rodzeństwa.
Rysunek 4.2: Usuwanie klucza węzła liścia (31) z drzewa B
Jeśli oba najbliższe węzły rodzeństwa składają się już z minimalnej liczby kluczy, wówczas połączymy węzeł z lewym lub prawym węzłem rodzeństwa. Ten proces łączenia odbywa się za pośrednictwem węzła nadrzędnego.
Wizualizujmy jeszcze raz, usuwając klucz 30 z powyższego Drzewa B.
Rysunek 4.3: Usuwanie klucza węzła liścia (30) z drzewa B
Ankita Dave
Przypadek 2: Usunięcie/usunięcie klucza leży w węźle innym niż Liść - Ten przypadek jest dalej podzielony na różne przypadki:
1. Węzeł inny niż liść/wewnętrzny, który zostanie usunięty, zostaje zastąpiony poprzednikiem w kolejności, jeśli lewy węzeł podrzędny ma więcej kluczy niż minimalna liczba.
Zwizualizujmy ten przypadek na przykładzie, w którym usuniemy klucz 33 z Drzewa B.
Rysunek 4.4: Usuwanie klucza węzła liścia (33) z drzewa B
2. Węzeł inny niż liść/wewnętrzny, który zostanie usunięty, zostaje zastąpiony następcą w kolejności, jeśli prawy węzeł podrzędny ma więcej kluczy niż minimalna liczba.
Jeśli którekolwiek dziecko ma minimalną liczbę kluczy, połączymy lewy i prawy węzeł podrzędny.
Zwizualizujmy ten przypadek usuwając klucz 30 z Drzewa B.
Rysunek 4.5: Usuwanie klucza węzła liścia (30) z drzewa B
Po połączeniu, jeśli węzeł nadrzędny ma mniej kluczy niż minimalna liczba kluczy, można szukać rodzeństwa, jak w Przypadek 1 .
Przypadek 3: W poniższym przypadku wysokość drzewa maleje. Jeśli klucz docelowy znajduje się w węźle wewnętrznym, a usunięcie klucza prowadzi do mniejszej liczby kluczy w węźle (czyli mniej niż wymagane minimum), poszukaj poprzednika w kolejności i następcy w kolejności. Jeśli oboje dzieci mają minimalną liczbę kluczy, pożyczanie nie może nastąpić. To prowadzi do Przypadek 2(3) , tj. scalanie węzłów podrzędnych.
Będziemy ponownie szukać rodzeństwa do pożyczenia klucza. Jeśli jednak rodzeństwo również składa się z minimalnej liczby kluczy, wówczas połączymy węzeł z rodzeństwem wraz z węzłem nadrzędnym i ułożymy węzły podrzędne zgodnie z wymaganiami (kolejność rosnąca).
Zwizualizujmy ten przypadek na przykładzie, w którym usuniemy element danych 10 z danego Drzewa B.
Rysunek 4.6: Usuwanie klucza węzła liścia (10) z drzewa B
Złożoność czasowa w powyższych przykładach różni się w zależności od lokalizacji, z której należy usunąć klucz. Zatem złożoność czasowa operacji usuwania w drzewie B wynosi O(log?n) .
Konkluzja
W tym samouczku dowiedzieliśmy się o drzewie B i zwizualizowaliśmy jego różne operacje na różnych przykładach. Zrozumieliśmy także pewne podstawowe właściwości i zasady Drzewa B.