Zaleta drzew B + nad BST?

Question

Uczę się o drzewach B + w klasie o bazach danych i zastanawiałem się, jakie konkretne zalety drzewa B + dadzą drzewa wyszukiwania binarnego?

Wygląda na to, że oba mają średnią złożoność O (logN) dla większości operacji z nutą, ale drzewa B + również mają dodatkowy (pomijalny?) Czas wyszukiwania w każdym węźle potomnym, gdzie BST oczywiście wymagają tylko O ​​(1) czasu. który węzeł podrzędny przejdzie do.

Jakie rzeczywiste zalety sprawiają, że drzewa B + stają się bardziej popularne w bazach danych niż BST?

Answer 1

Główną zaletą drzewa B + (i drzewek B w ogóle) w drzewach binarnych jest to, że dobrze współpracują z pamięcią podręczną. Jeśli masz binarne drzewo wyszukiwania, którego węzły są przechowywane w mniej więcej losowej kolejności w pamięci, to za każdym razem, gdy podążasz za wskaźnikiem, maszyna będzie musiała wciągnąć nowy blok pamięci do pamięci podręcznej procesora, która jest znacznie wolniejsza niż dostęp do pamięci już w pamięci podręcznej.

B + -tree i B-tree działają, ponieważ każdy węzeł przechowuje ogromną liczbę kluczy lub wartości i ma dużą liczbę dzieci. Zazwyczaj są one pakowane razem w taki sposób, aby pojedynczy węzeł ładnie mieścił się w pamięci podręcznej (lub, jeśli jest przechowywany na dysku, aby został pobrany z dysku w pojedynczej operacji odczytu). Następnie musisz wykonać więcej pracy, aby znaleźć klucz w węźle lub określić, które dziecko będzie czytać dalej, ale ponieważ wszystkie dostępy do pamięci wykonane w jednym węźle można wykonać bez powrotu do dysku, czasy dostępu są bardzo małe. Oznacza to, że nawet jeśli zasadniczo BST może być lepszy pod względem dostępu do pamięci pod numerem o numerze, B + -tree i B-drzewo mogą działać lepiej pod względem runtime dostępu do pamięci.

Typowy przypadek użycia dla drzewa B + lub drzewa B znajduje się w bazie danych, w której znajduje się ogromna ilość informacji, a dane są tak liczne, że nie wszystkie mieszczą się w pamięci głównej. W związku z tym dane mogą być przechowywane w drzewie B + lub drzewie B na dysku twardym. Minimalizuje to liczbę odczytów dysku potrzebnych do wciągnięcia danych podczas wyszukiwania. Niektóre systemy plików (jak na przykład ext4, jak sądzę) również używają B-drzew z tego samego powodu - minimalizują liczbę niezbędnych wyszukiwań na dysku, co jest prawdziwym wąskim gardłem.

Mam nadzieję, że to pomoże!

Answer 2

Prawdziwe przechowywanie danych (np. W DB) wymaga przechowywania dużej ilości danych. Ponieważ pobieranie danych jest podstawową operacją, niepotrzebne jest odczytywanie danych z dysku niż pamięci RAM.

Teraz, to jest haczyk ...

przechowuje dane w mniejszym BST węzła w porównaniu do B + drzew. Powoduje to wzrost wysokości drzew BST niż B +. Są więc przechowywane na dysku, a nie w pamięci RAM.

Za każdym razem, gdy dane mają być pobrane z drzewa, dane z dysku muszą być załadowane do pamięci głównej (co jest oczywiście czasochłonne), podczas gdy w przypadku drzewek B + dane już istnieją w pamięci RAM, a wymagany węzeł jest pobierany bezpośrednio, a dane są pobierane z tego węzła, który może zawierać wiele elementów podrzędnych (ale ogólny czas pobierania danych jest mniejszy w przypadku drzewek B +, ponieważ nie ma potrzeby ładowania danych z dysku do ubijania).