B+ DRZEWO: Wyszukaj, wstaw i usuń OperaPrzykład

Co to jest drzewo B+?

A B+ Drzewo jest wykorzystywany głównie do implementacji dynamicznego indeksowania na wielu poziomach. W porównaniu do B-Tree, B+ Tree przechowuje wskaźniki danych tylko w węzłach liściowych drzewa, co sprawia, że ​​wyszukiwanie jest dokładniejsze i szybsze.

Zasady dla drzewa B+

Oto podstawowe zasady 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, wówczas podążany jest punkt znajdujący się tuż po jego lewej stronie.
• Jeśli wartość klucza docelowego jest większa lub równa węzłowi wewnętrznemu, wówczas podążany jest punkt 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ć B+ Tree:

• Klucze są wykorzystywane przede wszystkim w celu ułatwienia wyszukiwania poprzez wskazanie właściwego liścia.
• B+ Tree wykorzystuje „współczynnik wypełnienia” do zarządzania wzrostem i spadkiem drzewa.
• 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.
• 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

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.	Zarówno węzły liściowe, 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.	Przeszukiwanie jest powolne ze względu na dane przechowywane w węzłach Leaf i wewnętrznych.
Usunięcie nie jest trudne, ponieważ element jest usuwany 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 B+ Tree wyszukiwanie jest jedną z najłatwiejszych do wykonania procedur, dzięki której można uzyskać szybkie i dokładne wyniki.

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

Wydajność:

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.
• 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 jego pełnego wykorzystania.
• Teraz, aby uzyskać lepsze wyniki, środkowy klawisz jest powiązany z węzłem najwyższego poziomu tego Liścia.
• Dopóki nie zostanie znaleziony węzeł najwyższego poziomu, kontynuuj proces wyjaśniony w powyższych krokach.

wstawka OperaAlgorytm

1.	Even 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.  

Wydajność:

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:

• Po pierwsze, mamy 3 węzły i 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óra musi zostać włączona do Drzewa.
• Aby to osiągnąć, podziel węzeł, dodaj 6 jako element wskaźnikowy.
• Teraz tworzona jest prawa hierarchia drzewa, a pozostałe wartości danych są odpowiednio dostosowywane, pamiętając o obowiązujących zasadach wartości równych lub większych niż względem węzłów klucz-wartość po prawej stronie.

Usuń 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+:

• Po pierwsze, musimy zlokalizować wpis liścia w Drzewie, który zawiera klawisz i wskaźnik. , usuń wpis liścia z Drzewa, jeśli Liść spełnia dokładnie warunki usunięcia rekordu.
• Jeśli węzeł liścia spełnia tylko warunek bycia w połowie zapełnionym, operacja zostaje zakończona; w przeciwnym razie węzeł liścia ma minimalną liczbę wpisów i nie może zostać usunięty.
• 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żeli te kryteria nie są spełnione, należy połączyć węzeł liścia i węzeł z nim połączony 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 połączonym sąsiedzie wskazującym na węzeł najwyższego poziomu są usuwane.

Powyższy przykład ilustruje procedurę usunięcia elementu z Drzewa B+ konkretnego zamówienia.

• Najpierw w drzewie identyfikowane są dokładne lokalizacje elementu do usunięcia.
• W tym przypadku element do usunięcia można dokładnie zidentyfikować jedynie na poziomie liścia, a nie na miejscu indeksu. Zatem element można usunąć bez wpływu na zasady usuwania, czyli wartość klucza minimalnego.

• W powyższym przykładzie musimy usunąć 31 z drzewa.
• Musimy zlokalizować instancje 31 w Indeksie i Liściu.
• Widzimy, że 31 jest dostępne zarówno na poziomie węzła Indeks, jak i Liść. Dlatego usuwamy go z obu instancji.
• Musimy jednak wypełnić indeks wskazujący 42. Przyjrzymy się teraz właściwemu dziecku w wieku poniżej 25 lat, przyjmiemy minimalną wartość i umieścimy ją jako indeks. Zatem, ponieważ 42 jest jedyną obecną wartością, stanie się indeksem.

Usuń OperaAlgorytm

1) Start at the root and go up to 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

Wydajność:

Klucz „K” jest usuwany, a klucze są pożyczane od rodzeństwa w celu dostosowania wartości w n i jego węzłach nadrzędnych, jeśli to konieczne.

Podsumowanie

• B+ Tree jest samobalansujący struktura danych do wykonywania dokładnych i szybszych procedur wyszukiwania, wstawiania i usuwania danych
• Możemy łatwo odzyskać pełne dane 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 na węzłach liściowych i późniejsze rozgałęzianie węzłów wewnętrznych wyraźnie skraca wysokość drzewa, co z kolei redukuje liczbę operacji wejścia i wyjścia na dysku, ostatecznie zużywając znacznie mniej miejsca na urządzeniach pamięci masowej.