IT rekvalifikace s garancí práce. Seniorní programátoři vydělávají až 160 000 Kč/měsíc a rekvalifikace je prvním krokem. Zjisti, jak na to!
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
Avatar
Jiří Hrdina
Člen
Avatar
Jiří Hrdina:13.6.2018 22:48

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

 
Odpovědět
13.6.2018 22:48
Avatar
Patrik Valkovič
Tvůrce
Avatar
Odpovídá na Jiří Hrdina
Patrik Valkovič:13.6.2018 23:33

Index je B (resp B+) strom. To je datová struktura, kterou můžeš uložit do paměti stejně jako třeba spojový seznam. B strom je vlastně jen n-ární strom (speciální případ je třeba binární strom https://www.itnetwork.cz/…ci-strom-bst).
Tabulky se dělí na clastered table a heap table. Heap table jsou v paměti uloženy více méně tak, jak do nich bylo vkládáno (nic speciálního). Clustered table mají nějaký index (tj. primární klíč), podle kterého jsou uloženy na disku (tj. procházení je velmi rychlé). To jsou pouze primární klíče.
Indexy používají B strom (protože data už jsou seřazeny podle primárního klíče a nemůžeš je tedy seřadit jinak), ve kterých lze rychleji vyhledávat. Ty se jako programátor o implementaci vůbec nestaráš, pouze řekneš, že chceš na sloupci INDEX a máš vyřešeno. V SELECTu se poté s indexy automaticky počítá (pokud jsou použity) a vyhledávání bude probíhat podle nich.
Pokud chceš vědět, jak to funguje, tak si první najdi, jak funguje clastered table a poté B stromy.

Nahoru Odpovědět
13.6.2018 23:33
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:14.6.2018 8:35

https://cs.wikipedia.org/…v_%C4%8Cesku

id | mesto | počtem obyvatel
1 | Praha       1 280 508
2 | Brno        377 973
3 | Ostrava     291 634
4 | Plzeň      170 548
5 | Liberec     103 853
6 | Olomouc     100 378
7 | České Budějovice         93 470
8 | Ústí nad Labem    92 984
9 | Hradec Králové    92 929
10 | Pardubice  90 044
11 | Zlín      75 117
12 | Havířov  73 274
13 | Kladno     68 660

Bez indexu, kdyz das hledat slovo Praha, tak projde vsechny radky, vsechny znaky (dokud je shoda s pismenem v hledanem slove). Kdyz mas v tabulce 1.000.000 zaznamu, tak to chvili trva.
Index je pomocna tabulka, ktera vypada treba takto

O - 3, 6
H - 9, 12

Budes hledat Ostrava, prvni pismenko je O, SQL primo skoci na radek 3 a 6.
Pouzil jsem index pro prvni pismenko. Obvykle se pouzivaji 3 znaky. Pak je tam strukturovanejsi tabulka

id_index | index | id_indexy | id_radky
1 | O | 2, 3 | null -- Ostrava, O je v indexech id = 2 a 3
2 | S | null | 3 -- OS (Ostrava)
3 | L | null | 6 - OL (Olomouc)
4 | dalsi kombinace pismen
...

Pismeno je cislo 0-255. 1 pismeno = 256, 2 pismena = 256 * 256 (16 bitu) ..., 10 pismen je 80 bitove cislo.
Ciselny index je napr 32 bitove cislo.
Takze je vyhodnejsi indexovat cisla nez pismena. Mysleno tak, ze se index pro slova pouziva prava 2-3 pismenka. Vic vetsinou nee. Sql vyfiltruje vsechny radky, kde zacina slovo temi 3 pismeny a pak uz se porovnaji vsechny radky. Samozrejme, pokud ti to nevadi, mas dost mista, klidne indexuj cele slova.
Ale, to uz by pak mozna bylo lepsi pouzit full-index, ktery si vytvari slovnik a nejspis vytvari ke slovu jakysi ciselny hash. Cili, tech 10 znaku prevede na 2 znaky. To mu vybere i spoustu radku, co tam nepatri a ty pak odfitruje po pismenkach. Vyhoda full-indexu je, ze by mel byt rovnomerne rozdeleny. Cestina v textu pouziva treba 30.000 slov, 30.000 / 2 / 2 / 2 / 2 ...zhruba dostanes, kolik prvku je v kazde vetvi (14). Porovnat 14 radku je rychlejsi nez kdyz nekdy vrati 1 a jindy 200.

Editováno 14.6.2018 8:36
 
Nahoru Odpovědět
14.6.2018 8:35
Avatar
Jiří Hrdina
Člen
Avatar
Jiří Hrdina:14.6.2018 16:32

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ě?

 
Nahoru Odpovědět
14.6.2018 16:32
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:15.6.2018 11:31

Takhle informaticky do hloubky tomu nerozumim. Jo, slysel jsem, zt ot maji nejak v B-tree, ale nezajimalo mne to presne. Ja si to umim udlat nejak, kdyz budu potrebovat :)
Ale myslim, ze to dela po pismenkach. Prvni pismeno, 1 strom. Kombinace AA dalsi, AB dalsi, ... Treba, tusim, cms docu-wiki si vytvari primo slozky na disku.
V podstate ta pomocna tabulka muze byt organizovana podle slov, mozne kombinace a jen linkujes v nejakem souboru na pozici, odkud zacinaji cisla radku
Tab
AA | 0 | 3 - na pozici 0, zkopiruj 3 cisla
AB | -1 | -1 - zadne slovo nezacina 'AB'
AC | 3 | 1 - na pozici 3, zkopiruj 1 cislo
Datovy soubor
23 | 52 | 3 | ... - jen seznam cisel radku

Nezda se mi, ze by pouzili slova, protoze to mohli pouzit . To mozna u full-text vyhledavani. Tam si myslim, ze to funguje tak, ze vytahne z textu slova, seradi a pak si ulozi jen cislo radku/sloupce s 'clankem' a pocet vyskytu, pripadne slovnik. Ktery je ale spolecny pro nekolik 'clanku'. Pri vyhledavani pak najde slovo ve slovniku, jeho id_slovo a podiva se do tabulky id_slovo, id_radku, pocet. V cestine je zhruba se sklonovanim kolem 30.000 slov, coz neni takova hruza.

Editováno 15.6.2018 11:32
 
Nahoru Odpovědět
15.6.2018 11:31
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 5 zpráv z 5.