Jakie są różnice między drzewami B i drzewami B +?

W drzewie b można przechowywać zarówno klucze, jak i dane w węzłach wewnętrznych i liściach , ale w drzewie b + dane należy przechowywać tylko w węzłach liści .

Czy jest jakaś zaleta robienia powyższego na drzewie b +?

Dlaczego nie używać wszędzie b-drzew zamiast b + drzew, ponieważ intuicyjnie wydają się one znacznie szybsze?

Mam na myśli, dlaczego musisz replikować klucz (dane) w drzewie b +?

Poniższy obraz pomaga pokazać różnice między drzewami B + a drzewami B.

Zalety drzew B +:

• Ponieważ drzewa B + nie mają danych powiązanych z węzłami wewnętrznymi, na stronie pamięci można zmieścić więcej kluczy. Dlatego będzie wymagało mniejszej liczby braków pamięci podręcznej, aby uzyskać dostęp do danych znajdujących się w węźle liścia.
• Węzły liści drzew B + są połączone, więc wykonanie pełnego skanowania wszystkich obiektów w drzewie wymaga tylko jednego liniowego przejścia przez wszystkie węzły liści. Z kolei drzewo AB wymagałoby przejścia przez każdy poziom drzewa. To przejście przez pełne drzewo prawdopodobnie będzie wiązało się z większą liczbą braków w pamięci podręcznej niż przejście liniowe liści B +.

Zaleta drzewek B:

• Ponieważ drzewa B zawierają dane dla każdego klucza, często używane węzły mogą leżeć bliżej katalogu głównego, a zatem można uzyskać do nich szybszy dostęp.

Główną zaletą drzew B + w porównaniu z drzewami B jest to, że pozwalają spakować więcej wskaźników do innych węzłów poprzez usunięcie wskaźników do danych, zwiększając w ten sposób rozłożenie i potencjalnie zmniejszając głębokość drzewa.

Wadą jest to, że nie ma wczesnych outów, gdy można było znaleźć dopasowanie w węźle wewnętrznym. Ale ponieważ obie struktury danych mają ogromne fanouty, zdecydowana większość twoich dopasowań i tak będzie na węzłach liści, co czyni średnio drzewo B + bardziej wydajnym.

Drzewa B + są znacznie łatwiejsze i wydajniejsze, aby wykonać pełne skanowanie, jak w przypadku każdego kawałka danych, które indeksuje drzewo, ponieważ węzły końcowe tworzą listę połączoną. Aby wykonać pełne skanowanie za pomocą B-drzewa, musisz wykonać pełne przejście drzewa, aby znaleźć wszystkie dane.

Z drugiej strony B-Drzewa mogą być szybsze podczas wyszukiwania (szukania określonego fragmentu danych według klucza), szczególnie gdy drzewo znajduje się w pamięci RAM lub innej pamięci nieblokowanej. Ponieważ można podnieść często używane węzły w drzewie, do uzyskania dostępu do danych potrzeba mniej porównań.

1. W drzewie B klucze wyszukiwania i dane są przechowywane w węzłach wewnętrznych lub liściowych. Ale w drzewku B + dane są przechowywane tylko w węzłach liści.
2. Pełne skanowanie drzewa B + jest bardzo łatwe, ponieważ wszystkie dane znajdują się w węzłach liści. Pełny skan drzewa B wymaga pełnego przejścia.
3. W drzewie B dane można znaleźć w węzłach liści lub węzłach wewnętrznych. Usuwanie wewnętrznych węzłów jest bardzo skomplikowane. W drzewie B + dane znajdują się tylko w węzłach liści. Usunięcie węzłów liści jest łatwe.
4. Wstawienie do drzewa B jest bardziej skomplikowane niż drzewo B +.
5. Drzewa B + przechowują zbędne klucze wyszukiwania, ale drzewo B nie ma nadmiarowej wartości.
6. W drzewie B + dane węzła liścia są uporządkowane jako sekwencyjna lista połączona, ale w drzewie B węzeł liścia nie może być przechowywany przy użyciu listy połączonych. Wdrożenia wielu systemów baz danych preferują prostotę strukturalną drzewa B +.

Przykład z koncepcji systemu baz danych 5

Drzewo B +

odpowiadające B-drzewo

Zdefiniuj „znacznie szybciej”. Asymptotycznie są mniej więcej takie same. Różnice polegają na tym, w jaki sposób wykorzystują pamięć dodatkową. Artykuły w Wikipedii na temat drzewek B i drzewek B + wyglądają na całkiem godne zaufania.

Adegoke A, Amit

Myślę, że jedną istotną kwestią, której brakuje ludziom, jest różnica między danymi a wskaźnikami, jak wyjaśniono w tej sekcji.

Wskaźnik: wskaźnik do innych węzłów.

Dane: - W kontekście indeksów baz danych dane są tylko kolejnym wskaźnikiem do rzeczywistych danych (wierszy), które znajdują się gdzie indziej.

Dlatego w przypadku drzewa B każdy węzeł ma trzy klucze informacyjne, wskaźniki do danych związanych z kluczami i wskaźnik do węzłów potomnych.

W drzewie wewnętrznym B + trzymaj klucze i wskaźniki do węzła potomnego, podczas gdy węzeł liścia przechowuj klucze i wskaźniki do powiązanych danych. Pozwala to na większą liczbę kluczy dla danego rozmiaru węzła. Rozmiar węzła zależy głównie od wielkości bloku.

Zaletę posiadania większej liczby kluczy na węzeł wyjaśniono powyżej, więc oszczędzę czasu na pisaniu.

Drzewa B + są szczególnie dobre w przypadku przechowywania blokowego (np .: dysk twardy). Mając to na uwadze, zyskujesz kilka zalet, na przykład (z góry mojej głowy):

• wysoka wentylacja / niska głębokość: oznacza to, że musisz dostać mniej bloków, aby dostać się do danych. z danymi przeplecionymi ze wskaźnikami, każdy odczyt dostaje mniej wskaźników, więc potrzebujesz więcej prób, aby dostać się do danych

• proste i spójne przechowywanie bloków: węzeł wewnętrzny ma N wskaźników, nic więcej, węzeł liścia ma dane, nic więcej. dzięki czemu łatwo parsować, debugować, a nawet rekonstruować.

• wysoka gęstość klucza oznacza, że ​​górne węzły prawie na pewno znajdują się w pamięci podręcznej, w wielu przypadkach wszystkie węzły wewnętrzne są szybko buforowane, więc tylko dostęp do danych musi przejść na dysk.

W B + Tree, ponieważ tylko wskaźniki są przechowywane w wewnętrznych węzłach, ich rozmiar staje się znacznie mniejszy niż wewnętrzne węzły drzewa B (które przechowują oba dane + klucz). Dlatego też indeksy drzewa B + można pobrać z pamięci zewnętrznej w jednym czytniku dysku, przetworzyć w celu znalezienia lokalizacji celu. Jeśli było to drzewo B, odczyt dysku jest wymagany dla każdego procesu decyzyjnego. Mam nadzieję, że wyjaśniłem swój punkt widzenia! :)

**

Główną wadą B-Tree jest trudność sekwencyjnego przemierzania kluczy. Drzewo B + zachowuje właściwości szybkiego dostępu losowego drzewa B, jednocześnie umożliwiając szybki dostęp sekwencyjny

** ref: Struktury danych przy użyciu C // Autor: Aaro M. Tenenbaum

http://books.google.co.in/books?id=X0Cd1Pr2W0gC&pg=PA456&lpg=PA456&dq=drawback+of+B-Tree+is+the+difficulty+of+Traversing+the+keys+ kolejno kolejno&source=bl&ots=pGcPQSEJMS&s F9MY7zEXYAMVKl_Sg4W-0LTRor8 & hl = en & sa = X & ei = nD5AUbeeH4zwrQe12oCYAQ & ved = 0CDsQ6AEwAg # v = on page & q = minus% 20of% 20B-Tree% 20ys% 20%% 20%% 20%% 20%

Weźmy przykład - masz tabelę z ogromną ilością danych na wiersz. Oznacza to, że każda instancja obiektu jest duża.

Jeśli użyjesz tutaj drzewa B, wówczas większość czasu spędza się na skanowaniu stron z danymi - co jest bezużyteczne. W bazach danych jest to powodem używania drzew B + do unikania skanowania danych obiektów.

B + Drzewa oddzielają klucze od danych.

Ale jeśli Twój rozmiar danych jest mniejszy, możesz przechowywać je z kluczem, co robi drzewo B.

Podstawowa różnica między drzewem B i drzewem B + polega na tym, że drzewo B eliminuje zbędne przechowywanie wartości kluczy wyszukiwania. Ponieważ klucze wyszukiwania nie powtarzają się w drzewie B, może nie być możliwe przechowywanie indeksu przy użyciu mniejszej liczby węzłów drzewa niż w odpowiednim indeksie drzewa B +. Ponieważ jednak klucz wyszukiwania, który pojawia się w węzłach innych niż liście, nie pojawia się nigdzie indziej w drzewie B, jesteśmy zmuszeni dołączyć dodatkowe pole wskaźnika dla każdego klucza wyszukiwania w węźle innym niż liść. Są to zalety przestrzenne dla B-drzewa, ponieważ powtórzenie nie występuje i można je stosować dla dużych indeksów.

Drzewo B + jest zrównoważonym drzewem, w którym każda ścieżka od korzenia drzewa do liścia ma tę samą długość, a każdy nieleafowy węzeł drzewa ma między [n / 2] a [n] dziećmi, gdzie n jest naprawiono dla konkretnego drzewa. Zawiera strony indeksu i strony danych. Drzewa binarne mają tylko dwa elementy podrzędne na węzeł nadrzędny, drzewa B + mogą mieć zmienną liczbę elementów podrzędnych dla każdego węzła nadrzędnego

Jednym z możliwych zastosowań drzew B + jest to, że nadaje się do sytuacji, w których drzewo rośnie tak duże, że nie mieści się w dostępnej pamięci. Dlatego ogólnie można oczekiwać, że będziesz wykonywać wiele operacji we / wy.
Często zdarza się, że drzewo B + jest używane nawet wtedy, gdy w rzeczywistości pasuje do pamięci, a następnie menedżer pamięci podręcznej może go tam przechowywać na stałe. Jest to jednak szczególny przypadek, nie ogólny, a zasady buforowania są odrębne od konserwacji drzewa B + jako takiej.

Ponadto w drzewie B + strony liści są połączone ze sobą na połączonej liście (lub podwójnie połączonej liście), co optymalizuje przechodzenie (dla przeszukiwania zakresu, sortowania itp.). Tak więc liczba wskaźników jest funkcją konkretnego algorytmu, który jest używany.