Indeksowanie bazy danych w pigułce z porównaniem B+tree i Hash

Często mówi się, że indeksowanie to najważniejsza technika wydajnego przetwarzania zapytań w przypadku, gdy baza danych jest wystarczająco duża. Ten post ma na celu podsumowanie tego, czym jest indeks bazy danych i ponowne omówienie hash i B+Tree.

Indeks to struktura danych, która organizuje rekordy w celu optymalizacji pewnych rodzajów operacji pobierania. Możemy utworzyć indeks w polu tabeli, a następnie pobrać wszystkie rekordy, które spełniają warunki wyszukiwania w search-key pole. Bez indeksu nasze zapytanie zakończyłoby skanowanie liniowe całej zawartości tabeli w celu pobrania tylko jednego lub kilku rekordów.

W tym poście chciałbym podsumować wydajność i przypadki użycia dwóch popularnych technik indeksowania:Hash index i B+drzewo

Indeks skrótu

Ta technika jest szeroko stosowana do tworzenia indeksów w pamięci głównej ze względu na jego szybkie odzyskiwanie z natury. Ma średnią złożoność operacji O(1) i złożoność pamięci O(n).
W wielu książkach ludzie używają terminu bucket do oznaczenia jednostki pamięci, która przechowuje jeden lub więcej rekordów
Jeśli chodzi o haszowanie, należy omówić dwie kwestie:

• Funkcja haszująca:mapuje klucze wyszukiwania (jako dane wejściowe) na liczbę całkowitą reprezentującą ten klucz w zasobniku.
• Schemat haszowania:jak radzić sobie z kolizją klawiszy po haszowaniu.

Niektórzy pytają:dlaczego kolizja? Czy kiedykolwiek istnieje idealna funkcja skrótu? W rzeczywistości, powiedzmy, że twoje klucze są nieskończonym zbiorem, niemożliwe jest zmapowanie ich na zbiór 32-bitowych liczb całkowitych bez kolizji. Powinien istnieć kompromis między obliczeniami a współczynnikiem kolizji.

Istnieje kilka schematów haszowania, o których warto wspomnieć:sondowanie liniowe, haszowanie łańcuchowe i haszowanie rozszerzalne. Algorytmy wyszukiwania/wstawiania/usuwania różnią się w zależności od schematu haszowania, na przykład haszowanie połączone radzą sobie z kolizjami kluczy, umieszczając elementy o tej samej wartości haszowania w tym samym zasobniku.

Plusy

• Indeks skrótu jest odpowiedni do wyszukiwania równości lub klucza podstawowego. Zapytania mogą korzystać z indeksu mieszającego, aby uzyskać zamortyzowany koszt wyszukiwania O(1). Na przykład:SELECT name, id FROM student WHERE id = '1315';

Wady

Tablica haszująca ma pewne ograniczenia:

• Zapytania o zakres nie są wydajne. Tablica haszująca oparta jest na równomiernym rozkładzie. Innymi słowy, nie masz kontroli nad tym, gdzie zostanie umieszczony wpis indeksu.
• Niska skalowalność:wydajność operacji wyszukiwania może ulec pogorszeniu, gdy występuje wiele kolizji i wymaga zmiany rozmiaru tablicy mieszającej, a następnie ponownego mieszania istniejących wpisów indeksu.

B+drzewo

Jest to samobilansująca się struktura danych w postaci drzewa, która utrzymuje dane w posortowanej kolejności i umożliwia szybkie wyszukiwanie w każdym węźle, zwykle przy użyciu wyszukiwania binarnego.
B+Tree to standardowa implementacja indeksu w prawie każdym systemie relacyjnych baz danych.

B+Tree to w zasadzie drzewo wyszukiwania M-way, które ma następującą strukturę:

• idealna równowaga:węzły liści zawsze mają tę samą wysokość.
• każdy węzeł wewnętrzny inny niż korzeń jest co najmniej w połowie zapełniony (M/2 − 1 <=liczba kluczy <=M − 1).
• Każdy węzeł wewnętrzny z k kluczy ma k+1 niepuste dzieci.

Każdy węzeł drzewa ma tablicę posortowanych par klucz-wartość. Para klucz-wartość jest konstruowana z (wartość klucza wyszukiwania, wskaźnik) dla węzłów głównych i wewnętrznych. Wartości węzłów liścia mogą być 2 możliwościami:

• rzeczywisty rekord
• wskaźnik do aktualnego rekordu

Wyszukaj wartość v

• Rozpocznij od węzła głównego
• Chociaż węzeł nie jest węzłem liścia, robimy:
  • Znajdź najmniejszą Ki, gdzie Ki>=v
  • Jeśli Ki ==v:ustaw bieżący węzeł na węzeł wskazany przez Pi+1
  • W przeciwnym razie ustaw bieżący węzeł na węzeł wskazany przez Pi

Zduplikowane klucze

Ogólnie rzecz biorąc, klucz wyszukiwania może być zduplikowany, aby rozwiązać ten problem, większość implementacji baz danych zawiera złożony klucz wyszukiwania. Na przykład chcemy utworzyć indeks na student_name wtedy nasz złożony klucz wyszukiwania powinien mieć postać (nazwa_ucznia, Ap), gdzie Ap jest kluczem podstawowym tabeli.

Plusy

B+tree oferuje dwie główne funkcje:

• Minimalizowanie operacji we/wy
  • Zredukowana wysokość:B+Tree ma dość duży współczynnik rozgałęzienia (często stosowana wartość między 50 a 2000), co sprawia, że ​​drzewo jest grube i krótkie. Poniższy rysunek ilustruje B+Drzewo o wysokości 2. Jak widzimy, węzły są rozrzucone, przejście w dół do liścia zajmuje mniej węzłów. Koszt wyszukania pojedynczej wartości to wysokość drzewa + 1 dla losowego dostępu do tabeli.
• Skalowalność:
  • Masz przewidywalną wydajność we wszystkich przypadkach, w szczególności O(log(n)). W przypadku baz danych jest to zwykle ważniejsze niż uzyskanie najlepszej lub średniej wydajności przypadku.
  • Drzewo zawsze pozostaje zrównoważone przez jego implementację. B+drzewo z n klawiszami zawsze ma głębokość O(log(n)). Dzięki temu wydajność nie ulegnie pogorszeniu, jeśli baza danych będzie się powiększać. Czteropoziomowe drzewo o współczynniku rozgałęzienia 500 może przechowywać do 256 TB pod warunkiem, że strona ma rozmiar 4 KB.

• B+Tree najlepiej nadaje się do zapytań zakresowych, na przykład "SELECT * FROM student WHERE age > 20 AND age < 22"

Wniosek

Chociaż indeks mieszający działa lepiej pod względem zapytań o dokładnym dopasowaniu, B+Tree jest prawdopodobnie najczęściej używaną strukturą indeksu w RDBMS dzięki jego stałej wydajności w ogólnej i wysokiej skalowalności.

Ostatnio drzewo scalające o strukturze dziennika (LSM-drzewo) wzbudziło duże zainteresowanie jako pretendent do drzewa B+, ponieważ jego struktura danych może umożliwić lepszą wydajność wykorzystania przestrzeni dyskowej. Zbadam to dokładniej i napiszę o tym w najbliższej przyszłości.