Čau Habr! Předkládám vaší pozornosti překlad článku
"Jak funguje relační databáze".

Pokud jde o relační databáze, nemohu si pomoci, ale myslím, že něco chybí. Používají se všude. K dispozici je mnoho různých databází, od malých a užitečných SQLite až po výkonná Teradata. Existuje ale jen pár článků, které vysvětlují, jak databáze funguje. Můžete se sami vyhledat pomocí „howdoesarelationaldatabasework“, abyste viděli, jak málo výsledků existuje. Navíc jsou tyto články krátké. Pokud hledáte nejnovější rušné technologie (BigData, NoSQL nebo JavaScript), najdete podrobnější články vysvětlující, jak fungují.

Jsou relační databáze příliš staré a příliš nudné na to, aby byly vysvětlovány mimo univerzitní kurzy, výzkumné práce a knihy?

Jako vývojář nesnáším používání něčeho, čemu nerozumím. A pokud se databáze používají déle než 40 let, musí k tomu být důvod. V průběhu let jsem strávil stovky hodin, abych skutečně porozuměl těmto podivným černým skříňkám, které používám každý den. Relační databáze velmi zajímavé, protože oni založené na užitečných a opakovaně použitelných konceptech. Pokud máte zájem porozumět databázi, ale nikdy jste neměli čas nebo chuť ponořit se do tohoto širokého tématu, měl by se vám tento článek líbit.

Ačkoli je název tohoto článku jasný, Účelem tohoto článku není pochopit, jak používat databázi, proto, měli byste již vědět, jak napsat jednoduchý požadavek na připojení a základní dotazy KRUTÝ; jinak tento článek možná nepochopíte. To je jediná věc, kterou potřebujete vědět, zbytek vysvětlím.

Začnu některými základy informatiky, jako je časová složitost algoritmů (BigO). Vím, že někteří z vás tento koncept nenávidí, ale bez něj nebudete schopni pochopit složitosti uvnitř databáze. Protože se jedná o velké téma, zaměřím se na co považuji za důležité: jak databáze probíhá SQL poptávka. Jen se představím základní databázové konceptyabyste na konci článku měli představu o tom, co se děje pod kapotou.

Protože se jedná o dlouhý a technický článek, který zahrnuje mnoho algoritmů a datových struktur, věnujte čas jeho přečtení. Některé pojmy mohou být obtížné pochopit; můžete je přeskočit a přesto získat obecnou představu.

Pro znalejší z vás je tento článek rozdělen do 3 částí:

Přehled nízkoúrovňových a vysokoúrovňových databázových komponent
Přehled procesu optimalizace dotazu
Přehled správy transakcí a vyrovnávací paměti

Zpět k základům

Před lety (v galaxii daleko, daleko...) museli vývojáři přesně znát počet operací, které kódovali. Znali své algoritmy a datové struktury nazpaměť, protože si nemohli dovolit plýtvat CPU a pamětí svých pomalých počítačů.

V této části vám připomenu některé z těchto pojmů, protože jsou nezbytné pro pochopení databáze. Představím také koncept index databáze.

O(1) vs O(n2)

V dnešní době se mnoho vývojářů nezajímá o časovou složitost algoritmů... a mají pravdu!

Ale když máte co do činění s velkým množstvím dat (nemluvím o tisících) nebo pokud se trápíte v milisekundách, je důležité tento koncept pochopit. A jak si dokážete představit, databáze se musí vypořádat s oběma situacemi! Nebudu vás nutit trávit více času, než je nutné, abyste pochopili podstatu věci. To nám později pomůže pochopit koncept optimalizace založené na nákladech (stát na základě optimalizace).

Koncepce

Časová složitost algoritmu slouží ke zjištění, jak dlouho bude trvat provedení algoritmu pro dané množství dat. K popisu této složitosti používáme matematickou notaci velkého O. Tato notace se používá s funkcí, která popisuje, kolik operací algoritmus potřebuje pro daný počet vstupů.

Když například řeknu „tento algoritmus má složitost O(nejaká_funkce())“, znamená to, že algoritmus vyžaduje operace nějaké_funkce (určité_množství_dat) ke zpracování určitého množství dat.

V tomto případě, Na množství dat nezáleží**, v opačném případě ** jak se zvyšuje počet operací s rostoucím objemem dat. Časová složitost neposkytuje přesný počet operací, ale je to dobrý způsob, jak odhadnout dobu provádění.

V tomto grafu můžete vidět počet operací versus množství vstupních dat pro různé typy časové složitosti algoritmu. K jejich zobrazení jsem použil logaritmickou stupnici. Jinými slovy, množství dat se rychle zvýší z 1 na 1 miliardu. Vidíme, že:

O(1) neboli konstantní složitost zůstává konstantní (jinak by se tomu neříkalo konstantní složitost).
O(přihlásit(n)) zůstává nízká i s miliardami dat.
Nejhorší obtížnost - O(n2), kde počet operací rychle roste.
Stejně rychle přibývají další dvě komplikace.

Příklady

Při malém množství dat je rozdíl mezi O(1) a O(n2) zanedbatelný. Řekněme například, že máte algoritmus, který potřebuje zpracovat 2000 prvků.

Algoritmus O(1) vás bude stát 1 operaci
Algoritmus O(log(n)) vás bude stát 7 operací
Algoritmus O(n) vás bude stát 2 000 operací
Algoritmus O(n*log(n)) vás bude stát 14 000 operací
Algoritmus O(n2) vás bude stát 4 000 000 operací

Rozdíl mezi O(1) a O(n2) se zdá velký (4 miliony operací), ale ztratíte maximálně 2 ms, akorát čas na mrknutí očí. Moderní procesory skutečně zpracovávají stovky milionů operací za sekundu. To je důvod, proč výkon a optimalizace nejsou problémem mnoha IT projektů.

Jak jsem řekl, při práci s obrovským množstvím dat je stále důležité tento pojem znát. Pokud tentokrát musí algoritmus zpracovat 1 000 000 prvků (což není tolik pro databázi):

Algoritmus O(1) vás bude stát 1 operaci
Algoritmus O(log(n)) vás bude stát 14 operací
Algoritmus O(n) vás bude stát 1 000 000 operací
Algoritmus O(n*log(n)) vás bude stát 14 000 000 operací
Algoritmus O(n2) vás bude stát 1 000 000 000 000 operací

Nepočítal jsem to, ale řekl bych, že s algoritmem O(n2) máte čas vypít kávu (dokonce dvě!). Pokud k objemu dat přidáte další 0, budete mít čas si zdřímnout.

Pojďme hlouběji

Pro vaše informace:

Dobré vyhledávání v hashovací tabulce najde prvek v O(1).
Hledání dobře vyváženého stromu dává výsledky v O(log(n)).
Prohledávání pole dává výsledky v O(n).
Nejlepší třídicí algoritmy mají složitost O(n*log(n)).
Špatný třídicí algoritmus má složitost O(n2).

Poznámka: V následujících částech uvidíme tyto algoritmy a datové struktury.

Existuje několik typů časové složitosti algoritmu:

průměrný případový scénář
nejlepší scénář
a nejhorší scénář

Časová složitost je často tím nejhorším scénářem.

Mluvil jsem pouze o časové složitosti algoritmu, ale složitost platí také pro:

spotřeba paměti algoritmu
algoritmus spotřeby I/O disku

Samozřejmě existují komplikace horší než n2, například:

n4: to je hrozné! Některé ze zmíněných algoritmů mají tuto složitost.
3n: to je ještě horší! Jeden z algoritmů, které uvidíme uprostřed tohoto článku, má tuto složitost (a ve skutečnosti se používá v mnoha databázích).
faktoriál n: nikdy nedosáhnete svých výsledků ani s malým množstvím dat.
nn: Pokud se setkáte s touto složitostí, měli byste si položit otázku, zda je to skutečně vaše pole působnosti...

Poznámka: Skutečnou definici označení velkého O jsem vám nedal, jen představu. Tento článek si můžete přečíst na Wikipedia pro skutečnou (asymptotickou) definici.

Sloučit třídění

Co děláte, když potřebujete třídit sbírku? Co? Zavoláte funkci sort()... Dobrá, dobrá odpověď... Ale pro databázi musíte pochopit, jak tato funkce sort() funguje.

Existuje několik dobrých třídicích algoritmů, takže se zaměřím na ty nejdůležitější: Sloučit třídění. Možná nechápete, proč je třídění dat právě teď užitečné, ale po části optimalizace dotazu byste to měli udělat. Navíc pochopení slučovacího řazení nám později pomůže porozumět společné operaci spojení databáze, která se nazývá spojit spojit (sloučení sdružení).

Spojit

Stejně jako mnoho užitečných algoritmů se slučovací třídění spoléhá na trik: zkombinování 2 seřazených polí o velikosti N/2 do N-prvkového setříděného pole stojí pouze N operací. Tato operace se nazývá sloučení.

Podívejme se, co to znamená, na jednoduchém příkladu:

Tento obrázek ukazuje, že k sestavení konečného seřazeného 8prvkového pole stačí iterovat pouze jednou přes 2 4prvková pole. Protože obě 4prvková pole jsou již seřazena:

1) porovnáte oba aktuální prvky ve dvou polích (na začátku aktuální = první)
2) pak vezměte ten nejmenší a vložte jej do pole s 8 prvky
3) a přejděte na další prvek v poli, kde jste vzali nejmenší prvek
a opakujte 1,2,3, dokud nedosáhnete posledního prvku jednoho z polí.
Poté vezmete zbývající prvky druhého pole a vložíte je do pole s 8 prvky.

To funguje, protože obě 4prvková pole jsou setříděna, takže se v těchto polích nemusíte "vracet".

Nyní, když rozumíme triku, zde je můj pseudokód pro sloučení:

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 rozdělí problém na menší problémy a pak najde výsledky menších problémů, aby získal výsledek původního problému (poznámka: tento typ algoritmu se nazývá rozděl a panuj). Pokud tomuto algoritmu nerozumíte, nebojte se; Když jsem to viděl poprvé, nerozuměl jsem tomu. Pokud vám to může pomoci, vidím tento algoritmus jako dvoufázový algoritmus:

Fáze dělení, kdy je pole rozděleno na menší pole
Fáze třídění je tam, kde jsou malá pole kombinována (pomocí sjednocení) k vytvoření většího pole.

Fáze dělení

Ve fázi dělení je pole rozděleno na unitární pole ve 3 krocích. Formální počet kroků je log(N) (protože N=8, log(N) = 3).

Jak to poznám?

Jsem génius! Jedním slovem - matematika. Myšlenka je taková, že každý krok dělí velikost původního pole 2. Počet kroků je počet, kolikrát můžete rozdělit původní pole na dva. Toto je přesná definice logaritmu (základ 2).

Fáze třídění

Ve fázi řazení začínáte s unitárními (jednoprvkovými) poli. Během každého kroku použijete více operací sloučení a celkové náklady jsou N = 8 operací:

V první fázi máte 4 sloučení, z nichž každá stojí 2 operace
Ve druhém kroku máte 2 sloučení, z nichž každé stojí 4 operace
Ve třetím kroku máte 1 sloučení, které stojí 8 operací

Protože existuje log(N) kroků, celkové náklady N * log(N) operace.

Výhody slučovacího řazení

Proč je tento algoritmus tak výkonný?

Protože:

Můžete jej změnit, abyste snížili nároky na paměť, takže nevytváříte nová pole, ale přímo upravujete vstupní pole.

Poznámka: Tento typ algoritmu se nazývá in-místo (třídění bez další paměti).

Můžete jej změnit tak, aby současně využíval místo na disku a malé množství paměti, aniž by došlo k výrazné režii diskových I/O. Cílem je načíst do paměti pouze ty části, které se právě zpracovávají. To je důležité, když potřebujete seřadit multigigabajtovou tabulku pouze s 100megabajtovou vyrovnávací pamětí.

Poznámka: Tento typ algoritmu se nazývá externí řazení.

Můžete jej změnit tak, aby běžel na více procesech/vláknech/serverech.

Jednou z klíčových součástí je například třídění distribuovaného sloučení Hadoop (což je struktura ve velkých datech).

Tento algoritmus dokáže proměnit olovo ve zlato (opravdu!).

Tento třídicí algoritmus se používá ve většině (pokud ne ve všech) databázích, ale není jediný. Pokud se chcete dozvědět více, můžete si přečíst toto výzkumná práce, který pojednává o výhodách a nevýhodách běžných algoritmů třídění databází.

Pole, strom a tabulka hash

Nyní, když rozumíme myšlence časové složitosti a řazení, měl bych vám říci o 3 datových strukturách. To je důležité, protože oni jsou základem moderních databází. Představím také koncept index databáze.

Array

Dvourozměrné pole je nejjednodušší datová struktura. Tabulku si lze představit jako pole. Například:

Toto 2rozměrné pole je tabulka s řádky a sloupci:

Každý řádek představuje entitu
Sloupce ukládají vlastnosti, které popisují entitu.
Každý sloupec ukládá data určitého typu (celé číslo, řetězec, datum...).

To je vhodné pro ukládání a vizualizaci dat, ale když potřebujete najít konkrétní hodnotu, není to vhodné.

Pokud byste například chtěli najít všechny lidi, kteří pracují ve Spojeném království, museli byste se podívat na každý řádek, abyste zjistili, zda tento řádek patří Spojenému království. Bude vás to stát N transakcíKde N - počet řádků, což není špatné, ale mohl by existovat rychlejší způsob? Nyní je čas, abychom se seznámili se stromy.

Poznámka: Většina moderních databází poskytuje rozšířená pole pro efektivní ukládání tabulek: heap-organizedtables a index-organizedtables. To ale nic nemění na problému rychlého nalezení konkrétního stavu ve skupině sloupců.

Databázový strom a index

Binární vyhledávací strom je binární strom se speciální vlastností, klíč v každém uzlu musí být:

větší než všechny klíče uložené v levém podstromu
méně než všechny klíče uložené v pravém podstromu

Podívejme se, co to znamená vizuálně

Nápad

Tento strom má N = 15 prvků. Řekněme, že hledám 208:

Začínám u kořene, jehož klíč je 136. Od 136<208 se dívám na pravý podstrom uzlu 136.
398>208 proto se dívám na levý podstrom uzlu 398
250>208 proto se dívám na levý podstrom uzlu 250
200<208, proto se dívám na pravý podstrom uzlu 200. Ale 200 nemá žádný pravý podstrom, hodnota neexistuje (protože pokud existuje, bude ve správném podstromu 200).

Teď řekněme, že hledám 40

Začnu u kořene, jehož klíč je 136. Od 136 > 40 se podívám na levý podstrom uzlu 136.
80 > 40, proto se dívám na levý podstrom uzlu 80
40 = 40, uzel existuje. Načítám ID řádku uvnitř uzlu (nezobrazeno na obrázku) a hledám v tabulce dané ID řádku.
Znalost ID řádku mi umožňuje přesně vědět, kde jsou data v tabulce, takže je mohu okamžitě získat.

Nakonec mě obě hledání budou stát počet úrovní uvnitř stromu. Pokud si pozorně přečtete část o řazení sloučení, měli byste vidět, že existují úrovně log(N). Ukazuje se, hledat protokol nákladů (N), není špatné!

Vraťme se k našemu problému

Ale to je velmi abstraktní, takže se vraťme k našemu problému. Místo jednoduchého celého čísla si představte řetězec, který představuje zemi někoho z předchozí tabulky. Řekněme, že máte strom, který obsahuje pole „země“ (sloupec 3) tabulky:

Pokud chcete vědět, kdo pracuje ve Velké Británii
podíváte se na strom a získáte uzel, který představuje Velkou Británii
uvnitř "UKnode" najdete umístění záznamů pracovníků ve Spojeném království.

Toto hledání bude stát log(N) operací místo N operací, pokud pole použijete přímo. To, co jste právě představil, bylo index databáze.

Můžete vytvořit indexový strom pro libovolnou skupinu polí (řetězec, číslo, 2 řádky, číslo a řetězec, datum...), pokud máte funkci pro porovnávání klíčů (tj. skupiny polí), abyste mohli nastavit pořadí mezi klíči (což je případ všech základních typů v databázi).

B+TreeIndex

I když tento strom funguje dobře pro získání konkrétní hodnoty, v případě potřeby nastává VELKÝ problém získat více prvků mezi dvěma hodnotami. To bude stát O(N), protože se budete muset podívat na každý uzel ve stromu a zkontrolovat, zda je mezi těmito dvěma hodnotami (např. při uspořádaném procházení stromu). Navíc tato operace není přátelská k diskovým I/O, protože musíte číst celý strom. Musíme najít způsob, jak efektivně realizovat žádost o rozsah. K vyřešení tohoto problému používají moderní databáze upravenou verzi předchozího stromu nazvanou B+Tree. Ve stromu B+Tree:

pouze nejnižší uzly (listy) obchodní informace (umístění řádků v související tabulce)
zbytek uzlů je zde pro směrování do správného uzlu během hledání.

Jak vidíte, uzlů je zde více (dvakrát). Ve skutečnosti máte další uzly, "rozhodovací uzly", které vám pomohou najít správný uzel (který ukládá umístění řádků v související tabulce). Složitost vyhledávání je ale stále O(log(N)) (existuje pouze jedna úroveň navíc). Velký rozdíl je v tom uzly na nižší úrovni jsou připojeny k jejich nástupcům.

S tímto B+Stromem, pokud hledáte hodnoty mezi 40 a 100:

Stačí hledat 40 (nebo nejbližší hodnotu po 40, pokud 40 neexistuje), jako jste to udělali u předchozího stromu.
Poté shromážděte 40 dědiců pomocí přímých dědických odkazů, dokud nedosáhnete 100.

Řekněme, že najdete M následníků a strom má N uzlů. Nalezení konkrétního uzlu stojí log(N) jako předchozí strom. Jakmile však získáte tento uzel, získáte M nástupců v operacích M s odkazy na jejich nástupce. Toto vyhledávání stojí pouze M+log(N) operací ve srovnání s N operacemi na předchozím stromu. Navíc nemusíte číst celý strom (pouze M+log(N) uzly), což znamená menší využití disku. Pokud je M malé (např. 200 řádků) a N velké (1 000 000 řádků), bude VELKÝ rozdíl.

Ale jsou tu nové problémy (opět!). Pokud přidáte nebo odstraníte řádek v databázi (a tedy v přidruženém indexu B+Tree):

musíte udržovat pořadí mezi uzly uvnitř B+stromu, jinak nebudete moci najít uzly uvnitř neseřazeného stromu.
musíte dodržet minimální možný počet úrovní v B+Strom, jinak se z časové složitosti O(log(N)) stane O(N).

Jinými slovy, B+Strom musí být samořadící a vyvážený. Naštěstí je to možné pomocí operací inteligentního mazání a vkládání. To však něco stojí: vkládání a mazání ve stromu B+ stojí O(log(N)). Proto to někteří z vás slyšeli používat příliš mnoho indexů není dobrý nápad. Opravdu, zpomalujete rychlé vkládání/aktualizaci/mazání řádku v tabulceprotože databáze potřebuje aktualizovat indexy tabulky pomocí nákladné operace O(log(N)) pro každý index. Přidání indexů navíc znamená větší pracovní zátěž transakční manažer (bude popsáno na konci článku).

Další podrobnosti naleznete v článku na Wikipedii B+Strom. Pokud chcete příklad implementace B+Stromu v databázi, podívejte se tento článek и tento článek od předního vývojáře MySQL. Oba se zaměřují na to, jak InnoDB (motor MySQL) zpracovává indexy.

Poznámka: Jeden čtenář mi řekl, že kvůli optimalizaci na nízké úrovni by měl být strom B+ zcela vyvážený.

Hashtable

Naší poslední důležitou datovou strukturou je hashovací tabulka. To je velmi užitečné, když chcete rychle vyhledat hodnoty. Porozumění hashovací tabulce nám navíc pomůže později porozumět běžné operaci spojení databáze nazývané hash join ( hash připojit). Tuto datovou strukturu využívá databáze také k ukládání některých interních věcí (např. zamykací stůl nebo buffer pool, oba tyto koncepty uvidíme později).

Hašovací tabulka je datová struktura, která rychle najde prvek podle jeho klíče. Chcete-li sestavit hashovací tabulku, musíte definovat:

ключ pro vaše prvky
hashovací funkce pro klíče. Vypočítané hash klíče dávají umístění prvků (tzv segmenty ).
funkce pro porovnávání klíčů. Jakmile najdete správný segment, musíte pomocí tohoto srovnání najít prvek, který hledáte v segmentu.

Jednoduchý příklad

Vezměme si jasný příklad:

Tato hash tabulka má 10 segmentů. Protože jsem líný, vyfotil jsem jen 5 segmentů, ale vím, že jsi chytrý, tak tě nechám, aby sis zbylých 5 vyfotil sám. Použil jsem hashovací funkci modulo 10 klíče. Jinými slovy, ukládám pouze poslední číslici klíče prvku, abych našel jeho segment:

pokud je poslední číslice 0, prvek spadá do segmentu 0,
pokud je poslední číslice 1, prvek spadá do segmentu 1,
pokud je poslední číslice 2, prvek spadá do oblasti 2,
...

Porovnávací funkce, kterou jsem použil, je prostě rovnost mezi dvěma celými čísly.

Řekněme, že chcete získat prvek 78:

Tabulka hash vypočítá hash kód pro 78, což je 8.
Hashovací tabulka se podívá na segment 8 a první prvek, který najde, je 78.
Vrátí vám položku 78
Hledání stojí pouze 2 operace (jeden pro výpočet hodnoty hash a druhý pro vyhledání prvku v segmentu).

Nyní řekněme, že chcete získat prvek 59:

Tabulka hash vypočítá hash kód pro 59, což je 9.
Hash tabulka hledá v segmentu 9, první nalezený prvek je 99. Protože 99!=59, prvek 99 není platným prvkem.
Pomocí stejné logiky se vezme druhý prvek (9), třetí (79), ..., poslední (29).
Prvek nenalezen.
Hledání stálo 7 operací.

Dobrá hashovací funkce

Jak vidíte, v závislosti na hodnotě, kterou hledáte, cena není stejná!

Pokud nyní změním hashovací funkci modulo 1 000 000 klíče (to znamená, že vezmu posledních 6 číslic), druhé vyhledávání stojí pouze 1 operaci, protože v segmentu 000059 nejsou žádné prvky. Skutečnou výzvou je najít dobrou hashovací funkci, která vytvoří kbelíky obsahující velmi malý počet prvků.

V mém příkladu je nalezení dobré hashovací funkce snadné. Ale toto je jednoduchý příklad, najít dobrou hashovací funkci je obtížnější, když je klíč:

řetězec (například - příjmení)
2 řádky (například - příjmení a jméno)
2 řádky a datum (například - příjmení, jméno a datum narození)
...

S dobrou hashovací funkcí stojí vyhledávání v hashovacích tabulkách O(1).

Pole vs hashovací tabulka

Proč nepoužít pole?

Hmm, dobrá otázka.

Hašovací tabulka může být částečně načteno do pamětia zbývající segmenty mohou zůstat na disku.
S polem musíte použít souvislý prostor v paměti. Pokud načítáte velký stůl je velmi obtížné najít dostatek souvislého prostoru.
U hašovací tabulky můžete vybrat požadovaný klíč (například zemi a příjmení osoby).

Pro více informací si můžete přečíst článek o JávaHashMap, což je efektivní implementace hashovací tabulky; nemusíte rozumět Javě, abyste pochopili koncepty popsané v tomto článku.

Zdroj: www.habr.com

Jak fungují relační databáze (část 1)