Vysvětlete mi indexování v databázi

Droan

Vysvětlete mi indexování v databázi
« kdy: 13. 06. 2018, 23:07:56 »
Ahoj,

snažím se pochopit, jak funguje indexování a mám v tom dost chaos.

Co jsem četl za články, tak jsem to pochopil stručně nějak takto:

Když nemám index, tak pokud zadám dotaz, tak se musí projet všechna data po jednom, pokud mám index, tak systém ví, kam má přesně jít a nemusí procházet všechna data. Index je datová struktura uložená v paměti a používá B+ stromy.

Nicméně... Jak je ten index uložený v paměti? Nedovedu si to prostě představit... to se vytvoří nová tabulka? Jak ta tabulka bude vypadat? Jak probíhá to "propojení"? Jak si zvolím ty hodnoty indexové? Když budu mít index na id nějakých zaměstnanců, tak z těch id se vytvoří ten b+ strom? Když budu chtít index na příjmení zaměstnanců a třeba budu hledat "Novák" - tak jak to bude konkrétně vypadat? To se projede ten index a index odkazuje na ty data přímo a projde se mnohem méně těch datových položek?

Mohl bych poprosit o osvětlení těhle věcí? Případně nějaké odkazy, kde je to hezky vysvětlené a s obrázky, z kterých se to lépe chápe?

Mockrát děkuji
« Poslední změna: 13. 06. 2018, 23:55:01 od Petr Krčmář »


Gődel

Re:Indexování - DB
« Odpověď #1 kdy: 13. 06. 2018, 23:28:12 »
Ano, index je typicky nějaký strom. Pro pole příjmení budou vrcholy reprezentovat jednotlivá příjmení. Každý vrchol pak obsahuje odkazy na příslušné záznamy, kde se vyskytuje v daném poli. Při hledání se strom prochází, na rozdíl od hledání bez použití indexu ovšem ne sekvenčně (tj. lineárně), ale rychleji (protože jde typicky o nějaký typ vyváženého stromu, kde je hloubka omezena logaritmicky). Wikipedie (aspoň ta anglická) to rozvádí velice názorně a podrobně.

Kit

Re:Indexování - DB
« Odpověď #2 kdy: 13. 06. 2018, 23:55:04 »
Indexy obvykle nebývají v paměti, ale opět někde na disku. Bývají v blocích o velikosti alokační jednotky, aby práce s nimi byla rychlá. Obsahují klíč a adresu do souboru s daty, kde se indexovaný záznam nachází. Pokud podmínce vyhovuje víc než asi čtvrtina záznamů, tak bývá výhodnější ignorovat index a projít si všechny záznamy sekvenčně. Rovněž nemá moc velký význam dělat index pro méně než 1000 záznamů.

Existují i databázové systémy, které mají indexy výhradně v operační paměti. Tyto databáze sice trochu déle startují, ale pak běží velice rychle.

xxxxx

Re:Indexování - DB
« Odpověď #3 kdy: 14. 06. 2018, 00:00:41 »
Velmi zjednodušeně, ale možná může pomoci:

Indexy nemusí být nutně v paměti, je to prostě další součást DB (vytvářená automaticky). Obvykle i ukládané spolu s DB. V paměti obvykle bývají, kvůli urychlení, ale to mohou být i vlastní položky.

Zapomeň na B+ tree a další specialitky, pro základní představu, nejjednodušší příklad, mysli, že index je opravdu jen další tabulka odkazů (tím "odkazem" si představ pořadí v základní tabulce). Index jsou tedy jen odkazy (pořadí, propojení), nic jiného. Akorát že seřazené.

Takže máš třeba DB čtyř jmen: Ondra, Jirka, Petr, Michal
Když si necháš oindexovat (dle jména), tak index bude vypadat třeba 2., 4., 1., 3. (tedy, seřazeně je jako první odkaz na 2. položku Jirka, pak Michal, Ondra, Petr).

- Výhody, když hledáš jméno, stačí půlením intervalu (přes ten index) dohledat seřazené, jinak bys musel projíždět položky jednu za druhou, než najdeš. Pro B tree index se pak projíždí ten strom.

- Nevýhody, když přidáš další jméno, musí se upravit i index (takže přidávání ubírání položek trvá déle než bez indexu). Příklad, přidáš "Karel" ... bude to vypadat Ondra, Jirka, Petr, Michal, Karel ... ale upravený index bude: index 2., 5., 4., 1., 3.

Indexů může být více (jméno, příjmení, ...), ale každé přidání a ubrání vždy znamená znovu opravit _všechny_ indexy. Ale vyhledávání je pak rychlé. Proto se jako index užívají různě B stromy a spol., aby se i pohyby (odebírání, přidávání) v rámci indexu prováděly rychle - není to jen prostá lineární tabulka pořadí (tam by se muselo celé posouvat, při přidání doprostřed).

V praxi v současných databázích to vypadá jen tak, že řekneš, že třeba pole "jméno" chceš indexovat a databáze už si vše dělá sama - jak upravuje index při přidávání/mazání, tak, pokud hledáš dle jména, tak využije index a vyhledá rychle. Stejně tak se nestaráš o to, jak to "propojení" vypadá ani jak vypadá zdrojová tabulka jmen - zda je index jen  prosté pořadí, či něco více. Ona totiž ani ta původní tabulka jmen neznamená, že jsou někde za sebou, může to být list, cokoli. O to se nestaráš, to zvenku nevíš.

Prostě, Ty už se pak nestaráš o to, že nějaký index musíš upravovat, ani jaká je fyzická podoba zdrojové "tabulky". To už je starost DB. Ty se jen ptáš (SQL).

uuuuu

Re:Vysvětlete mi indexování v databázi
« Odpověď #4 kdy: 14. 06. 2018, 04:03:55 »
doporucuju si precist hledani v binarnim stromu.
https://en.wikipedia.org/wiki/Binary_search_tree

treba mas tabulku s cislama (jake jsou vyplaty), kdyz to mas ve vektoru, tak musis prochazet
cely vektor, abys nasel zaznamy s cislem vetsim X.
kdyz k tomu mas index jako binarni strom, tak staci najit odpovidajici vetev stromu a mas
vsechny zaznamy co potrebujes.


Re:Vysvětlete mi indexování v databázi
« Odpověď #5 kdy: 14. 06. 2018, 09:47:08 »
Když nemám index, tak pokud zadám dotaz, tak se musí projet všechna data po jednom, pokud mám index, tak systém ví, kam má přesně jít a nemusí procházet všechna data. Index je datová struktura uložená v paměti a používá B+ stromy.

Zaklínadlo je právě B-tree. SELECT potom nemusí procházet (porovnávat) N záznamů, ale stačí mu log2(N) porovnání. Což znamená rozdíl 1000 vs. 10 nebo 1 000 000 vs 20. Ona údržba toho indexu taky něco stojí, ale odehrává se při vkládání záznamů (a i tak vložení záznamu opět NEznamená projít celou tabulku). Takže index má smysl pro velký počet záznamů a zejména pro tabulky (sloupce?) kde se často hledá (čte) a málo vkládá (zapisuje). Nebo nad sloupci, na které se provádí join mezi tabulkami!

B-tree má jeden obecný vtipný aspekt, přítomný v různých implementacích - pokud zkusíte používat nějaké B-tree knihovny v jazyce nízké úrovně, třeba v Cčku: samotná stromová struktura nijak těsně nezávisí na datovém typu, který stromem třídíte. Tzn. kostra stromu je prakticky stejná, ať se jedná o integer, nebo třeba o řetězec znaků o proměnlivé délce. (Nebo o Váš vlastní bizardní objekt se svéráznou sémantikou porovnávání.) Finta je v tom, že B-tree knihovně při vytvoření stromu předáte odkaz na "porovnávací funkci". V zásadě se jedná o funkci "je větší než", která bere dva argumenty "konkrétního cílového" datového typu. A pak už do stromu jenom sypete položky (resp. v našem případě odkazy na záznamy v DB) a on si porovnávací funkci úkoluje po svém. Vám při vyhledávání vypadnou hotové výsledky. Zdejší věrozvěsti funkcionálního programování zajisté pobaveně kroutí hlavou jak přednáším o vynálezu kola.

Nicméně... Jak je ten index uložený v paměti? Nedovedu si to prostě představit... to se vytvoří nová tabulka? Jak ta tabulka bude vypadat? Jak probíhá to "propojení"? Jak si zvolím ty hodnoty indexové? Když budu mít index na id nějakých zaměstnanců, tak z těch id se vytvoří ten b+ strom? Když budu chtít index na příjmení zaměstnanců a třeba budu hledat "Novák" - tak jak to bude konkrétně vypadat? To se projede ten index a index odkazuje na ty data přímo a projde se mnohem méně těch datových položek?

Jak je index uložený v paměti. Jak je binární strom uložený v paměti. Zkoušel jste programovat v Cčku, Pascalu, Perlu, nebo nějakém jiném jazyku, kde lze dynamicky alokovat "kompozitní" datové typy jako struct/record a odkazovat se na ně pointery/referencemi apod.? Většinou je tahle látka vyučována cca v pořadí pointer, struct, linked list, strom. Plus na to navazuje téma o "alokátorech" paměti = jak se z té "společné hromady" parcelují kousky RAMky pro jednotlivé structy = uzly stromu, tzn. co se skrývá za funkcemi jako malloc()/free(). To se pořád bavíme o RAMce / heapu. On se ale index nemusí do RAMky celý vejít, nebo není potřeba aby místo v RAMce trvale zabíral. A rozhodně potřebuje mít zajištěnu "perzistenci". Takže ano, ukládá se i na disk. Vlastně se dá i přímo na disku procházet, aniž by se celý do RAMky natáhl. Opět platí výše zmíněné "poměry akcelerace" - jenom už se nebavíme o porovnávacích operacích co operují čistě v RAMce, ale latence každého kroku bude určena latencí seeku na disk. (Nebo něco mezi, protože několik uzlů B-stromu bude na disku pohromadě v jedné alokační jednotce.) Navazuje problematika alokace místa na discích - a nebudu odkazovat striktně na souborové systémy, protože mnohé databáze rády fungují přímo na diskový oddíl (blokové zařízení) a spravují si alokaci "po svém". To je myslím už poměrně dost buzzwordů do googlu, co říkáte :-) Samozřejmě je index s tabulkou provázaný odkazy, jak v RAMce, tak na disku. Skutečné interní algoritmy indexování, alokování souvisejících datových struktur v RAMce a na disku, to je "sladké tajemství" každého DB enginu. U komerčních DB se jedná o obchodní tajemství / klíčové intelektuální vlastnictví, u open-source DBMS Vám nic nebrání ponořit se do zdrojáků a číst. V souvislosti s indexováním se zkuste mrknout vedle b-trees také na "hash" algoritmy, které k problému přistupují trochu jinak a mohou urychlit prohledávání indexu jiným způsobem.

Pro Vás jako uživatele RDBMS  = programátora aplikace a SQL dotazů je důležité, že tohle všechno se děje "pod kapotou", kam v zájmu svého duševního zdraví nechcete moc nahlížet. Od toho Vám pánbůh seslal DB engine, aby se postaral o Vaše pohodlí. Takže na úrovni SQL není index sám o sobě moc vidět. Vy ho vytvoříte příkazem cca CREATE INDEX ON TABLE, čili vznikne tam jakýsi objekt ve "jmenném prostoru věcí co jste si v databázi vytvořil", ale je pevně přivázaný ke konkrétní tabulce, a při SELECT/INSERT/UPDATE/DELETE se každopádně bavíte pomocí SQL příkazů explicitně s _tabulkou_, nikoli s indexem. Čili Index je v tomto smyslu občanem nižší kategorie než třeba "view". Nebo jinak, Index je za provozu spíš jenom takový "astrální duch v pozadí", který na Vaši tabulku potichu dohlíží. Existuje také explicitní "DROP INDEX", v různých dialektech SQL buď samostatný, nebo v rámci "ALTER TABLE".

A ještě jedna poznámka: snad všechny DBMS vytvoří impliticní index, pokud zmíníte klauzulku PRIMARY KEY v rámci SQL příkazu CREATE TABLE. Prostě primární klíč bývá implicitně indexovaný, aniž byste si o index musel ještě nějak extra říct pomocí CREATE INDEX. Stačí že si řeknete o PRIMARY KEY.

uuuuu

Re:Vysvětlete mi indexování v databázi
« Odpověď #6 kdy: 14. 06. 2018, 11:19:53 »
"Ona údržba toho indexu taky něco stojí, ale odehrává se při vkládání záznamů (a i tak vložení záznamu opět NEznamená projít celou tabulku)."

nebo-li vyvazovani stromu.

Kit

Re:Vysvětlete mi indexování v databázi
« Odpověď #7 kdy: 14. 06. 2018, 12:07:16 »
Složitost log2(N) by byla jen u vyváženého binárního stromu. B+ strom však používá větší node. Obvykle tak, aby odpovídal velikosti alokační jednotky na disku. V tomto node se už většinou vyhledává sekvenčně. Tento postup snižuje počet přístupů na disk, což je u databází žádoucí.

Onestone

Re:Vysvětlete mi indexování v databázi
« Odpověď #8 kdy: 14. 06. 2018, 13:19:47 »
Složitost log2(N) by byla jen u vyváženého binárního stromu. B+ strom však používá větší node. Obvykle tak, aby odpovídal velikosti alokační jednotky na disku. V tomto node se už většinou vyhledává sekvenčně. Tento postup snižuje počet přístupů na disk, což je u databází žádoucí.
Sekvenčně, ale v konstantním čase.

gnat

Re:Vysvětlete mi indexování v databázi
« Odpověď #9 kdy: 14. 06. 2018, 13:52:21 »
Ono ani tak nejde o rychlost prohledání toho stromu, ale o to, že se šetří ta nejdražší operace - nalezení a nahrání bloku z disku. Pokud mám tabulku o více sloupcích, která je v dejme tomu 20 blocích, tak pro nalezení zaznamů podle hodnoty nějakého  sloupce musím nacist všech 20 bloku i když vracím jen jeden zaznam. Pokud použijí index, tak je velmi pravděpodobné, že se celý vejde do 1 bloku a tudíž nacitam jen blok s indexem a blok s hledaným záznamem.

Kit

Re:Vysvětlete mi indexování v databázi
« Odpověď #10 kdy: 14. 06. 2018, 15:00:44 »
Indexy navíc obvykle bývají v cache, což přináší další zrychlení.

Droan

Re:Vysvětlete mi indexování v databázi
« Odpověď #11 kdy: 14. 06. 2018, 16:44:28 »
Děkuji :), tak ještě shrnutí, jestli jsem to pochopil správně...

Nastavím si, že chci třeba indexovat seznam podle jména...

id | jmeno | telefon
1 | Petr | 123
2 | Jan | 222
3 | Dan | 333
4 | Jiri | 444
Takže se mi vytvoří struktura B strom v paměti s hodnotami - Petr, Jan, Dan, Jiri a díky složitosti log2n vyhledávání se mi rychleji najdou ty indexy, které dále ukazují na data v tabulce. Takže třeba když budu hledat Dan - tak index Dan bude ukazovat na ten řádek (s id=3) v tabulce. Pokud by bylo více Danů v tabulce, tak bude ukazovat na všechny Dany. Chápu to tak správně?

Re:Vysvětlete mi indexování v databázi
« Odpověď #12 kdy: 14. 06. 2018, 20:26:51 »
Takže třeba když budu hledat Dan - tak index Dan bude ukazovat na ten řádek (s id=3) v tabulce.
Ano. Terminologická poznámka: index je celý ten strom zkonstruovaný nad sloupcem "jméno". Položka "Dan" je jenom jeden záznam v indexu, koncový "list" stromu. A ano, záznam v indexu obsahuje nějaký low-level odkaz na záznam v "hostitelské" tabulce. (Tedy pokud se jedná o index unikátní. Jak jste sám správně poznamenal.)

Pokud by bylo více Danů v tabulce, tak bude ukazovat na všechny Dany.
Tak. V tom případě se nejedná o index unikátní. I tak má příznivý vliv na rychlost selectů apod., které nad pojednaným sloupcem budete provádět.

Mimochodem index se dá definovat i nad více sloupci - tzn. můžete si třeba oindexovat "složený klíč", třeba jméno+příjmení. Kombinací více sloupců dosáhnete unikátnosti záznamů v indexu (nebo téměř).

Re:Vysvětlete mi indexování v databázi
« Odpověď #13 kdy: 14. 06. 2018, 22:15:28 »
Tak. V tom případě se nejedná o index unikátní. I tak má příznivý vliv na rychlost selectů apod., které nad pojednaným sloupcem budete provádět.
Ono je to opačně – index se vytváří kvůli rychlému vyhledání určitého záznamu v tabulce, a když je potřeba zajistit unikátnost nějaké hodnoty, vytvoří se nad daným sloupcem index, protože vyhledávat danou hodnotu bude nutné při každém insertu a updatu.

složitosti log2n vyhledávání se mi rychleji najdou ty indexy, které dále ukazují na data v tabulce
Jsou různé druhy indexů, mají různou složitost pro vyhledávání i pro zápis, dokonce i různou složitost pro různé charakteristiky dat. Index je prostě struktura, která umožňuje rychlejší nalezení záznamů odpovídajících daným podmínkám. Index je česky rejstřík – a databázový rejstřík má úplně stejnou funkci, jako rejstřík v knize. Některá slova, o kterých se předpokládá, že je budete v knize hledat, máte vypsaná v rejstříku, spolu s odkazem na stránku v knize, kde se to slovo nalézá. A slova v rejstříku jsou seřazená abecedně, takže v tom seznamu požadované slovo rychle najdete. To, co je v knize napsané, se z rejstříku nedozvíte – jsou tam vypsaná jen některá slova, a navíc v abecedním pořadí, ne v pořadí, v jakém jsou ve větách, aby věty dávaly smysl. Když ale potřebujete najít, kde se nachází konkrétní slovo, najdete ho v rejstříku mnohem rychleji, než kdybyste četl knihu od začátku do konce. A k jedné knize můžete mít rejstříků několik – třeba jmenný rejstřík, rejstřík míst, věcný rejstřík.

Rozdíl knižního a databázového rejstříku je v tom, že kniha se nemění, tudíž ani rejstřík se nemění, takže je řazený abecedně, protože v tom se lidem snadno hledá. Databázový rejstřík počítá s tím, že se data mění, takže se musí měnit i rejstřík. kdybyste chtěl do abecedního rejstříku vložit nové slovo, musíte najít řádek, kam patří, a celý zbytek rejstříku od toho místa až do konce byste musel smazat a napsat znova, o řádek níž. Proto se v databázích používají jinak uspořádané rejstříky, ve kterých se docela snadno hledá, ale ani přidání nebo mazání není tak složitá operace. Třeba ty stromové indexy (např. různé varianty B-tree) fungují tak, že nezačínáte od kraje, ale zhruba uprostřed – takže by rejstřík začínal třeba „pokud slovo začíná od A–M, pokračujte na stránce 79, pokud začíná N–Ž, pokračujte na stránce 93“. Pokud budete hledat třeba slovo „KLÍČ“, budete pokračovat na stránce 79, a tam bude „pokud slovo začíná na A–G, pokračujte na stránce 85, pokud na H–M, pokračujte na 82“. A tak dále. Hledání v takovém stromu je pro počítač o něco obtížnější, než hledání v setříděném seznamu, ale úprava takového rejstříku je podstatně snazší – třeba při vkládání stačí přepsat nanejvýš jeden list, což je mnohem lepší, než kdybyste musel průměrně přepisovat půlku abecedního rejstříku.

Re:Vysvětlete mi indexování v databázi
« Odpověď #14 kdy: 15. 06. 2018, 10:32:03 »
Pokud by bylo více Danů v tabulce, tak bude ukazovat na všechny Dany.
Tak. V tom případě se nejedná o index unikátní. I tak má příznivý vliv na rychlost selectů apod., které nad pojednaným sloupcem budete provádět.
Ono je to opačně – index se vytváří kvůli rychlému vyhledání určitého záznamu v tabulce, a když je potřeba zajistit unikátnost nějaké hodnoty, vytvoří se nad daným sloupcem index, protože vyhledávat danou hodnotu bude nutné při každém insertu a updatu.

Já bych řekl, že naše tvrzení nejsou ve sporu :-)

Index v SQL lze vytvořit i bez požadavku na unikátnost. Proto souhlasím s tazatelem, že pak záznam v takovém indexu (např. btree koncový list) odkazuje na množinu/kolekci záznamů v "hostitelské" tabulce. A příznivě se projeví na rychlosti selectů / joinů apod. nad takto indexovaným sloupcem = neunikátní index je lepší než žádný index. A že není unikátní, to vyplývá z reality = z dat, která ten sloupec uchovává.

Teď mluvím na abstraktní úrovni - jak to vidí "uživatel DBMS" = SQL programátor. Jak je to implementováno pod kapotou by určitě vydalo na zajímavou další debatu. Sám občas v c++ takové "hybridní grafy" vytvářím, a to se pohybuju obvykle jenom na heapu, o perzistenci se nesnažím.