b tree b tree data structure c
Ten samouczek języka C ++ wyjaśnia struktury danych B Tree i B + Tree. Służą do przechowywania danych na dyskach, gdy całych danych nie można zapisać w pamięci głównej:
B-drzewo jest samo-zrównoważonym drzewem, a także wyspecjalizowanym drzewem m-way używanym do dostępu do dysku.
Gdy ilość danych do zapisania jest bardzo duża, nie możemy przechowywać całych danych w pamięci głównej. Dlatego przechowujemy dane na dysku. Dostęp do danych z dysku zajmuje więcej czasu w porównaniu z dostępem do pamięci głównej.
Gdy liczba kluczy danych przechowywanych na dyskach jest bardzo duża, dostęp do danych jest zwykle uzyskiwany w postaci bloków. Czas dostępu do tych bloków jest wprost proporcjonalny do wysokości drzewa.
=> Kliknij tutaj, aby zapoznać się z serią szkoleń Absolute C ++.
Czego się nauczysz:
B-Tree w C ++
Drzewo B to drzewo płaskie, co oznacza, że wysokość drzewa B jest ograniczona do minimum. Zamiast tego, tyle kluczy jest umieszczanych w każdym węźle B-drzewa. Dzięki utrzymaniu minimalnej wysokości drzewa B dostęp jest szybszy w porównaniu z innymi zrównoważonymi drzewami, takimi jak drzewa AVL.
Poniżej przedstawiono typowe drzewo B:
bezpłatna aplikacja z kartą czasu na iPhone'a i Androida
Ogólnie rozmiar węzła w B-drzewie jest taki sam, jak rozmiar bloku.
Poniżej wymienione są niektóre właściwości B-Tree.
- Wszystkie liście drzewa B są na tym samym poziomie.
- B-drzewo rzędu m może mieć maksymalnie m-1 kluczy i m dzieci.
- Każdy węzeł w B-drzewie ma co najwyżej m dzieci.
- Węzeł główny musi mieć co najmniej dwa węzły.
- Każdy węzeł z wyjątkiem węzła głównego i węzła liścia zawiera m / 2 dzieci.
Następnie omówimy niektóre z podstawowych operacji B-drzewa.
Podstawowe operacje B-Tree
Poniżej podano niektóre z podstawowych operacji B-Tree.
# 1) Wyszukiwanie
Wyszukiwanie w drzewie B jest podobne do wyszukiwania w BST. W powyższym drzewie, jeśli chcemy odszukać pozycję 3, postępujemy w następujący sposób:
- Porównaj 3 z elementami głównymi. Tutaj 3<6 and 3 <15. So we proceed to the left subtree.
- Porównaj 3 z 4 w lewym poddrzewie. Jak 3<4, we proceed to the left subtree of node 4.
- Następny węzeł ma dwa klucze, 2 i 3. 3> 2, podczas gdy 3 = 3. Więc znaleźliśmy klucz w tym węźle. Wróć do znalezionej lokacji.
Wyszukiwanie w drzewie B zależy od wysokości drzewa. Zazwyczaj wyszukanie danego elementu zajmuje O (log n) czasu.
# 2) Wstawianie
Wstawienie nowego elementu do drzewa B odbywa się na poziomie węzłów liści.
Poniżej znajduje się sekwencja kroków (algorytm) wstawiania nowego elementu do drzewa B.
- Przejdź przez drzewo B, aby znaleźć miejsce w węzłach liści, aby wstawić element.
- Jeśli węzeł liścia zawiera klucze
- W przeciwnym razie, jeśli klucze węzła liścia = m-1, to:
- Wstaw nowy element w coraz większej liczbie elementów.
- Weź medianę węzłów i podziel węzeł na dwa węzły.
- Wypchnij medianę do jej węzła nadrzędnego.
- Jeśli klucz węzła nadrzędnego = m-1, powtórz powyższe kroki również dla węzła nadrzędnego. Dzieje się tak, dopóki nie znajdziemy odpowiedniego węzła liścia.
- Na koniec wstaw element.
- W przeciwnym razie, jeśli klucze węzła liścia = m-1, to:
Zademonstrowaliśmy wstawianie w drzewie B w następujący sposób.
Umieśćmy element 70 w drzewie pokazanym poniżej.
do czego służy C ++
Podane drzewo ma minimalny stopień „m” = 3. W związku z tym każdy węzeł może pomieścić w nim 2 * m -1 = 5 kluczy.
Teraz wstawiamy element 70. Ponieważ możemy mieć 5 kluczy w węźle, porównujemy element 70 z elementem głównym 30. Od 70> 30 wstawimy element 70 do prawego poddrzewa.
W prawym poddrzewie mamy węzeł z kluczami 40, 50, 60. Ponieważ każdy węzeł może mieć 5 kluczy, wstawimy element 70 do samego tego węzła.
Po wstawieniu B-Tree wygląda następująco.
# 3) Usunięcie
Podobnie jak w przypadku wstawiania, usuwanie klucza odbywa się również na poziomie węzłów liści. Ale w przeciwieństwie do wstawiania usuwanie jest bardziej skomplikowane. Klucz do usunięcia może być węzłem liścia lub węzłem wewnętrznym.
Aby usunąć klucz, postępujemy zgodnie z poniższą sekwencją kroków (algorytm).
1. Zlokalizuj węzeł liścia.
dwa. W przypadku, gdy liczba kluczy w węźle> m / 2, usuń dany klucz z węzła.
3. W przypadku, gdy węzeł liścia nie ma m / 2 kluczy, musimy uzupełnić klucze, pobierając klucze z prawego lub lewego poddrzewa, aby zachować drzewo B.
Wykonujemy następujące kroki:
- Jeśli lewe poddrzewo zawiera m / 2 elementów, to przesuwamy jego największy element do węzła nadrzędnego, a następnie przenosimy element pośredni w miejsce, w którym klucz został usunięty.
- Jeśli prawe poddrzewo zawiera m / 2 elementów, to wypychamy jego najmniejszy element do węzła nadrzędnego, a następnie przenosimy element pośredni w miejsce, w którym klucz został usunięty.
Cztery. Jeśli żaden węzeł nie ma m / 2 węzłów, powyższe kroki nie mogą być wykonane, dlatego tworzymy nowy węzeł-liść, łącząc dwa węzły-liście i element pośredniczący węzła nadrzędnego.
5. Jeśli rodzic nie ma m / 2 węzłów, powtarzamy powyższe kroki dla danego węzła nadrzędnego. Te kroki są powtarzane, aż otrzymamy zrównoważone drzewo B.
Poniżej przedstawiono ilustrację usuwania węzła z drzewa B.
Rozważ jeszcze raz następujące drzewo B.
jaka jest faza analizy w sdlc
Załóżmy, że chcemy usunąć klucz 60 z drzewa B. Jeśli sprawdzimy drzewo B, możemy stwierdzić, że klucz do usunięcia znajduje się w węźle liścia. Usuwamy klucz 60 z tego węzła-liścia.
Teraz drzewo będzie wyglądać tak, jak pokazano poniżej:
Możemy zauważyć, że po usunięciu klucza 60 węzeł liścia drzewa B spełnia wymagane właściwości i nie musimy już więcej modyfikować drzewa B.
Gdybyśmy jednak musieli usunąć klucz 20, tylko klucz 10 pozostałby w lewym węźle liścia. W takim przypadku musielibyśmy przesunąć korzeń 30 do węzła liścia i przenieść klucz 40 do korzenia.
Dlatego podczas usuwania klucza z drzewa B należy zachować ostrożność i nie naruszać właściwości drzewa B.
Przechodzenie w drzewie B.
Przemieszczanie w drzewie B jest również podobne do przechodzenia w kolejności w BST. Rozpoczynamy rekurencyjnie od lewej strony, następnie dochodzimy do korzenia i przechodzimy do lewego poddrzewa.
Zastosowania drzew B.
- Drzewa B są używane do indeksowania danych, zwłaszcza w dużych bazach danych, ponieważ dostęp do danych przechowywanych w dużych bazach danych na dyskach jest bardzo czasochłonny.
- Wyszukiwanie danych w większych, nieposortowanych zestawach danych zajmuje dużo czasu, ale można to znacznie poprawić dzięki indeksowaniu przy użyciu drzewa B.
Drzewo B + w C ++
Drzewo B + jest rozszerzeniem drzewa B. Różnica w drzewie B + i B polega na tym, że w drzewie B klucze i rekordy mogą być przechowywane zarówno jako węzły wewnętrzne, jak i jako liście, podczas gdy w drzewach B + rekordy są przechowywane jako węzły liści, a klucze są przechowywane tylko w węzłach wewnętrznych.
Rekordy są połączone ze sobą w postaci połączonej listy. Dzięki takiemu rozwiązaniu wyszukiwanie drzew B + jest szybsze i wydajniejsze. Węzły wewnętrzne drzewa B + nazywane są węzłami indeksowymi.
Drzewa B + mają dwa rzędy, tj. Jeden dla węzłów wewnętrznych, a drugi dla liści lub węzłów zewnętrznych.
Przykład drzewa B + pokazano poniżej.
Ponieważ drzewo B + jest rozszerzeniem B-drzewa, podstawowe operacje, które omówiliśmy w temacie B-drzewo, nadal są aktualne.
Podczas wstawiania i usuwania powinniśmy zachować podstawowe właściwości drzew B + nienaruszone. Jednak operacja usuwania w drzewie B + jest stosunkowo łatwiejsza, ponieważ dane są przechowywane tylko w węzłach liści i zawsze będą usuwane z węzłów liści.
Zalety drzew B +
- Możemy pobierać rekordy z taką samą liczbą dostępów do dysku.
- W porównaniu z drzewem B wysokość drzewa B + jest mniejsza i pozostaje zrównoważona.
- Używamy kluczy do indeksowania.
- Dostęp do danych w drzewie B + można uzyskać sekwencyjnie lub bezpośrednio, ponieważ węzły liści są ułożone na połączonej liście.
- Wyszukiwanie jest szybsze, ponieważ dane są przechowywane tylko w węzłach liści i jako połączona lista.
Różnica między drzewem B i drzewem B +
B-Tree | Drzewo B + |
---|---|
Dane są przechowywane w węzłach liści, a także w węzłach wewnętrznych. | Dane są przechowywane tylko w węzłach liści. |
Wyszukiwanie jest nieco wolniejsze, ponieważ dane są przechowywane zarówno w węzłach wewnętrznych, jak i w węzłach liści. | Wyszukiwanie jest szybsze, ponieważ dane są przechowywane tylko w węzłach liści. |
Brak dodatkowych kluczy wyszukiwania. | Mogą być obecne nadmiarowe klucze wyszukiwania. |
Operacja usuwania jest złożona. | Operacja usuwania jest łatwa, ponieważ dane można bezpośrednio usunąć z węzłów liści. |
Węzłów liści nie można łączyć ze sobą. | Węzły liści są połączone ze sobą, tworząc połączoną listę. |
Wniosek
W tym samouczku szczegółowo omówiliśmy drzewo B i drzewo B +. Te dwie struktury danych są używane, gdy jest bardzo dużo danych i gdy nie można przechowywać całych danych w pamięci głównej. Zatem do przechowywania danych na dyskach używamy drzewa B-drzewa i B + drzewa.
Przeszukiwanie B-drzewa jest nieco wolniejsze, ponieważ dane są przechowywane w węzłach wewnętrznych, a także w węzłach liści. B + drzewo jest rozszerzeniem B-drzewa, a dane tutaj są przechowywane tylko w węzłach liści. Z tego powodu wyszukiwanie w drzewie B + jest szybsze i wydajne.
=> Odwiedź tutaj, aby zapoznać się z pełną listą samouczków języka C ++.
rekomendowane lektury
- Struktura danych drzewa AVL i sterty w C ++
- Struktura danych listy połączonej w C ++ z ilustracją
- Struktura danych kolejki w C ++ z ilustracjami
- Struktura danych stosu w C ++ z ilustracjami
- Struktura danych listy połączonej cyklicznie w C ++ z ilustracją
- Wprowadzenie do struktur danych w C ++
- Struktura danych kolejki priorytetowej w C ++ z ilustracjami
- Struktura danych listy podwójnie połączonych w C ++ z ilustracjami