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

15

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)

Daniel Scocco
źródło
Pytasz, czy staną się przestarzałe z punktu widzenia implementacji bazy danych, czy ogólnie, ponieważ mają wiele innych aplikacji poza aplikacjami bazodanowymi.
Pemdas
Z punktu widzenia bazy danych.
Daniel Scocco

Odpowiedzi:

21

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.

Steve314
źródło
1
Ciekawy. Dałeś kilka dobrych wskazówek (bez zamierzonej gry słów!), Aby dalej badać ten temat. Dzięki.
Daniel Scocco
Ten kurs MIT zawiera również informacje na temat pamięci podręcznych struktur danych.
dan_waterworth
Cześć, czy miałeś na myśli, że B-drzewo będzie przestarzałe z powodu struktur danych nieobsługujących pamięci podręcznej, a nie z powodu dysków SSD? Ale co z innymi strukturami danych, takimi jak zarządzanie blokami w DBMS?
Yang Bo
@ user955091 - Miałem na myśli ze względu na struktury danych nieuwzględniające pamięci podręcznej (pedantycznie znaczące struktury, które są optymalne w modelu nieobsługiwanym przez pamięć podręczną), ale wtedy byłem nimi trochę podekscytowany. Inne struktury danych nie znikną wkrótce. Po pierwsze, pamięć podręczna nie jest jedynym problemem związanym z wydajnością - równoległość stawia różne wymagania. Poza tym potrzeba zamawiania na podstawie klucza jest często szczególnym przypadkiem - zwykle tabele skrótów są najważniejsze. Ułożenie „losowego” układu jako przyjaznego dla pamięci podręcznej może być trudne, ale jeden dostęp do bezpośredniego pobrania elementu jest trudny do pokonania - nie potrzebujesz lokalizacji.
Steve314
3

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.

Wilhelm Van Ende Boas
źródło
Tabela skrótów (normalnie) nie uwzględnia pamięci podręcznej WRT, modelując jej wydajność, ale to nie znaczy, że jest wydajna w tym modelu. Problem polega na tym, że funkcje skrótu są zwykle zaprojektowane do „losowego” rozpraszania elementów - dlatego tabele skrótów są nieuporządkowane, a także dlatego, że mają słabą lokalizację. Oznacza to, że nawet jeśli potrafisz zidentyfikować sekwencję elementów za pomocą sąsiednich kluczy, prawdopodobnie nie odczytasz dwóch lub więcej elementów na blok (dyski SSD są nadal urządzeniami blokowymi).
Steve314
1
Oczywiście haszowanie jest czasem nazywane „transformacją klucza”, a transformacja nie musi być „losowa” - być może możliwe jest zdefiniowanie funkcji skrótu, która pozwala na względnie wydajny dostęp sekwencyjny (nie eliminując wyszukiwania - informacja zostaje utracona przez w końcu funkcja skrótu - ale minimalizująca ją) i daje pewne korzyści lokalizacyjne, jednocześnie utrzymując rzadkie kolizje skrótów.
Steve314 16.04.13