Vyhledávání v relacích

Databáze tvoříme především proto, abychom v uložených datech mohli rychle a efektivně hledat. K tomu v zásadě slouží tři různé přístupy:

• vyhledávání pomocí dat uložených v primárním klíči (velmi rychlé, provádí se totiž scan pouze v datech primárního klíče, tj. není potřeba načítat všechna data z relace)
• vyhledávání pomocí dat uložený v jiném indexu (opět rychlé, provádí se scan pouze v datech daného indexu, tj. není potřeba načítat všechna data z relace)
• vyhledávání pomocí dat uložených mimo indexy (velmi pomalé, je potřeba načíst všechna data z tabulky a provádí se tzv. full table search)

Indexy máme v podstatě následujících typů:

• primární klíč = jeden nebo více atributů, které jednoznačně identifikují každý záznam v relaci (SŘBD vlastně vytvoří ještě jednu pomocnou tabulku, kde budou pouze hodnoty primárních klíčů a odkazy na konkrétní záznamy v relaci, to jí umožní velmi rychlé vyhledávání)
• cizí klíč = atribut jednoznačně odkazující na primární klíč v jiné relaci (SŘBD k němu přistupuje jako k dalšímu indexu)
• další index = atribut, který slouží ke zrychlení vyhledávání (SŘBD si pro každý takovýto index vytvoří pomocnou tabulku, kde budou pouze hodnoty daného indexu a odkazy na konkrétní záznamy v relaci)
  • unikátní index (v rámci jedné relace je možné uložit unikátní hodnotu pouze jednou)
  • neunikátní index (v rámci jedné relace je možné uložit stejnou hodnotu opakovaně)

Při definici nové relace je tedy nutné zvážit, podle jakých atributů budeme v relaci vyhledávat a podle toho nastavit indexy. Nezapomeňte na výhody a nevýhody:

• přidání indexu zrychlí vyhledávání, ale zpomalí přidávání a změnu dat (je potřeba data přidat nebo upravit kromě samotné relace i v technických tabulkách s indexy)
• méně indexů může sice vyhledávání zpomalit, ale zato je rychlejší přidávání a změna dat

Klasické něco za něco. Proto v relacích, kam spíš ukládáme, než z nich čteme, počet indexů omezujeme. Z relací, ze kterých hodně čteme, nastavujeme indexy u atributů, které k vyhledávání používáme nejčastěji.

Vyhledávání v poli

Představme si tedy, že SŘBD vytvořil pro index ještě jednu relaci, která obsahuje pouze data indexu a odkazy na konkrétní záznamy v relaci:

Ve skutečnosti se tedy budeme zabývat algoritmy, které můžeme využít pro vyhledávání v poli. Budeme totiž simulovat vyhledávání nikoliv v matici (v celé relaci), ale pouze vyhledávání v poli (hodnot indexu, zde #ID).

Základní algoritmy pro vyhledávání v poli jsou:

• sekvenční vyhledávání (sequential search)
• metoda binárního půlení (binary search)
• metoda binárního vyhledávacího stromu (binary search tree) s jeho dalšími variantami
• vyhledávání za použití hashovací funkce (hash index)

Pojďme si tedy o každém z algoritmů něco povědět a vyzkoušet si jeho způsob fungování a efektivitu.

Sekvenční vyhledávání

Prochází se pole prvek po prvku (od začátku do konce).

Složitost algoritmu je O(N). V databázi se tomu říká full table search (nebo full table scan).

Nastává v případech, kdy:

• na atributu, který pro vyhledávání používáme, není nastavený index
• je relace tak malá, že je rychlejší ji projít celou, než se zdržovat s indexem
• když je dotaz složitější a vyžaduje většinu dat

Příklad: vezměme si pole {17, 5, 9, 12, 10, 7, 1, 19, 21}. Hledáme-li prvek 7, pomocí metody sekvenčního vyhledávání jej najdeme na šestý pokus.

Metoda binárního půlení

Představme si, že máme seřazené pole – proč tedy hledat od začátku, když mnohem rychlejší musí být se nejprve podívat doprostřed a říct, jestli vyhledávané číslo je menší nebo větší než číslo nacházející se uprostřed. Jestliže jsem číslo nenašel, zmenším interval a proces opakuji.

Složitost algoritmu je O(log₂N). V databázi se využívá jako základ vyhledávání pro stromy.

Příklad: vezměme si pole {1, 5, 7, 9, 10, 12, 17, 18, 19, 21, 23}. Hledáme-li prvek 21, pomocí metody binárního půlení postupujeme následovně:

1. nejprve se podíváme na prostřední prvek (pole má 11 prvků, tj. na 5. prvek) = 12
   naše hledané číslo 21 > 12, čili dále pokračujeme vpravo
2. nové pole, kde hledáme, je tedy {17, 18, 19, 21, 23}
   podíváme se tedy opět na prostřední prvek (pole má 5 prvků, tj. na 2. prvek) = 19
   naše hledané číslo 21 > 19, čili dále pokračujeme vpravo
3. nové pole, kde hledáme, je tedy {21, 23}
   podíváme se opět na prostřední prvek (pole má 2 prvky, tj. na 0. prvek) = 21
   naše hledané číslo 21 == 21, čili úspěch

Prvek 21 jsme našli na třetí pokus. Na jaký pokus by to bylo se sekvenčním vyhledáváním? A představte si, že v realitě nemluvíme o pár záznamech, ale milionech či miliardách záznamů.

Metoda binárního vyhledávacího stromu

Klasický binární vyhledávací strom je takový, kdy každý uzel má pouze dva potomky, přičemž levý potomek je menší než uzel a pravý potomek je větší než uzel. Takový strom musí být v databázi uložený (tvoří se při ukládání nových hodnot do indexu).

Zkusíme si variantu binárního vyhledávacího stromu, tzv. AVL strom (samovyvažovací strom) vytvořit. Samovyvažovací strom má navíc podmínku, že počet úrovní levého podstromu a pravého podstromu se pro žádný uzel nesmí lišit o více než 1. Vezměme si pro příklad pole {17, 5, 19, 2, 21, 9, 18, 3, 1}. Zkuste si jej klidně vytvořit také na URL https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

Přidávání vypadá jednoduše, že. A skutečně je – dokud nedosáhneme stavu, kdy se počet úrovní v levém a pravém podstromu bude lišit o více než 1. Pojďme si tedy do výsledného stromu přidat například prvek 4 a uvidíme, co se stane:

Přidáme-li prvek 4, pak pro uzel 5 nastane stav, kdy není vyvážený (levý podstrom má délku 3 a pravý podstrom délku 1). Je tedy třeba se vyvážit, a to udělá tím, že místo sebe zvolí uzel z levého podstromu „3“:

Přidáme-li prvek 10, způsobíme stejný problém na samém vrcholu – uzel 17 bude mít v levém podstromu délku 4 a v pravém podstromu délku 2. Je tedy třeba se vyvážit, a to udělá tím, že místo sebe zvolí uzel z levého podstromu „5“:

Vlastní vyhledávání je pak snadné. Pro příklad zkusíme vyhledat prvek 19:

• začínáme od vrcholu, tj. 5
  19 > 5, čili jdeme do pravého podstromu
• pokračujeme s prvkem 17
  19 > 17, čili jdeme opět do pravého podstromu
• pokračujeme s prvkem 19
  19 == 19, čili prvek byl nalezen na třetí pokus.

ALV strom může být rychlejší než binární půlení intervalů (složitost až O(log₂N)). Je efektivní zvláště pro dynamická data. Vkládání je rychlejší než do setříděného pole potřebného pro metodu binárního půlení – vyvažování totiž může probíhat asynchronně.

SŘBD v případě MariaDB nejvíce používá variantu B-stromu. Ten funguje velmi podobně, jen může mít více než jedno číslo v každém uzlu, takže je plošší. Zkuste si vytvořit B-strom s maximální úrovní 4 pro stejnou sadu prvků zde: https://www.cs.usfca.edu/~galles/visualization/BTree.html

Zkusíme si opět vyhledat prvek 19:

• hledáme nejprve ve vrcholovém uzlu {2, 5, 17}, kde 19 > 17, čili jdeme na ukazatel nejvíce vpravo
• pokračujeme s podstromem {18, 19, 21} a tam jsme 19 našli napoprvé.

Vyhledávání za použití hashovací funkce

Představte si, že máme nějakou ideální hashovací funkci, která nám z každého prvku pomocí pouhého jednoho výpočtu udělá rovnou jeho číslo v seznamu. Složitost takového algoritmu niž nelze překonat – je O(1).

Pro představu si zkusíme zvolit jednoduchou hashovací funkci, která je rovna součtu ASCII hodnot jednotlivých znaků řetězce, přičemž součet proženeme operací modulo 10 (pouze zbytek po celočíselném dělení 10).

Například pro slovo Apple máme ASCII hodnoty písmen: 65 + 112 + 112 + 108 + 101 = 498.
498 % 10 = 8

Máme-li prvky {Apple, Banan, Sloup, Robin, Hlava, Jelen}, budou hodnoty hashovací funkce následující:

Hashovací tabulka ale vypadá jinak – vlevo je hodnota hashovací funkce a vpravo odkaz na záznam s daným prvkem (my si tam uvedeme přímo prvek):

Hledáme-li tedy například prvek „Robin“, pomocí hashovací funkce si spočítáme, že bude na místě 6, a tam jej nalezneme. Na první pokus.

Je-li správně zvolená hashovací funkce, je tento způsob bezkonkurenčně nejrychlejší. Je jednoduchý na programování. Nevýhodou může být složité určení správné hashovací funkce.

Jestliže třeba budeme chtít přidat ještě prvek Marek, pak y = f(Marek) = 496 % 10 = 6. Na místě 6 už ale máme Robina, tj. dojde ke kolizi a k tzv. řetězení (na místě 6 bude nejprve Robin a dále ukazatel na Marka).

Je-li nesprávně zvolená hashovací funkce, může složitost limitně dojít až k O(N).