Wiele (być może większość) aplikacji bazodanowych używa obecnie B-drzew i odmian do przechowywania danych, ponieważ ta struktura danych optymalizuje operacje odczytu, zapisu i wyszukiwania na dysku twardym (a te z kolei odgrywają ważną rolę w ogólnej wydajności bazy danych).
Czy jednak dyski SSD powinny całkowicie wyprzeć tradycyjne dyski twarde (HDD), czy moglibyśmy powiedzieć, że B-Drzewa i ich odmiany staną się przestarzałe, dając miejsce dla struktur danych, które są bardziej wydajne w przypadku pamięci bezpośredniego dostępu? Jeśli tak, jakie będą te struktury? (np. tabele skrótów, drzewa AVL)
database
data-structures
Daniel Scocco
źródło
źródło
Odpowiedzi:
B-Drzewa są najczęściej używane do indeksowania baz danych na dysku twardym, ale mają zalety nawet jako struktura danych w pamięci, biorąc pod uwagę nowoczesną heirarchię pamięci z wieloma warstwami pamięci podręcznej i pamięcią wirtualną. Nawet jeśli pamięć wirtualna znajduje się na dysku SSD, to się nie zmieni.
Używam wbudowanej w drzewo biblioteki wielodrogowej w stylu B +, którą sporo napisałem w C ++. To może mieć przewagę wydajności - powodem był pierwotnie napisany było spróbować użyć pamięci podręcznej lepiej - ale muszę przyznać często nie działa w ten sposób. Problemem jest kompromis, który oznacza, że elementy muszą się przemieszczać w obrębie węzłów podczas wstawiania i usuwania, co nie zdarza się w przypadku drzew binarnych. Ponadto, niektóre z niskopoziomowych hacków kodujących, których użyłem do optymalizacji - cóż, prawdopodobnie mylą i pokonują optymalizator, prawdę mówiąc.
W każdym razie, nawet jeśli twoje bazy danych są przechowywane na dysku SSD, wciąż jest to blokowe urządzenie magazynujące, a nadal istnieje zaleta korzystania z B-Drzewa i innych drzew wielodrogowych.
ALE około dziesięć lat temu wymyślono algorytmy i struktury danych nieuwzględniające pamięci podręcznej. Są one nieświadome wielkości i struktury pamięci podręcznej itp. - sprawiają (asymptotycznie) najlepsze możliwe wykorzystanie każdej dziedziczności pamięci. B-Drzewa muszą zostać „dostrojone” do konkretnej dziedziczności pamięci, aby jak najlepiej wykorzystać (chociaż działają dość dobrze w przypadku dość szerokiego zakresu odmian).
Struktury danych niepamięci w pamięci podręcznej nie są jeszcze często spotykane na wolności, ale w tym czasie mogą sprawić, że zwykłe drzewa binarne w pamięci staną się przestarzałe. Mogą się również okazać przydatne w przypadku dysków twardych i dysków SSD, ponieważ nie dbają o rozmiar strony w klastrze lub w pamięci podręcznej dysku twardego.
Układ Van Emde Boas jest bardzo ważny w strukturach danych nieobsługujących pamięci podręcznej.
Kurs algorytmów MIT OpenCourseware obejmuje pewien zakres struktur danych niepamięci cache.
źródło
A priori tak, większość silników baz danych będzie musiała zostać przepisana, ponieważ B-Tree nie będzie już najbardziej wydajną strukturą danych do przechowywania danych, biorąc pod uwagę, że lokalizacja jest ważna na dysku twardym, na którym dysk porusza się wolno, a dane są pobierane w blokach, co oznacza, że każda zmiana danych musi:
To 10 + 3 + 3 + 10 + 3 + 3 = 34 ms
Średnio robienie tego samego na dysku SSD trwa tylko 1 ms, niezależnie od pozycji na dysku.
A ponieważ hashtable jest znacznie szybszy, moglibyśmy pomyśleć, że hashtable byłby lepszym zamiennikiem.
Jedynym problemem jest to, że tablice skrótów nie zachowują porządku i dlatego nie można znaleźć następnego i poprzedniego, jak robi to Van Emde Boas.
Widzieć:
Dlaczego znajdowanie następnego i poprzedniego jest ważne? Wyobraź sobie, że wszystkie elementy są większe niż x i mniejsze niż z, musisz użyć indeksów z funkcją znajdź poprzednią i znajdź następną.
Cóż, jedynym problemem jest to, że nie znaleźliśmy tablic skrótów z zdolnościami do utrzymywania porządku. Być może rozmiar wiadra w drzewie B będzie ważny, ale zostanie on rozwiązany za pomocą algorytmów nieświadomych z pamięci podręcznej.
Powiedziałbym więc, że jest to problem otwarty.
źródło