Hej Habro! Zwracam uwagę na tłumaczenie artykułu
„Jak działa relacyjna baza danych”.

Jeśli chodzi o relacyjne bazy danych, nie mogę oprzeć się wrażeniu, że czegoś brakuje. Są używane wszędzie. Dostępnych jest wiele różnych baz danych, od małego i użytecznego SQLite po potężne Teradata. Ale jest tylko kilka artykułów wyjaśniających, jak działa baza danych. Możesz wyszukiwać samodzielnie, korzystając z narzędzia „howdoesarelationaldatabasework”, aby zobaczyć, jak niewiele jest wyników. Poza tym te artykuły są krótkie. Jeśli szukasz najnowocześniejszych technologii (BigData, NoSQL lub JavaScript), znajdziesz więcej szczegółowych artykułów wyjaśniających, jak one działają.

Czy relacyjne bazy danych są zbyt stare i zbyt nudne, aby można je było wyjaśniać poza kursami uniwersyteckimi, artykułami naukowymi i książkami?

Jako programista nienawidzę używać czegoś, czego nie rozumiem. A jeśli bazy danych są używane od ponad 40 lat, musi istnieć ku temu powód. Przez lata spędziłem setki godzin, aby naprawdę zrozumieć te dziwne czarne skrzynki, których używam na co dzień. Relacyjne bazy danych bardzo interesujące, ponieważ w oparciu o użyteczne i nadające się do ponownego wykorzystania koncepcje. Jeśli interesuje Cię zrozumienie bazy danych, ale nigdy nie miałeś czasu ani ochoty zagłębiać się w ten szeroki temat, ten artykuł powinien Ci się spodobać.

Choć tytuł tego artykułu jest jednoznaczny, celem tego artykułu nie jest zrozumienie, jak korzystać z bazy danych, dlatego też, powinieneś już wiedzieć jak napisać prostą prośbę o połączenie i podstawowe zapytania OKRUTNY; w przeciwnym razie możesz nie zrozumieć tego artykułu. Tylko to musisz wiedzieć, resztę wyjaśnię.

Zacznę od podstaw informatyki, takich jak złożoność czasowa algorytmów (BigO). Wiem, że niektórzy z Was nienawidzą tej koncepcji, ale bez niej nie będziecie w stanie zrozumieć zawiłości bazy danych. Ponieważ jest to obszerny temat, Skupię się na co myślę, że jest ważne: jak przetwarza baza danych SQL zapytanie ofertowe. Po prostu przedstawię podstawowe pojęcia dotyczące baz danychtak, aby na końcu artykułu mieć pojęcie o tym, co dzieje się pod maską.

Ponieważ jest to długi i techniczny artykuł, który obejmuje wiele algorytmów i struktur danych, nie spiesz się, aby go przeczytać. Niektóre pojęcia mogą być trudne do zrozumienia; możesz je pominąć i nadal uzyskać ogólny pomysł.

Dla bardziej doświadczonych, ten artykuł jest podzielony na 3 części:

Przegląd komponentów bazy danych niskiego i wysokiego poziomu
Omówienie procesu optymalizacji zapytań
Przegląd zarządzania transakcjami i pulą buforów

Powrót do podstaw

Wiele lat temu (w odległej galaktyce...) programiści musieli dokładnie znać liczbę kodowanych operacji. Znali swoje algorytmy i struktury danych na pamięć, ponieważ nie mogli sobie pozwolić na marnowanie procesora i pamięci swoich powolnych komputerów.

W tej części przypomnę niektóre z tych pojęć, ponieważ są one niezbędne do zrozumienia bazy danych. Przedstawię również koncepcję indeks bazy danych.

O(1) vs O(n2)

W dzisiejszych czasach wielu programistów nie przejmuje się złożonością czasową algorytmów... i mają rację!

Ale gdy masz do czynienia z dużą ilością danych (nie mówię o tysiącach) lub jeśli zmagasz się z problemem milisekund, zrozumienie tej koncepcji staje się niezwykle istotne. Jak możesz sobie wyobrazić, bazy danych muszą radzić sobie w obu sytuacjach! Nie będę wymagał, abyś poświęcił więcej czasu, niż to konieczne, na przekazanie tematu. Pomoże nam to później zrozumieć koncepcję optymalizacji opartej na kosztach (koszt na podstawie optymalizacja).

Koncepcja

Złożoność czasowa algorytmu służy do sprawdzania, ile czasu zajmie wykonanie algorytmu dla danej ilości danych. Aby opisać tę złożoność, używamy notacji matematycznej z dużym O. Notacji tej używa się z funkcją opisującą, ile operacji potrzebuje algorytm dla danej liczby wejść.

Na przykład, gdy mówię „ten algorytm ma złożoność O(jakaś_funkcja())”, oznacza to, że algorytm wymaga operacji niektórych_funkcji(a_certain_amount_of_data) do przetworzenia określonej ilości danych.

W tym przypadku, Nie ilość danych się liczy**, W przeciwnym razie ** jak wzrasta liczba operacji wraz ze wzrostem ilości danych. Złożoność czasowa nie podaje dokładnej liczby operacji, ale jest dobrym sposobem na oszacowanie czasu wykonania.

Na tym wykresie można zobaczyć liczbę operacji w funkcji ilości danych wejściowych dla różnych typów złożoności czasowej algorytmów. Do ich przedstawienia użyłem skali logarytmicznej. Innymi słowy, ilość danych szybko rośnie z 1 do 1 miliarda.Możemy zobaczyć, że:

O(1) czyli stała złożoność pozostaje stała (w przeciwnym razie nie nazwalibyśmy tego stałą złożonością).
O(log(n)) pozostaje niski nawet przy miliardach danych.
Najgorsza trudność - O(n2), gdzie liczba operacji szybko rośnie.
Pozostałe dwie komplikacje nasilają się równie szybko.

Примеры

Przy małej ilości danych różnica pomiędzy O(1) i O(n2) jest pomijalna. Załóżmy na przykład, że masz algorytm, który musi przetworzyć 2000 elementów.

Algorytm O(1) będzie kosztować 1 operację
Algorytm O(log(n)) będzie Cię kosztować 7 operacji
Algorytm O(n) będzie Cię kosztować 2 operacji
Algorytm O(n*log(n)) będzie Cię kosztować 14 000 operacji
Algorytm O(n2) będzie Cię kosztować 4 000 000 operacji

Różnica pomiędzy O(1) i O(n2) wydaje się duża (4 miliony operacji), ale stracisz maksymalnie 2 ms, czyli czas na mrugnięcie oczami. Rzeczywiście, nowoczesne procesory mogą przetwarzać setki milionów operacji na sekundę. Dlatego też wydajność i optymalizacja nie stanowią problemu w wielu projektach IT.

Jak powiedziałem, znajomość tego pojęcia jest nadal ważna podczas pracy z ogromnymi ilościami danych. Jeśli tym razem algorytm ma przetworzyć 1 000 000 elementów (co jak na bazę danych to niewiele):

Algorytm O(1) będzie kosztować 1 operację
Algorytm O(log(n)) będzie Cię kosztować 14 operacji
Algorytm O(n) będzie Cię kosztować 1 000 000 operacji
Algorytm O(n*log(n)) będzie Cię kosztować 14 000 000 operacji
Algorytm O(n2) będzie Cię kosztować 1 000 000 000 000 operacji

Nie liczyłem, ale powiedziałbym, że dzięki algorytmowi O(n2) masz czas na wypicie kawy (nawet dwóch!). Jeśli dodasz kolejne 0 do wolumenu danych, będziesz miał czas na drzemkę.

Zejdźmy głębiej

Dla twojej informacji:

Dobre przeszukanie tablicy mieszającej pozwala znaleźć element w O(1).
Przeszukiwanie dobrze zrównoważonego drzewa daje wyniki w O(log(n)).
Przeszukiwanie tablicy daje wyniki w O(n).
Najlepsze algorytmy sortowania mają złożoność O(n*log(n)).
Zły algorytm sortowania ma złożoność O(n2).

Uwaga: w kolejnych częściach zobaczymy te algorytmy i struktury danych.

Istnieje kilka typów złożoności czasowej algorytmów:

przeciętny scenariusz
najlepszy scenariusz
i najgorszy scenariusz

Złożoność czasowa jest często najgorszym scenariuszem.

Mówiłem tylko o złożoności czasowej algorytmu, ale złożoność dotyczy także:

zużycie pamięci przez algorytm
Algorytm zużycia operacji we/wy dysku

Oczywiście zdarzają się komplikacje gorsze niż n2, na przykład:

n4: to jest straszne! Niektóre z wymienionych algorytmów mają taką złożoność.
3n: to jest jeszcze gorsze! Jeden z algorytmów, który zobaczymy w środku tego artykułu, ma tę złożoność (i jest faktycznie używany w wielu bazach danych).
silnia n: nigdy nie otrzymasz wyników nawet przy niewielkiej ilości danych.
nn: Jeśli napotkasz tę złożoność, powinieneś zadać sobie pytanie, czy to naprawdę jest twoje pole działania…

Uwaga: nie podałem faktycznej definicji oznaczenia dużego O, tylko pomysł. Artykuł ten można przeczytać pod adresem Wikipedia dla definicji rzeczywistej (asymptotycznej).

Sortowanie przez scalanie

Co robisz, gdy musisz posortować kolekcję? Co? Wywołujesz funkcję sort()... OK, dobra odpowiedź... Ale w przypadku bazy danych musisz zrozumieć, jak działa ta funkcja sort().

Dobrych algorytmów sortowania jest kilka, dlatego skupię się na najważniejszych: sortowanie przez scalanie. Możesz nie rozumieć, dlaczego sortowanie danych jest teraz przydatne, ale powinieneś to zrobić po części dotyczącej optymalizacji zapytań. Co więcej, zrozumienie sortowania przez scalanie pomoże nam później zrozumieć typową operację łączenia baz danych zwaną łączyć przystąpić (stowarzyszenie fuzyjne).

Łączyć

Podobnie jak wiele przydatnych algorytmów, sortowanie przez scalanie opiera się na pewnej sztuczce: połączenie 2 posortowanych tablic o rozmiarze N/2 w tablicę posortowaną na podstawie N elementów kosztuje tylko N operacji. Ta operacja nazywa się łączeniem.

Zobaczmy, co to oznacza na prostym przykładzie:

Ten rysunek pokazuje, że aby zbudować ostateczną posortowaną tablicę 8-elementową, wystarczy wykonać tylko jedną iterację po 2 tablicach 4-elementowych. Ponieważ obie tablice 4-elementowe są już posortowane:

1) porównujesz oba bieżące elementy w dwóch tablicach (na początku prąd = pierwszy)
2) następnie weź najmniejszy i umieść go w 8-elementowej tablicy
3) i przejdź do następnego elementu tablicy, z którego wziąłeś najmniejszy element
i powtarzaj 1,2,3, aż dojdziesz do ostatniego elementu jednej z tablic.
Następnie bierzesz pozostałe elementy drugiej tablicy i umieszczasz je w 8-elementowej tablicy.

Działa to, ponieważ obie tablice 4-elementowe są posortowane, więc nie trzeba „wracać” do tych tablic.

Teraz, gdy rozumiemy tę sztuczkę, oto mój pseudokod scalania:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

Sortowanie przez scalanie dzieli problem na mniejsze problemy, a następnie znajduje wyniki mniejszych problemów, aby uzyskać wynik pierwotnego problemu (uwaga: ten typ algorytmu nazywa się dziel i zwyciężaj). Jeśli nie rozumiesz tego algorytmu, nie martw się; Nie zrozumiałem tego, kiedy zobaczyłem to po raz pierwszy. Jeśli może ci to pomóc, widzę ten algorytm jako algorytm dwufazowy:

Faza podziału, podczas której tablica jest dzielona na mniejsze tablice
Faza sortowania polega na łączeniu małych tablic (za pomocą unii) w celu utworzenia większej tablicy.

Faza podziału

Na etapie dzielenia tablica jest dzielona na tablice unitarne w 3 krokach. Formalna liczba kroków to log(N) (ponieważ N=8, log(N) = 3).

Skąd mam to wiedzieć?

Jestem geniuszem! Jednym słowem – matematyka. Pomysł jest taki, że każdy krok dzieli rozmiar oryginalnej tablicy przez 2. Liczba kroków oznacza, ile razy można podzielić oryginalną tablicę na dwie części. To jest dokładna definicja logarytmu (podstawa 2).

Faza sortowania

W fazie sortowania zaczynasz od tablic unitarnych (jednoelementowych). Podczas każdego kroku wykonujesz wiele operacji scalania, a całkowity koszt wynosi N = 8 operacji:

W pierwszym etapie masz 4 połączenia, z których każde kosztuje 2 operacje
W drugim kroku masz 2 połączenia, z których każde kosztuje 4 operacje
W trzecim kroku masz 1 połączenie, które kosztuje 8 operacji

Ponieważ istnieją kroki log(N), całkowity koszt N * operacje log(N)..

Zalety sortowania przez scalanie

Dlaczego ten algorytm jest tak potężny?

Ponieważ:

Możesz to zmienić, aby zmniejszyć zużycie pamięci i nie tworzyć nowych tablic, ale bezpośrednio modyfikować tablicę wejściową.

Uwaga: ten typ algorytmu nazywa się in-miejsce (sortowanie bez dodatkowej pamięci).

Można to zmienić, aby jednocześnie wykorzystywać miejsce na dysku i niewielką ilość pamięci, bez ponoszenia znacznych kosztów operacji we/wy dysku. Chodzi o to, aby załadować do pamięci tylko te części, które są aktualnie przetwarzane. Jest to ważne, gdy trzeba posortować wielogigabajtową tabelę przy użyciu jedynie 100-megabajtowego bufora pamięci.

Uwaga: ten typ algorytmu nazywa się sortowanie zewnętrzne.

Możesz go zmienić, aby działał na wielu procesach/wątkach/serwerach.

Na przykład rozproszone sortowanie przez scalanie jest jednym z kluczowych elementów Hadoop (która jest strukturą w dużych zbiorach danych).

Algorytm ten może zamienić ołów w złoto (naprawdę!).

Ten algorytm sortowania jest używany w większości (jeśli nie we wszystkich) bazach danych, ale nie jest jedyny. Jeśli chcesz dowiedzieć się więcej, możesz to przeczytać Praca badawcza, w którym omówiono zalety i wady popularnych algorytmów sortowania baz danych.

Tablica, drzewo i tablica mieszająca

Teraz, gdy rozumiemy ideę złożoności czasowej i sortowania, powinienem opowiedzieć o 3 strukturach danych. To ważne, bo oni stanowią podstawę nowoczesnych baz danych. Przedstawię również koncepcję indeks bazy danych.

Array

Tablica dwuwymiarowa jest najprostszą strukturą danych. Tabela może być traktowana jako tablica. Na przykład:

Ta dwuwymiarowa tablica jest tabelą zawierającą wiersze i kolumny:

Każda linia reprezentuje jednostkę
Kolumny przechowują właściwości opisujące jednostkę.
Każda kolumna przechowuje dane określonego typu (liczba całkowita, ciąg znaków, data...).

Jest to wygodne do przechowywania i wizualizacji danych, jednak gdy trzeba znaleźć konkretną wartość, nie jest to odpowiednie.

Na przykład, jeśli chcesz znaleźć wszystkich pracowników, którzy pracują w Wielkiej Brytanii, musisz sprawdzić każdy wiersz, aby ustalić, czy ten wiersz należy do Wielkiej Brytanii. Będzie Cię to kosztować N transakcjiGdzie N - liczba linii, co nie jest złe, ale czy może być szybszy sposób? Teraz przyszedł czas na zapoznanie się z drzewami.

Uwaga: Większość nowoczesnych baz danych udostępnia rozszerzone tablice do wydajnego przechowywania tabel: tabele zorganizowane na stercie i tabele zorganizowane na podstawie indeksu. Nie zmienia to jednak problemu szybkiego znalezienia konkretnego warunku w grupie kolumn.

Drzewo bazy danych i indeks

Drzewo wyszukiwania binarnego to drzewo binarne o specjalnej właściwości, kluczem w każdym węźle musi być:

większy niż wszystkie klucze przechowywane w lewym poddrzewie
mniej niż wszystkie klucze przechowywane w prawym poddrzewie

Zobaczmy, co to oznacza wizualnie

Pomysł

To drzewo ma N = 15 elementów. Powiedzmy, że szukam 208:

Zaczynam od korzenia, którego kluczem jest 136. Ponieważ 136<208, patrzę na prawe poddrzewo węzła 136.
398>208, dlatego patrzę na lewe poddrzewo węzła 398
250>208, dlatego patrzę na lewe poddrzewo węzła 250
200<208, dlatego patrzę na prawe poddrzewo węzła 200. Ale 200 nie ma prawego poddrzewa, wartość nie istnieje (ponieważ jeśli istnieje, będzie w prawym poddrzewie 200).

Powiedzmy teraz, że szukam 40

Zaczynam od korzenia, którego kluczem jest 136. Ponieważ 136 > 40, patrzę na lewe poddrzewo węzła 136.
80 > 40, dlatego patrzę na lewe poddrzewo węzła 80
40= 40, węzeł istnieje. Pobieram identyfikator wiersza wewnątrz węzła (niepokazany na obrazku) i szukam w tabeli podanego identyfikatora wiersza.
Znajomość identyfikatora wiersza pozwala mi dokładnie wiedzieć, gdzie znajdują się dane w tabeli, dzięki czemu mogę je natychmiast pobrać.

Ostatecznie oba wyszukiwania będą kosztować mnie liczbę poziomów w drzewie. Jeśli uważnie przeczytasz część dotyczącą sortowania przez scalanie, powinieneś zobaczyć, że istnieją poziomy log(N). Okazało się, przeszukaj dziennik kosztów (N), nie jest zły!

Wróćmy do naszego problemu

Ale to jest bardzo abstrakcyjne, więc wróćmy do naszego problemu. Zamiast prostej liczby całkowitej wyobraź sobie ciąg znaków reprezentujący kraj osoby z poprzedniej tabeli. Załóżmy, że masz drzewo zawierające pole „kraj” (kolumna 3) tabeli:

Jeśli chcesz wiedzieć kto pracuje w Wielkiej Brytanii
patrzysz na drzewo, aby uzyskać węzeł reprezentujący Wielką Brytanię
w „UKnode” znajdziesz lokalizację rekordów pracowników w Wielkiej Brytanii.

To wyszukiwanie będzie kosztować operacje log(N) zamiast N operacji, jeśli użyjesz tablicy bezpośrednio. To co właśnie przedstawiłeś indeks bazy danych.

Możesz zbudować drzewo indeksu dla dowolnej grupy pól (ciąg, liczba, 2 linie, liczba i ciąg, data...), o ile masz funkcję porównywania kluczy (tj. grup pól), dzięki czemu możesz ustawić porządek wśród kluczy (co ma miejsce w przypadku dowolnych podstawowych typów w bazie danych).

B+DrzewoIndeks

Chociaż to drzewo działa dobrze w celu uzyskania określonej wartości, w razie potrzeby pojawia się DUŻY problem uzyskać wiele elementów pomiędzy dwiema wartościami. Będzie to kosztować O(N), ponieważ będziesz musiał przyjrzeć się każdemu węzłowi w drzewie i sprawdzić, czy znajduje się pomiędzy tymi dwiema wartościami (np. przy uporządkowanym przejściu drzewa). Co więcej, ta operacja nie jest przyjazna dla operacji wejścia/wyjścia dysku, ponieważ trzeba przeczytać całe drzewo. Musimy znaleźć sposób na efektywną realizację żądanie zakresu. Aby rozwiązać ten problem, nowoczesne bazy danych wykorzystują zmodyfikowaną wersję poprzedniego drzewa o nazwie B+Tree. W drzewie B+Drzewo:

tylko najniższe węzły (liście) Przechowaj informację (lokalizacja wierszy w powiązanej tabeli)
reszta węzłów jest tutaj do routingu do prawidłowego węzła podczas wyszukiwania.

Jak widać, węzłów jest tu więcej (dwa razy). Rzeczywiście, masz dodatkowe węzły, „węzły decyzyjne”, które pomogą Ci znaleźć właściwy węzeł (który przechowuje lokalizację wierszy w powiązanej tabeli). Ale złożoność wyszukiwania nadal wynosi O(log(N)) (jest tylko jeszcze jeden poziom). Największą różnicą jest to węzły na niższym poziomie są połączone ze swoimi następcami.

W przypadku tego B+Tree, jeśli szukasz wartości od 40 do 100:

Musisz po prostu poszukać 40 (lub najbliższej wartości po 40, jeśli 40 nie istnieje), tak jak zrobiłeś to w poprzednim drzewie.
Następnie zbierz 40 spadkobierców, korzystając z bezpośrednich łączy spadkobierców, aż osiągniesz 100.

Załóżmy, że znalazłeś M następców, a drzewo ma N węzłów. Znalezienie konkretnego węzła kosztuje log(N), podobnie jak w poprzednim drzewie. Ale gdy już zdobędziesz ten węzeł, otrzymasz M następców w operacjach M z odniesieniami do ich następców. To wyszukiwanie kosztuje tylko M+log(N) operacji w porównaniu do N operacji w poprzednim drzewie. Co więcej, nie musisz czytać całego drzewa (tylko węzły M+log(N)), co oznacza mniejsze zużycie dysku. Jeśli M jest małe (np. 200 wierszy), a N jest duże (1 000 000 wierszy), będzie DUŻA różnica.

Ale tutaj pojawiają się nowe problemy (znowu!). Jeśli dodasz lub usuniesz wiersz w bazie danych (a tym samym w powiązanym indeksie B+Tree):

musisz zachować porządek między węzłami w drzewie B+, w przeciwnym razie nie będziesz w stanie znaleźć węzłów w nieposortowanym drzewie.
musisz zachować minimalną możliwą liczbę poziomów w B+Tree, w przeciwnym razie złożoność czasowa O(log(N)) stanie się O(N).

Innymi słowy, B+Tree musi być samoporządkujące i zrównoważone. Na szczęście jest to możliwe dzięki inteligentnym operacjom usuwania i wstawiania. Ale to ma swoją cenę: insercje i usunięcia w drzewie B+ kosztują O(log(N)). Dlatego niektórzy z Was to słyszeli używanie zbyt wielu indeksów nie jest dobrym pomysłem. Naprawdę, spowalniasz szybkie wstawianie/aktualizowanie/usuwanie wiersza w tabeliponieważ baza danych musi aktualizować indeksy tabeli przy użyciu kosztownej operacji O(log(N)) dla każdego indeksu. Co więcej, dodanie indeksów oznacza większe obciążenie pracą menadżer transakcji (zostanie opisane na końcu artykułu).

Więcej szczegółów znajdziesz w artykule na Wikipedii B+Drzewo. Jeśli chcesz przykład implementacji B+Tree w bazie danych, spójrz Ten artykuł и Ten artykuł od wiodącego programisty MySQL. Obydwa skupiają się na tym, jak InnoDB (silnik MySQL) obsługuje indeksy.

Uwaga: Czytelnik powiedział mi, że ze względu na optymalizacje niskiego poziomu drzewo B+ powinno być całkowicie zrównoważone.

Hashtable

Naszą ostatnią ważną strukturą danych jest tablica mieszająca. Jest to bardzo przydatne, gdy chcesz szybko sprawdzić wartości. Co więcej, zrozumienie tabeli mieszającej pomoże nam później zrozumieć typową operację łączenia bazy danych zwaną łączeniem mieszającym ( hash dołącz). Ta struktura danych jest również wykorzystywana przez bazę danych do przechowywania niektórych rzeczy wewnętrznych (np. zamek do stołu lub pula buforów, oba pojęcia zobaczymy później).

Tablica mieszająca to struktura danych, która szybko odnajduje element po swoim kluczu. Aby zbudować tabelę skrótów, musisz zdefiniować:

ключ dla Twoich elementów
funkcja skrótu na klucze. Obliczone skróty kluczy podają lokalizację elementów (tzw segmenty ).
funkcja porównywania kluczy. Po znalezieniu odpowiedniego segmentu musisz znaleźć w nim element, którego szukasz, korzystając z tego porównania.

Prosty przykład

Weźmy jasny przykład:

Ta tabela mieszająca ma 10 segmentów. Ponieważ jestem leniwy, zobrazowałem tylko 5 segmentów, ale wiem, że jesteś mądry, więc pozwolę ci zobrazować pozostałe 5 samodzielnie. Użyłem funkcji skrótu modulo 10 klucza. Innymi słowy, przechowuję tylko ostatnią cyfrę klucza elementu, aby znaleźć jego segment:

jeśli ostatnią cyfrą jest 0, element należy do segmentu 0,
jeśli ostatnią cyfrą jest 1, element należy do segmentu 1,
jeśli ostatnią cyfrą jest 2, element wpada do obszaru 2,
...

Funkcja porównawcza, której użyłem, to po prostu równość dwóch liczb całkowitych.

Powiedzmy, że chcesz uzyskać element 78:

Tabela mieszająca oblicza kod skrótu dla 78, czyli 8.
Tabela mieszająca sprawdza segment 8 i pierwszym znalezionym elementem jest 78.
Zwraca ci przedmiot 78
Wyszukiwanie kosztuje tylko 2 operacje (jeden do obliczenia wartości skrótu, a drugi do wyszukania elementu w segmencie).

Powiedzmy teraz, że chcesz uzyskać element 59:

Tabela mieszająca oblicza kod skrótu dla 59, czyli 9.
Tablica mieszająca przeszukuje segment 9, pierwszym znalezionym elementem jest 99. Ponieważ 99!=59, element 99 nie jest prawidłowym elementem.
Stosując tę samą logikę, bierzemy drugi element (9), trzeci (79), ..., ostatni (29).
Nie znaleziono elementu.
Poszukiwania kosztowały 7 operacji.

Dobra funkcja skrótu

Jak widać, w zależności od wartości, której szukasz, koszt nie jest taki sam!

Jeśli teraz zmienię funkcję skrótu modulo 1 000 000 klucza (to znaczy biorąc ostatnie 6 cyfr), drugie wyszukiwanie kosztuje tylko 1 operację, ponieważ w segmencie 000059 nie ma żadnych elementów. Prawdziwym wyzwaniem jest znalezienie dobrej funkcji skrótu, która utworzy segmenty zawierające bardzo małą liczbę elementów.

W moim przykładzie znalezienie dobrej funkcji skrótu jest łatwe. Ale to jest prosty przykład. Znalezienie dobrej funkcji skrótu jest trudniejsze, gdy kluczem jest:

ciąg (na przykład - nazwisko)
2 linie (na przykład - nazwisko i imię)
2 linie i data (np. nazwisko, imię i data urodzenia)
...

Przy dobrej funkcji skrótu przeszukiwanie tablicy mieszającej kosztuje O(1).

Tablica a tabela mieszająca

Dlaczego nie użyć tablicy?

Hm, dobre pytanie.

Tabela mieszająca może być częściowo załadowany do pamięci, a pozostałe segmenty mogą pozostać na dysku.
W przypadku tablicy należy używać ciągłej przestrzeni w pamięci. Jeśli ładujesz duży stół bardzo trudno jest znaleźć wystarczającą ilość ciągłej przestrzeni.
W przypadku tabeli skrótów możesz wybrać żądany klucz (na przykład kraj i nazwisko osoby).

Aby uzyskać więcej informacji, możesz przeczytać artykuł na temat JavaHashMapa, co jest wydajną implementacją tablicy mieszającej; nie musisz znać języka Java, aby zrozumieć pojęcia omówione w tym artykule.

Źródło: www.habr.com

Jak działają relacyjne bazy danych (część 1)