Čau Habr! Do pozornosti dávam preklad článku
"Ako funguje relačná databáza".

Pokiaľ ide o relačné databázy, nemôžem si pomôcť, ale myslím si, že niečo chýba. Používajú sa všade. K dispozícii je veľa rôznych databáz, od malých a užitočných SQLite až po výkonné Teradata. Existuje však len niekoľko článkov, ktoré vysvetľujú, ako databáza funguje. Môžete sa sami vyhľadať pomocou „howdoesarelationaldatabasework“ a zistiť, koľko výsledkov je k dispozícii. Navyše sú tieto články krátke. Ak hľadáte najnovšie rušné technológie (BigData, NoSQL alebo JavaScript), nájdete tu podrobnejšie články vysvetľujúce, ako fungujú.

Sú relačné databázy príliš staré a príliš nudné na to, aby sa dali vysvetľovať mimo univerzitných kurzov, výskumných prác a kníh?

Ako vývojár neznášam používanie niečoho, čomu nerozumiem. A ak sa databázy používajú viac ako 40 rokov, musí na to byť dôvod. V priebehu rokov som strávil stovky hodín, aby som skutočne pochopil tieto zvláštne čierne skrinky, ktoré používam každý deň. Relačné databázy veľmi zaujímavé, pretože oni založené na užitočných a opakovane použiteľných konceptoch. Ak máte záujem porozumieť databáze, ale nikdy ste nemali čas alebo chuť ponoriť sa do tejto širokej témy, tento článok by sa vám mal páčiť.

Aj keď je názov tohto článku jasný, Účelom tohto článku nie je pochopiť, ako používať databázu. teda už by ste mali vedieť napísať jednoduchú žiadosť o pripojenie a základné otázky Crud; inak tomuto článku možno nerozumieš. To je jediná vec, ktorú potrebujete vedieť, zvyšok vysvetlím.

Začnem niektorými základmi informatiky, ako je časová zložitosť algoritmov (BigO). Viem, že niektorí z vás nenávidia tento koncept, ale bez neho nebudete schopní pochopiť zložitosti vnútri databázy. Keďže ide o veľkú tému, zameriam sa na čo si myslím, že je dôležité: ako databáza spracováva SQL dotaz. Len sa predstavím základné databázové konceptyaby ste na konci článku mali predstavu o tom, čo sa deje pod kapotou.

Keďže ide o dlhý a technický článok, ktorý zahŕňa množstvo algoritmov a dátových štruktúr, nájdite si čas na jeho prečítanie. Niektoré pojmy môžu byť ťažko pochopiteľné; môžete ich preskočiť a získať všeobecnú predstavu.

Pre znalejších z vás je tento článok rozdelený na 3 časti:

Prehľad nízkoúrovňových a vysokoúrovňových databázových komponentov
Prehľad procesu optimalizácie dopytu
Prehľad správy transakcií a vyrovnávacej pamäte

Spať k základom

Pred rokmi (v galaxii ďaleko, ďaleko...) museli vývojári presne vedieť, koľko operácií kódujú. Poznali svoje algoritmy a dátové štruktúry naspamäť, pretože si nemohli dovoliť plytvať CPU a pamäťou svojich pomalých počítačov.

V tejto časti vám pripomeniem niektoré z týchto pojmov, pretože sú nevyhnutné na pochopenie databázy. Predstavím aj koncept databázový index.

O(1) vs O(n2)

V súčasnosti sa veľa vývojárov nezaujíma o časovú zložitosť algoritmov... a majú pravdu!

Ale keď máte čo do činenia s množstvom údajov (nehovorím o tisícoch) alebo ak máte problémy v priebehu milisekúnd, je dôležité pochopiť tento koncept. A ako si viete predstaviť, databázy sa musia vysporiadať s oboma situáciami! Nebudem vás nútiť tráviť viac času, ako je potrebné, aby ste pochopili podstatu. To nám neskôr pomôže pochopiť koncepciu optimalizácie založenej na nákladoch (náklady na základe optimalizácia).

Pojem

Časová zložitosť algoritmu slúži na zistenie, ako dlho bude trvať spustenie algoritmu pre dané množstvo údajov. Na opísanie tejto zložitosti používame matematickú notáciu veľkého O. Táto notácia sa používa s funkciou, ktorá popisuje, koľko operácií potrebuje algoritmus pre daný počet vstupov.

Napríklad, keď poviem „tento algoritmus má zložitosť O(nejaká_funkcia())“, znamená to, že algoritmus vyžaduje operácie some_function(a_urtain_amount_of_data) na spracovanie určitého množstva údajov.

V tomto prípade, Nie je dôležité množstvo údajov**, inak ** ako sa zvyšuje počet operácií so zvyšujúcim sa objemom dát. Časová zložitosť neposkytuje presný počet operácií, ale je to dobrý spôsob, ako odhadnúť čas vykonania.

V tomto grafe môžete vidieť počet operácií oproti množstvu vstupných údajov pre rôzne typy časovej zložitosti algoritmu. Na ich zobrazenie som použil logaritmickú stupnicu. Inými slovami, množstvo údajov sa rýchlo zvýši z 1 na 1 miliardu. Vidíme, že:

O(1) alebo konštantná zložitosť zostáva konštantná (inak by sa to nenazývalo konštantná zložitosť).
O(záznam(n)) zostáva nízka aj pri miliardách údajov.
Najhoršia obtiažnosť - O(n2), kde počet operácií rýchlo rastie.
Rovnako rýchlo pribúdajú aj ďalšie dve komplikácie.

príklady

Pri malom množstve údajov je rozdiel medzi O(1) a O(n2) zanedbateľný. Povedzme napríklad, že máte algoritmus, ktorý potrebuje spracovať 2000 prvkov.

Algoritmus O(1) vás bude stáť 1 operáciu
Algoritmus O(log(n)) vás bude stáť 7 operácií
Algoritmus O(n) vás bude stáť 2 000 operácií
Algoritmus O(n*log(n)) vás bude stáť 14 000 operácií
Algoritmus O(n2) vás bude stáť 4 000 000 operácií

Rozdiel medzi O(1) a O(n2) sa zdá byť veľký (4 milióny operácií), ale stratíte maximálne 2 ms, akurát čas na žmurknutie očí. Moderné procesory totiž dokážu spracovať stovky miliónov operácií za sekundu. To je dôvod, prečo výkon a optimalizácia nie sú problémom v mnohých IT projektoch.

Ako som už povedal, pri práci s obrovským množstvom dát je stále dôležité poznať tento pojem. Ak tentoraz musí algoritmus spracovať 1 000 000 prvkov (čo nie je toľko pre databázu):

Algoritmus O(1) vás bude stáť 1 operáciu
Algoritmus O(log(n)) vás bude stáť 14 operácií
Algoritmus O(n) vás bude stáť 1 000 000 operácií
Algoritmus O(n*log(n)) vás bude stáť 14 000 000 operácií
Algoritmus O(n2) vás bude stáť 1 000 000 000 000 operácií

Nepočítal som to, ale povedal by som, že s algoritmom O(n2) máte čas vypiť kávu (aj dve!). Ak k objemu dát pridáte ďalšiu 0, stihnete si zdriemnuť.

Poďme hlbšie

Pre vaše informácie:

Dobré vyhľadávanie v hašovacej tabuľke nájde prvok v O(1).
Vyhľadávanie vo vyváženom strome poskytuje výsledky v O(log(n)).
Vyhľadávanie poľa produkuje výsledky v O(n).
Najlepšie triediace algoritmy majú zložitosť O(n*log(n)).
Zlý triediaci algoritmus má zložitosť O(n2).

Poznámka: V nasledujúcich častiach uvidíme tieto algoritmy a dátové štruktúry.

Existuje niekoľko typov časovej zložitosti algoritmov:

priemerný scenár
najlepší možný scenár
a najhorší scenár

Časová zložitosť je často najhorším scenárom.

Hovoril som len o časovej zložitosti algoritmu, ale zložitosť platí aj pre:

spotreba pamäte algoritmu
Algoritmus spotreby I/O disku

Samozrejme, existujú komplikácie horšie ako n2, napríklad:

n4: to je hrozné! Niektoré zo spomínaných algoritmov majú túto zložitosť.
3n: toto je ešte horšie! Jeden z algoritmov, ktoré uvidíme v strede tohto článku, má túto zložitosť (a v skutočnosti sa používa v mnohých databázach).
faktoriál n: svoje výsledky nikdy nedosiahnete ani s malým množstvom údajov.
nn: Ak sa stretnete s touto zložitosťou, mali by ste si položiť otázku, či je to skutočne oblasť vašej činnosti...

Poznámka: Neposkytol som vám skutočnú definíciu označenia veľkého O, len nápad. Tento článok si môžete prečítať na Wikipedia pre skutočnú (asymptotickú) definíciu.

MergeSort

Čo robíte, keď potrebujete triediť zbierku? Čo? Zavoláte funkciu sort()... Ok, dobrá odpoveď... Ale pre databázu musíte pochopiť, ako táto funkcia sort() funguje.

Existuje niekoľko dobrých triediacich algoritmov, takže sa zameriam na tie najdôležitejšie: zlúčiť triediť. Možno nerozumiete, prečo je triedenie údajov práve teraz užitočné, ale po časti optimalizácie dotazu by ste to mali urobiť. Okrem toho, pochopenie zlučovacieho triedenia nám neskôr pomôže pochopiť spoločnú operáciu spojenia databáz nazývanú spojiť spojiť (zlúčenie združenia).

Zlúčiť

Rovnako ako mnoho užitočných algoritmov, zlučovacie triedenie sa spolieha na trik: spojenie 2 triedených polí veľkosti N/2 do N-prvkového triedeného poľa stojí iba N operácií. Táto operácia sa nazýva zlučovanie.

Pozrime sa, čo to znamená, na jednoduchom príklade:

Tento obrázok ukazuje, že na zostavenie konečného zoradeného 8-prvkového poľa stačí iterovať iba raz cez 2 4-prvkové polia. Keďže obe 4-prvkové polia sú už zoradené:

1) porovnáte oba prúdové prvky v dvoch poliach (na začiatku prúd = prvý)
2) potom zoberte najmenšiu a vložte ju do poľa s 8 prvkami
3) a prejdite na ďalší prvok v poli, kde ste vzali najmenší prvok
a opakujte 1,2,3, kým nedosiahnete posledný prvok jedného z polí.
Potom zoberiete zostávajúce prvky z druhého poľa a vložíte ich do poľa s 8 prvkami.

Funguje to preto, že obe 4-prvkové polia sú zoradené, takže sa v týchto poliach nemusíte "vracať".

Teraz, keď rozumieme triku, tu je môj pseudokód na zlúčenie:

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;

Merge sort rozdelí problém na menšie problémy a potom nájde výsledky menších problémov, aby získal výsledok pôvodného problému (poznámka: tento typ algoritmu sa nazýva rozdeľ a panuj). Ak tomuto algoritmu nerozumiete, nebojte sa; Nechápal som to, keď som to prvýkrát videl. Ak vám to môže pomôcť, vidím tento algoritmus ako dvojfázový algoritmus:

Fáza delenia, kde je pole rozdelené na menšie polia
Fáza triedenia je tam, kde sa kombinujú malé polia (pomocou spojenia), aby sa vytvorilo väčšie pole.

Fáza delenia

Vo fáze delenia je pole rozdelené na unitárne polia v 3 krokoch. Formálny počet krokov je log(N) (keďže N=8, log(N) = 3).

Ako to mám vedieť?

Som génius! Jedným slovom - matematika. Myšlienka je taká, že každý krok delí veľkosť pôvodného poľa o 2. Počet krokov je počet, koľkokrát môžete rozdeliť pôvodné pole na dva. Toto je presná definícia logaritmu (základ 2).

Fáza triedenia

Vo fáze triedenia začínate s unitárnymi (jednoprvkovými) poliami. Počas každého kroku použijete viacero operácií zlúčenia a celkové náklady sú N = 8 operácií:

V prvej fáze máte 4 zlúčenia, z ktorých každá stojí 2 operácie
V druhom kroku máte 2 zlúčenia, z ktorých každé stojí 4 operácie
V treťom kroku máte 1 zlúčenie, ktoré stojí 8 operácií

Keďže existujú log(N) kroky, celkové náklady N * log(N) operácie.

Výhody zlučovacieho triedenia

Prečo je tento algoritmus taký výkonný?

Pretože:

Môžete ho zmeniť, aby ste znížili nároky na pamäť, takže nebudete vytvárať nové polia, ale priamo upravovať vstupné pole.

Poznámka: Tento typ algoritmu sa nazýva in-miesto (triedenie bez dodatočnej pamäte).

Môžete ho zmeniť tak, aby súčasne využíval miesto na disku a malé množstvo pamäte bez výraznej réžie diskových I/O. Cieľom je načítať do pamäte iba tie časti, ktoré sa práve spracúvajú. Je to dôležité, keď potrebujete triediť viacgigabajtovú tabuľku iba so 100-megabajtovou vyrovnávacou pamäťou.

Poznámka: Tento typ algoritmu sa nazýva externé triedenie.

Môžete ho zmeniť tak, aby bežal na viacerých procesoch/vláknach/serveroch.

Jedným z kľúčových komponentov je napríklad triedenie distribuovaného zlúčenia Hadoop (čo je štruktúra veľkých dát).

Tento algoritmus dokáže premeniť olovo na zlato (naozaj!).

Tento triediaci algoritmus sa používa vo väčšine (ak nie vo všetkých) databázach, ale nie je jediný. Ak chcete vedieť viac, môžete si prečítať toto výskumná práca, ktorá pojednáva o výhodách a nevýhodách bežných algoritmov triedenia databáz.

Pole, strom a tabuľka hash

Teraz, keď chápeme myšlienku časovej zložitosti a triedenia, mal by som vám povedať o 3 dátových štruktúrach. To je dôležité, pretože oni sú základom moderných databáz. Predstavím aj koncept databázový index.

rad

Dvojrozmerné pole je najjednoduchšia dátová štruktúra. Tabuľku si možno predstaviť ako pole. Napríklad:

Toto 2-rozmerné pole je tabuľka s riadkami a stĺpcami:

Každý riadok predstavuje entitu
Stĺpce ukladajú vlastnosti, ktoré popisujú entitu.
Každý stĺpec obsahuje údaje špecifického typu (celé číslo, reťazec, dátum...).

To je vhodné na ukladanie a vizualizáciu údajov, ale keď potrebujete nájsť konkrétnu hodnotu, nie je to vhodné.

Ak by ste napríklad chceli nájsť všetkých ľudí, ktorí pracujú v Spojenom kráľovstve, museli by ste sa pozrieť na každý riadok, aby ste zistili, či daný riadok patrí Spojenému kráľovstvu. Bude vás to stáť N transakciíKde N - počet riadkov, čo nie je zlé, ale mohol by existovať rýchlejší spôsob? Teraz je čas, aby sme sa zoznámili so stromami.

Poznámka: Väčšina moderných databáz poskytuje rozšírené polia na efektívne ukladanie tabuliek: heap-organizedtables a index-organizedtables. To však nič nemení na probléme rýchleho nájdenia konkrétneho stavu v skupine stĺpcov.

Databázový strom a index

Binárny vyhľadávací strom je binárny strom so špeciálnou vlastnosťou, kľúč v každom uzle musí byť:

väčšie ako všetky kľúče uložené v ľavom podstrome
menej ako všetky kľúče uložené v pravom podstrome

Pozrime sa, čo to znamená vizuálne

Nápad

Tento strom má N = 15 prvkov. Povedzme, že hľadám 208:

Začnem od koreňa, ktorého kľúč je 136. Od 136<208 sa pozriem na pravý podstrom uzla 136.
398>208, preto sa pozerám na ľavý podstrom uzla 398
250>208, preto sa pozerám na ľavý podstrom uzla 250
200<208, preto sa pozerám na pravý podstrom uzla 200. Ale 200 nemá žiadny pravý podstrom, hodnota neexistuje (pretože ak existuje, bude v pravom podstrome 200).

Teraz povedzme, že hľadám 40

Začnem od koreňa, ktorého kľúč je 136. Od 136 > 40 sa pozriem na ľavý podstrom uzla 136.
80 > 40, preto sa pozerám na ľavý podstrom uzla 80
40 = 40, uzol existuje. Získam ID riadku vo vnútri uzla (nie je znázornené na obrázku) a v tabuľke hľadám dané ID riadku.
Poznanie ID riadku mi umožňuje presne vedieť, kde sa údaje v tabuľke nachádzajú, takže ich môžem okamžite získať.

V konečnom dôsledku ma obe vyhľadávania budú stáť počet úrovní vo vnútri stromu. Ak si pozorne prečítate časť o triedení zlúčením, mali by ste vidieť, že existujú úrovne log(N). Ukázalo sa, hľadať denník nákladov (N), nie zlé!

Vráťme sa k nášmu problému

Ale to je veľmi abstraktné, takže sa vráťme k nášmu problému. Namiesto jednoduchého celého čísla si predstavte reťazec, ktorý predstavuje krajinu niekoho z predchádzajúcej tabuľky. Povedzme, že máte strom, ktorý obsahuje pole „krajina“ (stĺpec 3) tabuľky:

Ak chcete vedieť, kto pracuje vo Veľkej Británii
pozriete sa na strom a získate uzol, ktorý predstavuje Veľkú Britániu
vnútri "UKnode" nájdete umiestnenie záznamov pracovníkov Spojeného kráľovstva.

Toto vyhľadávanie bude stáť log(N) operácií namiesto N operácií, ak použijete pole priamo. To, čo ste práve prezentovali, bolo databázový index.

Môžete vytvoriť indexový strom pre akúkoľvek skupinu polí (reťazec, číslo, 2 riadky, číslo a reťazec, dátum...), pokiaľ máte funkciu na porovnávanie kľúčov (tj skupiny polí), takže môžete nastaviť poradie medzi kľúčmi (čo je prípad všetkých základných typov v databáze).

B+TreeIndex

Aj keď tento strom funguje dobre na získanie konkrétnej hodnoty, v prípade potreby nastáva VEĽKÝ problém získať viacero prvkov medzi dvoma hodnotami. Bude to stáť O(N), pretože sa budete musieť pozrieť na každý uzol v strome a skontrolovať, či je medzi týmito dvoma hodnotami (napríklad pri usporiadanom prechode stromom). Navyše táto operácia nie je priateľská k diskovým I/O, pretože musíte prečítať celý strom. Musíme nájsť spôsob, ako efektívne vykonávať žiadosť o rozsah. Na vyriešenie tohto problému moderné databázy používajú upravenú verziu predchádzajúceho stromu s názvom B+Tree. V strome B+Strom:

iba najnižšie uzly (listy) uložiť informácie (umiestnenie riadkov v súvisiacej tabuľke)
ostatné uzly sú tu na smerovanie do správneho uzla počas vyhľadávania.

Ako vidíte, uzlov je tu viac (dvakrát). V skutočnosti máte ďalšie uzly, "rozhodovacie uzly", ktoré vám pomôžu nájsť správny uzol (ktorý ukladá umiestnenie riadkov v pridruženej tabuľke). Zložitosť vyhľadávania je však stále O(log(N)) (existuje len jedna úroveň navyše). Veľký rozdiel je v tom uzly na nižšej úrovni sú spojené s ich nástupcami.

S týmto B+Stromom, ak hľadáte hodnoty medzi 40 a 100:

Stačí vyhľadať 40 (alebo najbližšiu hodnotu po 40, ak 40 neexistuje), ako ste to urobili s predchádzajúcim stromom.
Potom zozbierajte 40 dedičov pomocou priamych dedičských väzieb, kým nedosiahnete 100.

Povedzme, že nájdete M nástupcov a strom má N uzlov. Nájdenie konkrétneho uzla log(N) ako predchádzajúci strom. Ale akonáhle získate tento uzol, získate M nástupcov v operáciách M s odkazmi na ich nástupcov. Toto vyhľadávanie stojí iba M+log(N) operácií v porovnaní s N operáciami v predchádzajúcom strome. Navyše nemusíte čítať celý strom (iba uzly M+log(N), čo znamená menšie využitie disku. Ak je M malé (napr. 200 riadkov) a N je veľké (1 000 000 riadkov), bude VEĽKÝ rozdiel.

Ale sú tu nové problémy (opäť!). Ak pridáte alebo odstránite riadok v databáze (a teda v súvisiacom indexe B+Strom):

musíte udržiavať poriadok medzi uzlami vo vnútri B+stromu, inak nebudete môcť nájsť uzly v netriedenom strome.
musíte dodržať minimálny možný počet úrovní v B+strom, inak sa časová zložitosť O(log(N)) zmení na O(N).

Inými slovami, B+Strom musí byť samoobslužný a vyvážený. Našťastie je to možné pomocou operácií inteligentného vymazania a vloženia. To však niečo stojí: vloženia a vymazania v strome B+ stoja O(log(N)). Preto to niektorí z vás počuli používať príliš veľa indexov nie je dobrý nápad. naozaj, spomaľujete rýchle vkladanie/aktualizovanie/odstraňovanie riadku v tabuľkepretože databáza potrebuje aktualizovať indexy tabuľky pomocou drahej operácie O(log(N)) pre každý index. Okrem toho pridávanie indexov znamená väčšie pracovné zaťaženie manažér transakcií (bude popísané na konci článku).

Ďalšie podrobnosti nájdete v článku na Wikipédii B+strom. Ak chcete príklad implementácie B+Stromu v databáze, pozrite sa tento článok и tento článok od popredného vývojára MySQL. Obaja sa zameriavajú na to, ako InnoDB (motor MySQL) spracováva indexy.

Poznámka: Čitateľ mi povedal, že kvôli optimalizácii na nízkej úrovni by mal byť strom B+ úplne vyvážený.

Hashtable

Našou poslednou dôležitou dátovou štruktúrou je hašovacia tabuľka. To je veľmi užitočné, keď chcete rýchlo vyhľadať hodnoty. Okrem toho, pochopenie hašovacej tabuľky nám neskôr pomôže pochopiť bežnú operáciu spojenia databázy nazývanú hašovacie spojenie ( hash join). Túto dátovú štruktúru využíva aj databáza na ukladanie niektorých interných vecí (napr. uzamykateľný stôl alebo buffer pool, oba tieto koncepty uvidíme neskôr).

Hašovacia tabuľka je dátová štruktúra, ktorá rýchlo nájde prvok podľa svojho kľúča. Na vytvorenie hašovacej tabuľky musíte definovať:

kľúč pre vaše prvky
hašovacia funkcia pre kľúče. Vypočítané kľúče hash dávajú umiestnenie prvkov (tzv segmentov ).
funkcia na porovnávanie kľúčov. Keď nájdete správny segment, musíte pomocou tohto porovnania nájsť prvok, ktorý hľadáte v rámci segmentu.

Jednoduchý príklad

Uveďme si jasný príklad:

Táto hašovacia tabuľka má 10 segmentov. Pretože som lenivý, nafotil som len 5 segmentov, ale viem, že si šikovný, tak ťa nechám, aby si si ostatných 5 nafotil sám. Použil som hašovaciu funkciu modulo 10 kľúča. Inými slovami, ukladám iba poslednú číslicu kľúča prvku, aby som našiel jeho segment:

ak je posledná číslica 0, prvok spadá do segmentu 0,
ak je posledná číslica 1, prvok spadá do segmentu 1,
ak je posledná číslica 2, prvok spadá do oblasti 2,
...

Porovnávacia funkcia, ktorú som použil, je jednoducho rovnosť medzi dvoma celými číslami.

Povedzme, že chcete získať prvok 78:

Tabuľka hash vypočíta hash kód pre 78, čo je 8.
Tabuľka hash sa pozrie na segment 8 a prvý prvok, ktorý nájde, je 78.
Vráti vám položku 78
Vyhľadávanie stojí len 2 operácie (jeden na výpočet hodnoty hash a druhý na vyhľadanie prvku v segmente).

Teraz povedzme, že chcete získať prvok 59:

Tabuľka hash vypočíta hash kód pre 59, čo je 9.
Hašovacia tabuľka hľadá v segmente 9, prvý nájdený prvok je 99. Keďže 99!=59, prvok 99 nie je platným prvkom.
Pomocou rovnakej logiky sa vezme druhý prvok (9), tretí (79), ..., posledný (29).
Prvok sa nenašiel.
Pátranie stálo 7 operácií.

Dobrá hašovacia funkcia

Ako vidíte, v závislosti od hodnoty, ktorú hľadáte, cena nie je rovnaká!

Ak teraz zmením hašovaciu funkciu modulo 1 000 000 kľúča (to znamená, že vezmem posledných 6 číslic), druhé vyhľadávanie stojí iba 1 operáciu, pretože v segmente 000059 nie sú žiadne prvky. Skutočnou výzvou je nájsť dobrú hašovaciu funkciu, ktorá vytvorí vedrá obsahujúce veľmi malý počet prvkov.

V mojom príklade je nájdenie dobrej hašovacej funkcie jednoduché. Ale toto je jednoduchý príklad, nájsť dobrú hašovaciu funkciu je ťažšie, keď je kľúč:

reťazec (napríklad - priezvisko)
2 riadky (napríklad – priezvisko a meno)
2 riadky a dátum (napríklad - priezvisko, meno a dátum narodenia)
...

Vďaka dobrej hašovacej funkcii stojí vyhľadávanie v hašovacej tabuľke 1(XNUMX).

Pole vs hašovacia tabuľka

Prečo nepoužiť pole?

Hmm, dobrá otázka.

Hašovacia tabuľka môže byť čiastočne načítané do pamätea zostávajúce segmenty môžu zostať na disku.
S poľom musíte použiť súvislý priestor v pamäti. Ak načítate veľký stôl je veľmi ťažké nájsť dostatok súvislého priestoru.
V prípade hašovacej tabuľky si môžete vybrať požadovaný kľúč (napríklad krajinu a priezvisko osoby).

Pre viac informácií si môžete prečítať článok o JávaHashMap, čo je efektívna implementácia hašovacej tabuľky; na pochopenie pojmov obsiahnutých v tomto článku nemusíte rozumieť jazyku Java.

Zdroj: hab.com

Ako fungujú relačné databázy (1. časť)