// Částečně kradeno z https://github.com/Krejdom/school_notes/blob/master/PB154.md
- Search key (výběrový klíč) - množina atributů, která se využívá k budování indexu
- Index file - skládá se z index entries:
(search-key, pointer)
- typy:
- Ordered indices (uspořádané): jednotlivé položky dat se dají uspořádat
- Hash indices: key to adress transformation; z klíče nám pomocí funkce vznikne adresa
-
typy dotazů:
- Exact-match query: záznam má přesně danou hodnotu
- Range (interval) query: záznam je v rozmezí hodnot
-
Vyhodnocení indexů:
- Podporované přístupové typy
- Doba přístupu (scalability)
- Doba vkládání
- Doba mazání
- Využití místa
- Primary index: klíč je souhlasný s klíčem podle kterého je sekvenční soubor uspořádán
- někdy taky clustering index (shlukovací)
- Secondary index: indexy, jejíž uspořádání klíču je jiné než sekvenční uspořádání klíčů
- někdy také nonclustering index
- Index-sequential file: sekvenční soubor s primárním indexem
- pro každou položku v databázi mám index
- může být i na skupinu se stejnou hodnotou –> ukazuje na první prvek skupiny (máme seřazeno daným atributem)
- obsahuje index pouze pro některé hodnoty
- použitelné pokud jsou položky sekvečně seřazené
- Hledaný prvek je buď hodnota v index file,
- nebo hodnota mezi dvěma záznamy v index file
- vs hustý index:
- používá méně místa a má méně aktualizací
- obecně pomalejší pro hledání záznamů než hustý index
- indexy je soubor rozdělen na bloky
- Jestliže primární index se nevleze do paměti, přístup je drahý
- Řešení: Primární index budeme považovat jako sekvenční soubor a uděláme na něj řídký index
- outer index - a sparse index of primary index
- inner index - the primary index file
- Jestli se ani outer index nevleze do paměti, můžeme indexaci zopakovat
- dense index:
- jestli smažu nějakou položku, musím smazit i daný index
- sparse index
- Jestliže se smaže položka, která není v indexu nic se nestane
- Jestli se ale smaže položka, která je v indexu, musí se najít nový index, pokud už je daný index v indexovacím souboru znovu se už nepřidá
- dense index:
- při vložení nového klíče, musím vložit nový index
- sparse index:
- přidání nového indexu pouze pokud je nový blok
- n-ární vyvážený strom, kde
n značí počet pointerů z uzlu
- klíčů je
n-1 (mohou být replikované)
- každý listový uzel je naplněn alespoň polovinou klíčů (zaokrouhleno nahoru)
- každý vnitřní uzel má alespoň
n/2 pointerů
- všechny větve v B-stromech i B+-stromech mají stejnou délku
- hodnoty klíčů v každém uzlu jsou uspořádané
- výška stromu je logn/2(K)
p1 | k1 | p2 | k2 - příklad podstromupn - pointerkn - klíč- pro podstrom
p2 platí pn < k2 a zároveň pn >= k1
- Rozdílná délka řetězců jako klíče
- Prefix compression
- Vytvoření B+-stromy s daty, která již znám dopředu (přidávat po jednom by bylo velmi neefektivní)
- Řešení:
1.
- setřídění vstupů
- vložení v uspořádaném stavu
- vložení půjde to existující stránky (nebo způsobí rozštěpení)
- lepší efektivita IO
- Bottom-up B+-tree constrution
- setřídění vstupů
- Vytvoření stromu úroveň po úrovni, začínaje na úrovni listů
- Implementováno většinou databázových systémů
- nereplikuje informaci oproti B+-stromu
p1 | b1 | k1 | ... - vždy musí být tyto tři hodnoty po soběbn je bucket (ukazatel na záznam kn)
- Composite search keys - obsahují více než jeden atribut
- Lexikografické uspořádání: (a1,a2) < (b1,b2) pokud
- a1 < b1, nebo
- a1 = b1 a a2 < b2
- bucket = jednotka úložiště obsahující jeden nebo více záznamů (typicky diskový blok)
- hashovací funkce by měla být uniformní (průměrný počet prvků je ve všech bucketech stejný) a náhodná
- buckets overflow = prvky se nevlezou do nám volných buckets
- otevřené (na jeden index se uloží pouze jeden prvek) vs. zavřené (bucket = linked list) hashování
- statické (mapuje hodnoty na omezený počet indexů) vs. dynamické (počet indexů se může v průběhu dynamicky měnit, např. extendable hashing) hashování
CREATE INDEX <index-name> ON <relation-name> (<attribute-list>)
DROP INDEX <index-name>