B+ TREE: wyszukiwanie, wstawianie i usuwanie Operanych
Sara Chen
⚡ Inteligentne podsumowanie
Drzewo B+ to wielopoziomowy, dynamiczny indeks, który przechowuje wskaźniki danych tylko w połączonych węzłach liściowych, co zapewnia dokładność i szybkość wyszukiwania. Obejmuje on reguły drzewa B+, różnice między nim a drzewem B oraz operacje wyszukiwania, wstawiania i usuwania.
Co to jest drzewo B+?
A B+ Drzewo Jest wykorzystywany głównie do implementacji dynamicznego indeksowania na wielu poziomach. W porównaniu z drzewem B, drzewo B+ przechowuje wskaźniki danych tylko w węzłach liściowych drzewa, co sprawia, że proces wyszukiwania jest dokładniejszy i szybszy.
Zasady dla drzewa B+
Poniżej przedstawiono podstawowe zasady drzewa B+.
- Liście służą do przechowywania rekordów danych.
- Rekordy przechowywane są w wewnętrznych węzłach drzewa.
- Jeśli wartość klucza docelowego jest mniejsza niż wartość węzła wewnętrznego, wówczas podążany jest wskaźnik znajdujący się tuż po jego lewej stronie.
- Jeśli wartość klucza docelowego jest większa lub równa wartości węzła wewnętrznego, wówczas podążany jest wskaźnik znajdujący się tuż po jego prawej stronie.
- Korzeń ma co najmniej dwójkę dzieci.
Dlaczego warto używać drzewa B+
Oto powody, dla których warto używać drzewa B+:
- Klucze służą przede wszystkim do ułatwienia wyszukiwania poprzez wskazanie właściwego arkusza.
- Drzewo B+ wykorzystuje „współczynnik wypełnienia” do zarządzania przyrostem i ubytkiem w drzewie.
- W drzewach B+ na stronie pamięci można łatwo umieścić wiele kluczy, gdyż nie posiadają one danych powiązanych z węzłami wewnętrznymi. Dzięki temu szybko uzyska dostęp do danych drzewa znajdujących się w węźle liścia.
- Do pełnego skanowania wszystkich elementów potrzebny jest tylko jeden przebieg liniowy, ponieważ wszystkie węzły liściowe drzewa B+ są ze sobą połączone.
Drzewo B+ kontra drzewo B
Oto główne różnice między drzewem B+ a drzewem B.
| B+ Drzewo | Drzewo B |
|---|---|
| Klucze wyszukiwania można powtarzać. | Klucze wyszukiwania nie mogą być zbędne. |
| Dane są zapisywane tylko w węzłach liści. | Dane mogą być przechowywane zarówno w węzły liściowe, jak i węzły wewnętrzne. |
| Dane przechowywane w węźle liścia sprawiają, że wyszukiwanie jest dokładniejsze i szybsze. | Przeszukiwanie jest powolne ze względu na dane przechowywane na liściach i węzłach wewnętrznych. |
| Usunięcie nie jest trudne, ponieważ element usuwa się tylko z węzła liścia. | Usuwanie elementów jest procesem skomplikowanym i czasochłonnym. |
| Połączone węzły liści sprawiają, że wyszukiwanie jest wydajne i szybkie. | Nie można łączyć węzłów liści. |
Szukaj Operacja
W drzewie B+ wyszukiwanie jest jedną z najłatwiejszych procedur do wykonania, a jej wyniki są szybkie i dokładne.
Można zastosować następujący algorytm wyszukiwania:
- Aby znaleźć wymagany rekord, należy wykonać polecenie 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 nie uda się znaleźć dokładnego klucza w węźle nadrzędnym, bieżącym lub potomnym, użytkownikowi zostanie wyświetlony komunikat „nie znaleziono”.
- Proces wyszukiwania można powtórzyć, aby uzyskać lepsze i dokładniejsze wyniki.
Szukaj OperaAlgorytm
1. Call the binary search method on the records in the B+ Tree. 2. If the search parameters match the exact key The accurate result is returned and displayed to the user Else, if the node being searched is the current and the exact key is not found by the algorithm Display the statement "Recordset cannot be found."
Wyjście: Użytkownikowi wyświetlany jest zestaw rekordów dopasowanych do dokładnego klucza; w przeciwnym razie użytkownikowi wyświetla się informacja o nieudanej próbie.
wstawka Operacja
Poniższy algorytm ma zastosowanie do operacji wstawiania:
- 50 procent elementów w węzłach jest przenoszonych do nowego liścia w celu przechowywania.
- Element nadrzędny 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 jego pełnego wykorzystania.
- Teraz, aby uzyskać lepsze wyniki, klucz środkowy jest skojarzony z węzłem najwyższego poziomu danego liścia.
- Dopóki nie zostanie znaleziony węzeł najwyższego poziomu, kontynuuj proces wyjaśniony w powyższych krokach.
wstawka OperaAlgorytm
1. If inserting at least 1 entry into the leaf container does not make it full, then add the record. 2. 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 tree. b. 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.
Wyjście: Algorytm określi element i pomyślnie wstawi go w wymaganym węźle liścia.
Powyższy przykładowy przykład drzewa B+ wyjaśniono w poniższych krokach:
- Najpierw mamy 3 węzły, a pierwsze 3 elementy, czyli 1, 4 i 6, dodajemy w odpowiednich miejscach węzłów.
- Następną wartością w serii danych jest 12, którą należy umieścić w Drzewie.
- Aby to osiągnąć, podziel węzeł i dodaj 6 jako element wskaźnikowy.
- Teraz tworzona jest prawa hierarchia drzewa, a pozostałe wartości danych są odpowiednio dostosowywane przez keeping mając na uwadze obowiązujące zasady wartości równych lub większych od węzłów klucz-wartość po prawej stronie.
Usunięcia Operacja
Złożoność procedury usuwania w drzewie B+ przewyższa złożoność funkcji wstawiania i wyszukiwania.
Poniższy algorytm można zastosować podczas usuwania elementu z drzewa B+:
- Najpierw musimy zlokalizować wpis liścia w drzewie, który zawiera klucz i wskaźnik, a następnie usunąć wpis liścia z drzewa, jeśli liść spełnia dokładne warunki usunięcia rekordu.
- W przypadku gdy węzeł liściowy spełnia jedynie warunek bycia zapełnionym w połowie, operacja zostaje zakończona; w przeciwnym wypadku węzeł liściowy ma minimalną liczbę wpisów i nie może zostać usunięty.
- Pozostałe połączone węzły po prawej i lewej stronie mogą zwolnić 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 jego węzeł połączony w hierarchii drzewa.
- Po scaleniu węzła liścia z jego sąsiadami po prawej lub lewej stronie, wpisy wartości w węźle liścia lub powiązanym sąsiedzie wskazujące na węzeł najwyższego poziomu zostają usunięte.
Powyższy przykład ilustruje procedurę usuwania elementu z drzewa B+ o określonym rzędzie.
- Najpierw w drzewie identyfikowane są dokładne lokalizacje elementu do usunięcia.
- W tym przypadku element do usunięcia można precyzyjnie zidentyfikować tylko na poziomie liścia, a nie na podstawie indeksu. W związku z tym element można usunąć bez naruszania reguł usuwania, czyli wartości klucza minimalnego.
- W powyższym przykładzie musimy usunąć 31 z drzewa.
- Musimy zlokalizować wystąpienia 31 w indeksie i liściu.
- Widzimy, że 31 jest dostępne zarówno na poziomie węzła indeksowego, jak i węzła liściowego. Dlatego usuwamy je z obu instancji.
- Musimy jednak uzupełnić indeks wskazujący na 42. Teraz przyjrzymy się odpowiedniemu dziecku poniżej 25 roku życia i weźmiemy minimalną wartość, którą ustawimy jako indeks. Zatem, ponieważ 42 jest jedyną obecną wartością, stanie się ona indeksem.
Usunięcia OperaAlgorytm
1) Start at the root and go up to the leaf node containing the key K. 2) Find the node n on the path from the root to the leaf node containing K. A. If n is root, remove K a. if root has more than one key, done b. if root has only K i) if any of its child nodes can lend a node Borrow key from the child and adjust child links ii) Otherwise merge the children nodes. It will be a new root c. If n is an internal node, remove K i) 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 node Adjust child links Else Merge n with its sibling Adjust child links d. If n is a leaf node, remove K i) If n has at least ceil(M/2) elements, done! In case the smallest key is deleted, push up the next key ii) If n has less than ceil(m/2) elements If the sibling can lend a key Borrow key from a sibling and adjust keys in n and its parent node Else Merge n and its sibling Adjust keys in the parent node
Wyjście: Klucz „K” zostaje usunięty, a w razie potrzeby klucze zostają pożyczone od węzłów pokrewnych w celu dostosowania wartości w n i jego węzłach nadrzędnych.
