B+ Tree jest rozszerzeniem B Tree, które umożliwia wydajne operacje wstawiania, usuwania i wyszukiwania.
W drzewie B klucze i rekordy mogą być przechowywane zarówno w węzłach wewnętrznych, jak i liściach. Podczas gdy w drzewie B+ rekordy (dane) mogą być przechowywane tylko w węzłach-liście, podczas gdy węzły wewnętrzne mogą przechowywać tylko wartości kluczy.
Węzły-liście drzewa B+ są ze sobą połączone w formie pojedynczo połączonych list, aby zwiększyć efektywność wyszukiwania.
B+ Tree służą do przechowywania dużej ilości danych, których nie można zapisać w pamięci głównej. Ze względu na to, że wielkość pamięci głównej jest zawsze ograniczona, węzły wewnętrzne (klucze dostępu do rekordów) drzewa B+ przechowywane są w pamięci głównej, natomiast węzły-liście są przechowywane w pamięci dodatkowej.
Nieprzezroczystość przejścia CSS
Wewnętrzne węzły drzewa B+ nazywane są często węzłami indeksowymi. Drzewo B+ rzędu 3 pokazano na poniższym rysunku.
Zalety drzewa B+
- Rekordy można pobierać przy równej liczbie dostępów do dysku.
- Wysokość drzewa pozostaje zrównoważona i mniejsza w porównaniu do drzewa B.
- Dostęp do danych zapisanych w drzewie B+ możemy uzyskać zarówno sekwencyjnie, jak i bezpośrednio.
- Klucze służą do indeksowania.
- Szybsze wyszukiwanie zapytań, ponieważ dane są przechowywane tylko w węzłach liści.
Drzewo B VS Drzewo B+
| SN | Drzewo B | B+ Drzewo |
|---|---|---|
| 1 | Klucze wyszukiwania nie mogą być zapisywane wielokrotnie. | Mogą występować nadmiarowe klucze wyszukiwania. |
| 2 | Dane mogą być przechowywane w węzłach liściowych, a także węzłach wewnętrznych | Dane mogą być przechowywane wyłącznie w węzłach liści. |
| 3 | Wyszukiwanie niektórych danych jest procesem wolniejszym, ponieważ dane można znaleźć zarówno w węzłach wewnętrznych, jak i w węzłach liściowych. | Wyszukiwanie jest stosunkowo szybsze, ponieważ dane można znaleźć tylko w węzłach liści. |
| 4 | Usuwanie węzłów wewnętrznych jest więc skomplikowane i czasochłonne. | Usuwanie nigdy nie będzie skomplikowanym procesem, ponieważ element będzie zawsze usuwany z węzłów liści. |
| 5 | Węzły liści nie mogą być ze sobą łączone. | Węzły liści są ze sobą połączone, aby zwiększyć efektywność operacji wyszukiwania. |
Wstawienie do drzewa B+
Krok 1: Wstaw nowy węzeł jako węzeł liścia
Krok 2: Jeśli liść nie ma wymaganego miejsca, podziel węzeł i skopiuj węzeł środkowy do następnego węzła indeksowego.
Krok 3: Jeśli węzeł indeksu nie ma wymaganego miejsca, podziel węzeł i skopiuj środkowy element na następną stronę indeksu.
Przykład :
Wstaw wartość 195 do drzewa B+ rzędu 5 pokazanego na poniższym rysunku.
znak do ciągu w Javie
Liczba 195 zostanie wstawiona w prawym poddrzewie liczby 120 po wartości 190. Wstaw ją w żądanym miejscu.
Węzeł zawiera większą liczbę elementów niż maksymalna, tj. 4, dlatego podziel go i umieść węzeł środkowy aż do elementu nadrzędnego.
pętla programu Java
Teraz węzeł indeksu zawiera 6 dzieci i 5 kluczy, co narusza właściwości drzewa B+, dlatego musimy go podzielić, jak pokazano poniżej.
Usunięcie w drzewie B+
Krok 1: Usuń klucz i dane z liści.
Krok 2: jeśli węzeł-liść zawiera mniej niż minimalna liczba elementów, połącz węzeł z jego rodzeństwem i usuń klucz znajdujący się pomiędzy nimi.
Krok 3: jeśli węzeł indeksu zawiera mniej niż minimalna liczba elementów, połącz węzeł z rodzeństwem i przesuń klucz w dół pomiędzy nimi.
Przykład
Usuń klucz 200 z drzewa B+ pokazanego na poniższym rysunku.
Liczba 200 jest obecna w prawym poddrzewie liczby 190, po liczbie 195. Usuń ją.
Połącz dwa węzły, używając liczb 195, 190, 154 i 129.
Teraz element 120 jest pojedynczym elementem obecnym w węźle, który narusza właściwości drzewa B+. Dlatego musimy go scalić, używając 60, 78, 108 i 120.
Teraz wysokość drzewa B+ zostanie zmniejszona o 1.
długi format ciągu Java
