Kluczowa różnica: w komputerach drzewa binarne są strukturami danych drzewa, które przechowują dane i umożliwiają użytkownikowi dostęp, wyszukiwanie, wstawianie i usuwanie danych w czasie algorytmu. Różnica między drzewem B i B + polega na tym, że w drzewie B klucze i dane mogą być przechowywane zarówno w węzłach wewnętrznych, jak iw liściach, podczas gdy w drzewie B + dane i klucze mogą być przechowywane tylko w węzłach liści .
Drzewa binarne są zbalansowanymi drzewami wyszukiwania, które zaprojektowano tak, aby dobrze działały na urządzeniach pamięci masowej o bezpośrednim dostępie, takich jak dyski magnetyczne. Rudolf Bayer i Ed McCreight wymyślili koncepcję drzewa B-tree.
Drzewo B jest uogólnionym binarnym drzewem wyszukiwania, w którym każdy węzeł może mieć więcej niż dwoje dzieci. Każdy wewnętrzny węzeł w drzewie B zawiera pewną liczbę kluczy. Te klucze dzielą wartości i dalej tworzą pod-drzewa. Wewnętrzne węzły w drzewie B mogą mieć zmienną liczbę węzłów potomnych, które są rozmieszczone w predefiniowanym zakresie. W momencie wstawienia lub usunięcia danych z dowolnego odpowiedniego węzła następuje zmiana liczby węzłów potomnych. Aby zachować wstępnie zdefiniowany zakres, węzły wewnętrzne mogą być łączone lub dzielone. W drzewie B dozwolony jest zakres węzłów podrzędnych, dzięki czemu należy zachować zdefiniowany wcześniej zakres.
Drzewa B nie muszą być często równoważone, w przeciwieństwie do innych drzewek wyszukiwania równoważenia. Węzły w tych drzewach nie zawsze są pełne; w związku z tym przestrzenie te są niepotrzebne w tych drzewach, prowadząc do marnotrawienia przestrzeni. Jedynie dolna i górna granica liczby węzłów potomnych są zazwyczaj ustalone dla konkretnej implementacji. Na przykład w drzewie 2-3 B (często nazywanym po prostu drzewkiem 2-3) każdy węzeł wewnętrzny może mieć tylko 2 lub 3 węzły potomne.
Dodatkowo drzewo B jest zoptymalizowane pod kątem systemów, które odczytują i zapisują duże bloki danych. Jest powszechnie stosowany w bazach danych i systemach plików. W drzewie B wszystkie węzły są utrzymywane na tych samych głębokościach równoważenia od węzłów głównych. Głębokości te rosną powoli wraz ze wzrostem liczby elementów; to powoduje, że wszystkie węzły liści są o jeden węzeł dalej od katalogu głównego. Ponadto drzewa B są bardziej korzystne w porównaniu z innymi implementacjami w odniesieniu do czasu potrzebnego do uzyskania dostępu do danych.
Drzewo B + to drzewo n-tablicowe z węzłem, które składa się z dużej liczby dzieci na węzeł. Korzeń może być liściem lub węzłem, który zawiera więcej niż dwoje dzieci. Drzewo B + składa się z korzenia, wewnętrznych węzłów i liści.
Drzewo B + jest takie samo jak drzewo B; jedyną różnicą jest to, że w drzewie B + dodatkowy poziom jest dodawany u dołu z połączonymi liśćmi. Ponadto, w przeciwieństwie do drzewa B, każdy węzeł w drzewie B + zawiera tylko klucze, a nie pary klucz-wartość.
Dodatkowo, czynnik bilansujący lub kolejność drzewa B + mierzy pojemność wewnętrznych węzłów w drzewie, tj. Liczbę węzłów, które mogą mieć. Rzeczywista liczba elementów podrzędnych dla węzła jest ograniczona dla węzłów wewnętrznych. Root jest jednak wyjątkiem, ponieważ może mieć więcej niż dwie liczby dzieci. Na przykład, jeśli kolejność drzewa B + to 7, każdy węzeł wewnętrzny (z wyjątkiem korzenia) może mieć od 4 do 7 dzieci; podczas gdy root może mieć od 2 do 7. Podstawową wartością drzewa B + jest przechowywanie danych w celu wydajnego pobierania w kontekście pamięci masowej blokowej, a w szczególności systemów plików.
Podstawową wartością drzewa B + jest przechowywanie i utrzymywanie danych, dzięki czemu dane nie zostaną utracone. To podejście jest szczególnie stosowane w kontekście pamięci blokowej i niektórych systemach plików. Liście, które są najniżej położonymi blokami indeksu drzewa B +, są często połączone ze sobą na połączonej liście; stąd to sprawia, że zapytania o zakres lub uporządkowana iteracja poprzez bloki stają się prostsze i bardziej wydajne. Ponadto współczynnik przestrzeni nie jest marnowany w drzewach B +. Drzewo B + zapewnia wydajny format struktury danych mieszkaniowych, co ułatwia ich dostęp i przechowywanie. Drzewa B + są szczególnie użyteczne jako indeks systemu baz danych, w którym dane zazwyczaj znajdują się na dysku.
Porównanie drzewa B i drzewa B +:
Drzewo B | B + Drzewo | |
Krótkie opisy w Internecie | Drzewo AB jest strukturą organizacyjną do przechowywania i pobierania informacji w postaci drzewa, w którym wszystkie węzły końcowe znajdują się w tej samej odległości od bazy, a wszystkie węzły nieterminalne mają między n a 2 n pod-drzewkami lub wskaźnikami (gdzie n jest liczbą całkowitą). | Drzewo B + to drzewo n-tablicowe ze zmienną, ale często dużą liczbą dzieci na węzeł. Drzewo B + składa się z korzenia, wewnętrznych węzłów i liści. Korzeń może być liściem lub węzłem z dwoma lub większą liczbą dzieci. |
Znany również jako | Zrównoważone drzewo. | B plus drzewo. |
Przestrzeń | Na) | Na) |
Szukaj | O (log n) | O (log b n) |
Wstawić | O (log n) | O (log b n) |
Kasować | O (log n) | O (log b n) |
Przechowywanie | W drzewie B wyszukaj klucze i dane przechowywane w węzłach wewnętrznych lub liści. | W drzewie B + dane przechowywane tylko w węzłach liści. |
Dane | Węzły listkowe wskaźników trzech magazynów zamiast rekordów rzeczywistych. | Węzły liści drzewa przechowują rzeczywisty zapis, a nie wskaźniki do zapisów. |
Przestrzeń | Te drzewa marnują przestrzeń | Tam drzewa nie marnują miejsca. |
Funkcja węzłów liści | W drzewie B węzeł liścia nie może być zapisywany przy użyciu listy połączonej. | W drzewie B + dane węzłów liści są uporządkowane na liście połączonej sekwencyjnie. |
Badawczy | Tutaj wyszukiwanie staje się trudne w drzewie B, ponieważ nie można znaleźć danych w węźle liści. | W tym przypadku wyszukiwanie dowolnych danych w drzewie B + jest bardzo łatwe, ponieważ wszystkie dane znajdują się w węzłach liści. |
Wyszukaj dostępność | Tutaj w drzewie B wyszukiwanie nie jest takie proste jak w drzewie B +. | Tutaj w drzewie B + wyszukiwanie staje się łatwe. |
Nadmiarowy klucz | Nie przechowują zbędnego klucza wyszukiwania. | Przechowują one nadmiarowy klucz wyszukiwania. |
Aplikacje | Są starszą wersją i nie są tak korzystne w porównaniu do drzewek B +. | Wielu wdrażających systemy baz danych preferuje prostotę strukturalną drzewa B +. |
