Využití databázových indexů

K čemu indexy slouží

Databázové indexy slouží ke zrychlení přístupu k datům a měly by se používat u všech sloupců, podle kterých se vyhledává, třídí nebo podle kterých se spojují tabulky.

Při ukládání dat do tabulek nejsou záznamy obvykle nijak tříděny a ukládají se většinou za sebe tak, jak byly postupně vloženy. V momentě, kdy chceme data z tabulky později vybrat podle nějakého kritéria, je nutné projít všechny záznamy a vybrat z nich ty, které kritériu vyhovují. K tomu, aby při výběru několika záznamů nebylo potřeba procházet všechny ostatní, slouží právě indexy, ve kterých jsou data organizována tak, aby bylo možné rychle vybrat pouze relevantní záznamy.

Indexy se vytvářejí nad jedním nebo několika sloupci tabulky, každá tabulka může mít indexů několik. Index definovaný nad sloupcem tabulky umožňuje rychlý přístup k záznamům podle hodnot tohoto sloupce.

Organizace dat v indexu umožňuje nejen přímé vybrání záznamů s určitou hodnotou, ale samozřejmě také záznamů v intervalu hodnot. Kromě toho jsou prvky v indexu provázané podle svého pořadí při řazení (ať už se jedná o číselné, nebo řetězcové sloupce), takže indexy umožňují také rychlé seřazení tabulky podle sloupců, nad kterými je index definován. Tím pádem umožňují i rychlé vybrání minima a maxima. Informaci o počtu hodnot a počtu různých hodnot (SQL funkce COUNT a COUNT DISTINCT) databáze obvykle uchovávají nezávisle na indexu ve statistikách tabulky, které používají například také při hledání strategie pro vyhodnocování složitějších dotazů.

Indexy nad řetězcovými sloupci umožňují také rychlejší vyhledávání pomocí operátoru LIKE, avšak pouze v případě, kdy je znám začátek hledaného výrazu – tedy např. X LIKE 'text%' využití indexu dovoluje, X LIKE '%text%'  ne.

Použití indexů se často zanedbává a faktem je, že u malých tabulek obsahujících řádově desítky záznamů je jejich význam zanedbatelný. U větších tabulek indexy naopak výkon ovlivňují zásadně. Vzhledem k tomu, že správa indexu stojí určitou režii při každém vkládání záznamu nebo jeho mazání, měli bychom se vytváření indexů vyhnout u tabulek, do kterých se převážně vkládá a jen výjimečně se z nich čte, což jsou např. logy.

Kromě běžných indexů lze definovat také unikátní indexy, které do tabulky nedovolí vložit více záznamů se stejnou hodnotou sloupců, nad kterými je index definován (výjimku tvoří hodnoty NULL). Tato informace může databázovému serveru sloužit také k efektivnějšímu uspořádání dat. Speciálním typem indexu je primární klíč označující sloupce, které jednoznačně identifikují libovolný záznam v tabulce. Definování primárního klíče by mělo být samozřejmostí.

Po vytvoření indexů se o ně již dále nemusíme starat, databázový server sám zajišťuje jejich automatickou aktualizaci a sám rozhoduje o tom, jaké indexy využije při získávání dat. Pokud nás zajímá, jaké indexy server použije, můžeme v MySQL i u několika dalších serverů použít příkaz  EXPLAIN.

Příkazy pro práci s indexem

K vytvoření indexu slouží v MySQL příkaz:

CREATE [UNIQUE] INDEX název ON tabulka (sloupec, ...)

Index se dá vytvořit také přímo při vytváření tabulky:

CREATE TABLE tabulka (..., {INDEX|UNIQUE|PRIMARY KEY} [název] (sloupec, ...), ...)

Odstranění indexu zajišťuje DROP INDEX název ON tabulka, s indexy se dá pracovat i pomocí příkazu  ALTER TABLE.

Název indexu nehraje velkou roli a využijeme ho v podstatě jenom při případném odstraňování indexu. Jestliže název neuvedeme, vytvoří se automaticky. U jiných databází slouží pro práci s indexy obdobné příkazy.

Server MySQL dovoluje také definici indexu pouze nad začátkem řetězce, což šetří místo nezbytné pro uložení indexu a používá se v případě, kdy se data v dlouhém řetězcovém sloupci obvykle liší již svým začátkem. Místo sloupec stačí v definici indexu napsat sloupec(X), kde X je délka začátku řetězce, který chceme při vytváření indexu použít.

Indexy nad více sloupci

Jestliže při získávání dat provádíme hledání, třídění nebo kombinaci obojího nad více sloupci, je vhodné definovat index nad více sloupci. Je dobré si uvědomit, že definování indexu nad více sloupci je něco jiného než definování více indexů nad jedním sloupcem. Jestliže totiž máme např. podmínku X=3 AND Y=4 a indexy (X) a (Y), může se pro nalezení relevantních řádků použít jen jeden index (obvykle ten, který množinu řádků více zredukuje) a řádky vyhovující druhé části podmínky se musí dohledat záznam po záznamu. Jestliže je však definován index (X, Y), může se použít pro přímé nalezení všech relevantních záznamů.

Z indexů nad více sloupci může databázový server při čtení dat využít také libovolný začátek, nemůže však využít libovolnou podmnožinu. Index (X, Y) tak může použít při vyhledávání podle sloupce X, nikoliv však podle sloupce Y. Data pro sloupec Y jsou totiž organizována až v závislosti na hodnotách ve sloupci  X.

Implementace indexů databázemi

Indexy se obvykle implementují pomocí B-stromu, což je datová struktura, která umožňuje vkládání, mazání a vyhledávání prvků s amortizovanou časovou složitostí O(log N), kde N je počet prvků ve stromě. Každý vrchol stromu obsahuje nejméně t-1 a nejvíce 2t-1 prvků, kde t je faktor stromu, pro kořen stromu za určitých okolností stačí, aby byla splněna pouze druhá podmínka. Prvky jsou ve vrcholu uspořádané a z každého vrcholu veden(x)+1 uka­zatelů na jeho syny, kde n(x) je počet prvků vrcholu x. Každý ukazatel vlevo ukazuje pouze na vrcholy s prvky menšími než je daný prvek, ukazatel vpravo naopak na vrcholy s většími prvky. Rychlost operace vyhledání zaručuje to, že všechny cesty z kořene do listů musí mít stejnou délku a že počet prvků v každém vrcholu je z obou stran omezen. Kromě rychlosti operací mají B-stromy proti některým jiným datovým strukturám také tu výhodu, že při všech operacích potřebují málo přístupů na médium, na kterém jsou uloženy (což obvykle není paměť, ale disk).

O B-stromech se lze více dozvědět např. na adrese www.bluerwhite­.org/btree/. V databázích se pro indexy používá kromě B-stromů např. také hašování, ale pouze u některých databázích a jen v některých případech.

Příklad

Vytvoříme jednoduchou aplikaci, ve které budou moci registrovaní uživatelé vkládat příspěvky do různých diskusních skupin. Uživatelé se budou přihlašovat pomocí loginu, diskusní skupiny budeme vypisovat seřazené podle názvu a příspěvky v nich potom podle datumu vložení. Na samostatné stránce potom budeme vypisovat několik nejnovějších příspěvků nezávisle na skupině. Tabulky se správně vytvořenými indexy by v MySQL mohly vypadat takto:

CREATE TABLE uzivatele (
   id int NOT NULL AUTO_INCREMENT,
   login varchar(32) NOT NULL,
   jmeno varchar(100) NOT NULL,
   UNIQUE (login),
   PRIMARY KEY (id)
);

CREATE TABLE skupiny (
   id int NOT NULL AUTO_INCREMENT,
   nazev varchar(100) NOT NULL,
   INDEX (nazev),
   PRIMARY KEY (id)
);

CREATE TABLE prispevky (
   id int NOT NULL AUTO_INCREMENT,
   skupina int NOT NULL REFERENCES skupiny(id),
   uzivatel int NOT NULL REFERENCES uzivatele(id),
   nadpis varchar(100) NOT NULL,
   vytvoreno datetime NOT NULL,
   prispevek text NOT NULL,
   INDEX (skupina, vytvoreno),
   INDEX (vytvoreno),
   PRIMARY KEY (id)
);


Všechny tabulky mají automaticky generovaný primární klíč. V tabulce uzivatele by jako primární klíč mohl sloužit také sloupec login, pro umožnění jeho snadné změny je však vhodnější definovat umělý primární klíč a nad sloupcem login vytvořit unikátní index. V tabulce prispevky je definován jednak index nad sloupcem vytvoreno, který se využije při vypisování několika nejnovějších příspěvků nezávisle na skupině. Pro výpis ve skupinách se potom využije index (skupina, vytvoreno)  – např. v dotazu:

SELECT prispevky.*, uzivatele.jmeno
FROM prispevky
LEFT JOIN uzivatele ON prispevky.uzivatel = uzivatele.id
WHERE skupina = @skupina
ORDER BY vytvoreno DESC


Pokud bychom uživateli chtěli umožnit výpis všech jeho příspěvků řazený podle datumu, bylo by vhodné vytvořit ještě index (uzivatel, vytvoreno), jinak však sloupec uzivatel není v indexech potřeba – v našem dotazu je v okamžiku spojování tabulek jeho hodnota již známa.

Závěr

U aplikací, které pracují pouze s tabulkami obsahujícími několik desítek řádků, není použití indexů životně nezbytné. I u takovýchto tabulek je ale dobrým zvykem vytvářet indexy současně s datovou strukturou a soustředit se tak nejen na to, jaká data budou v databázi uložena, ale také na to, jak se s těmito daty bude pracovat. U tabulek s větším počtem řádků je správná práce s indexy pro rychlost aplikace často rozhodující.