Co to jest drzewo B +?
B + drzewa jest wykorzystywana przede wszystkim do realizacji dynamicznego indeksowanie na wielu poziomach. W porównaniu do B-Tree, B + Tree przechowuje wskaźniki danych tylko w węzłach liści drzewa, co sprawia, że wyszukiwanie jest dokładniejsze i szybsze.
W tym samouczku B + Tree dowiesz się:
- Co to jest drzewo B +?
- Reguły dla drzewa B +
- Dlaczego warto korzystać z B + Tree
- Drzewo B + kontra Drzewo B.
- Operacja wyszukiwania
- Operacja wstawiania
- Usuń operację
Reguły dla drzewa B +
Oto podstawowe zasady dotyczące B + Tree.
- Liście służą do przechowywania rekordów danych.
- Jest przechowywany w wewnętrznych węzłach drzewa.
- Jeśli wartość klucza docelowego jest mniejsza niż węzeł wewnętrzny, to następuje punkt znajdujący się po jego lewej stronie.
- Jeśli wartość klucza docelowego jest większa lub równa węzłowi wewnętrznemu, to następuje punkt znajdujący się po jego prawej stronie.
- Korzeń ma co najmniej dwoje dzieci.
Dlaczego warto korzystać z B + Tree
Oto powody, dla których warto używać B + Tree:
- Klucze są używane głównie do wspomagania poszukiwań, kierując je do właściwego Liścia.
- B + Tree używa „współczynnika wypełnienia” do zarządzania wzrostem i spadkiem drzewa.
- W drzewach B + wiele kluczy można łatwo umieścić na stronie pamięci, ponieważ nie mają one danych powiązanych z węzłami wewnętrznymi. W związku z tym szybko uzyska dostęp do danych drzewa, które znajdują się w węźle liścia.
- Kompleksowe pełne skanowanie wszystkich elementów to drzewo, które wymaga tylko jednego przejścia liniowego, ponieważ wszystkie węzły liści drzewa B + są ze sobą połączone.
Drzewo B + kontra Drzewo B.
Oto główne różnice między drzewem B + a drzewem B.
| Drzewo B + | Drzewo B. |
| Klawisze wyszukiwania można powtórzyć. | Klucze wyszukiwania nie mogą być nadmiarowe. |
| Dane są zapisywane tylko w węzłach liści. | Zarówno węzły-liście, jak i węzły wewnętrzne mogą przechowywać dane |
| Dane przechowywane w węźle liścia sprawiają, że wyszukiwanie jest dokładniejsze i szybsze. | Wyszukiwanie jest powolne z powodu danych przechowywanych w Liście i węzłach wewnętrznych. |
| Usunięcie nie jest trudne, ponieważ element jest usuwany tylko z węzła liścia. | Usuwanie elementów to skomplikowany i czasochłonny proces. |
| Połączone węzły liści sprawiają, że wyszukiwanie jest wydajne i szybkie. | Nie możesz łączyć węzłów liści. |
Operacja wyszukiwania
W B + Tree wyszukiwanie jest jedną z najłatwiejszych procedur do wykonania i uzyskania szybkich i dokładnych wyników.
Zastosowanie ma następujący algorytm wyszukiwania:
- Aby znaleźć wymagany rekord, musisz przeprowadzić wyszukiwanie binarne na dostępnych rekordach w drzewie.
- W przypadku dokładnego dopasowania do klucza wyszukiwania odpowiedni rekord jest zwracany użytkownikowi.
- W przypadku, gdy podczas wyszukiwania w węźle nadrzędnym, bieżącym lub liścia nie zostanie znaleziony dokładny klucz, użytkownikowi zostanie wyświetlony komunikat „nie znaleziono”.
- Proces wyszukiwania można powtórzyć, aby uzyskać lepsze i dokładniejsze wyniki.
Algorytm operacji wyszukiwania
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
Dane wyjściowe :
Dopasowany rekord ustawiony względem dokładnego klucza jest wyświetlany użytkownikowi; w przeciwnym razie użytkownikowi zostanie wyświetlona nieudana próba.
Operacja wstawiania
Do operacji wstawiania ma zastosowanie następujący algorytm:
- 50 procent elementów w węzłach jest przenoszonych do nowego liścia w celu przechowywania.
- Rodzic nowego liścia jest dokładnie powiązany z minimalną wartością klucza i nową lokalizacją w drzewie.
- Podziel węzeł nadrzędny na więcej lokalizacji na wypadek, gdyby został w pełni wykorzystany.
- Teraz, aby uzyskać lepsze wyniki, klucz środkowy jest powiązany z węzłem najwyższego poziomu tego liścia.
- Dopóki węzeł najwyższego poziomu nie zostanie znaleziony, kontynuuj iterację procesu wyjaśnionego w powyższych krokach.
Algorytm operacji wstawiania
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. Else, divide the node into more locations to fit more records.a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the treeb. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.c. Divide the top-level node if it gets full of keys and addresses.i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore.3) Build a new top-level root node of 1 Key and 2 indicators.
Dane wyjściowe :
Algorytm określi element i pomyślnie wstawi go do wymaganego węzła liścia.
Powyższy przykładowy przykład B + Tree jest wyjaśniony w poniższych krokach:
- Po pierwsze mamy 3 węzły, a pierwsze 3 elementy, czyli 1, 4 i 6, są dodawane w odpowiednich miejscach w węzłach.
- Następną wartością w serii danych jest 12, które należy uczynić częścią drzewa.
- Aby to osiągnąć, podziel węzeł, dodaj 6 jako element wskaźnika.
- Teraz tworzona jest prawostronna hierarchia drzewa, a pozostałe wartości danych są odpowiednio dostosowywane, pamiętając o obowiązujących regułach równych lub większych niż wartości względem węzłów klucz-wartość po prawej stronie.
Usuń operację
Złożoność procedury usuwania w B + Tree przewyższa złożoność funkcji wstawiania i wyszukiwania.
Podczas usuwania elementu z drzewa B + ma zastosowanie następujący algorytm:
- Po pierwsze, musimy zlokalizować wpis liścia w drzewie, który zawiera klucz i wskaźnik. , usuń wpis liścia z Drzewa, jeśli Liść spełnia dokładne warunki usunięcia rekordu.
- W przypadku gdy węzeł liścia spełnia tylko zadowalający współczynnik zapełnienia w połowie, operacja jest zakończona; w przeciwnym razie węzeł Liść ma minimalne wpisy i nie można go usunąć.
- Inne połączone węzły po prawej i lewej stronie mogą opuścić dowolne wpisy, a następnie przenieść je do Liścia. Jeśli te kryteria nie są spełnione, powinny połączyć węzeł liścia i powiązany z nim węzeł w hierarchii drzewa.
- Po połączeniu węzła liścia z jego sąsiadami po prawej lub lewej stronie, wpisy wartości w węźle liścia lub w połączonym sąsiedzie wskazującym na węzeł najwyższego poziomu są usuwane.
Powyższy przykład ilustruje procedurę usuwania elementu z drzewa B + o określonej kolejności.
- Po pierwsze, dokładne lokalizacje usuwanego elementu są określone w drzewie.
- Tutaj element do usunięcia można dokładnie zidentyfikować tylko na poziomie liścia, a nie w miejscu indeksu. W związku z tym element można usunąć bez wpływu na zasady usuwania, czyli wartość klucza minimum.
- W powyższym przykładzie musimy usunąć 31 z drzewa.
- Musimy zlokalizować wystąpienia 31 w indeksie i liście.
- Widzimy, że 31 jest dostępne zarówno na poziomie węzła indeksu, jak i liścia. Dlatego usuwamy go z obu instancji.
- Ale musimy wypełnić indeks wskazujący na 42. Przyjrzymy się teraz właściwemu dziecku poniżej 25 roku życia, weźmiemy wartość minimalną i umieścimy ją jako indeks. Zatem 42 jako jedyna obecna wartość stanie się indeksem.
Usuń algorytm operacji
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) If n has at least ceil(m/2) keys, done!ii) If n has less than ceil(m/2) keys,If a sibling can lend a key,Borrow key from the sibling and adjust keys in n and the parent nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node
Dane wyjściowe :
Klucz „K” jest usuwany, a klucze są pożyczane od rodzeństwa w celu dostosowania wartości w n i jego węzłów nadrzędnych, jeśli to konieczne.
Podsumowanie:
- B + Tree to samobalansująca się struktura danych do wykonywania dokładnego i szybszego wyszukiwania, wstawiania i usuwania procedur na danych
- Możemy łatwo odzyskać pełne lub częściowe dane, ponieważ przeglądanie połączonej struktury drzewa sprawia, że jest to wydajne.
- Struktura drzewa B + rośnie i kurczy się wraz ze wzrostem / spadkiem liczby przechowywanych rekordów.
- Przechowywanie danych w węzłach liści i późniejsze rozgałęzianie węzłów wewnętrznych ewidentnie skraca wysokość drzewa, co zmniejsza operacje wejścia i wyjścia dysku, ostatecznie zajmując znacznie mniej miejsca na urządzeniach pamięci masowej.