Czy wraz z pojawieniem się dysków półprzewodnikowych B-drzewa i inne struktury danych staną się przestarzałe?

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)

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.

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:

1. Przenieś głowę w odpowiednie miejsce na dysku (~ 10ms).
2. Poczekaj, aż dysk się obróci (przy 10k rpm, co oznacza 167 obrotów na sekundę, ale średnio czekamy tylko na pół obrotu, więc ~ 3ms).
3. Przeczytaj blok (~ 3ms).
4. Zmodyfikuj w pamięci RAM. (~ 10ns)
5. Ponownie przenieś głowicę do właściwej lokalizacji na dysku (ponownie ~ 10 ms).
6. Poczekaj, aż dysk ponownie się obróci (ponownie ~ 3 ms).
7. Napisz blok (~ 3ms).

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ć:

1. http://en.wikipedia.org/wiki/Van_Emde_Boas_tree
2. http://bryanpendleton.blogspot.com/2009/06/cache-oblivious-data-structures.html

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.