Rejstřík (databáze)
Ve vědě o počítačích , v databázích , An index je datová struktura používá a udržuje systém pro správu databází (DBMS), aby mohl rychle najít data. Použití indexu zjednodušuje a zrychluje operace vyhledávání, řazení, připojení nebo agregace prováděné systémem DBMS.
Index umístěn na stole umožní DBMS přístup k evidenci velmi rychle, v závislosti na hodnotě jednoho nebo více oborů .
Zásada
Index je automaticky udržovaná struktura, která usnadňuje vyhledání záznamů v souboru. Použití rejstříků je založeno na následujícím pozorování: najít knihu v knihovně, místo toho, abyste každou knihu zkoumali jednu po druhé (což odpovídá postupnému vyhledávání ), je rychlejší nahlédnout do katalogu, kde jsou klasifikovány podle tématu, autor a název. Každá položka v indexu má hodnotu získanou z dat a ukazatel na své původní umístění. Záznam lze tedy snadno vyhledat vyhledáním jeho umístění v rejstříku.
Index lze objednat, nasekaný, hustý nebo řídký:
- Uspořádaný index obsahuje seznam hodnot načtených z tabulky a seřazených.
- V hašovaném indexu jsou hodnoty transformovány hashovací funkcí .
- V hustém indexu se odkazuje na všechny záznamy v tabulce.
- V rozptýleném indexu se odkazuje pouze na část záznamů.
Primární index na stole je první index , který slouží k vyhledání záznamů. Tabulka může kromě primárního indexu obsahovat také sekundární indexy . Každá tabulka může mít jeden nebo více indexů. Index může pocházet z jednoho pole nebo může kombinovat několik polí.
Technický
Indexy používá DBMS pro mnoho operací. Indexy usnadňují třídění, hledání, seskupování a připojování. Nejběžnější strukturou indexu je B-strom . Jiné struktury existují, ale jsou zřídka používány - ISAM , hash tabulky nebo bitmapy.
- stromová struktura: kmen, ke kterému jsou připojeny větve s rozvětvením a listy na konci. Všechna vyhledávání se provádějí od kufru. Hledáním mezi větvemi pro tu, která obsahuje hledanou hodnotu, dokud nedosáhnete listu.
Pro urychlení operací se indexové stromy zaznamenávají do bloku s velmi velkým počtem důsledků: Pevné disky, na které se zaznamenávají indexy, načítají data v blocích několika kilobajtů a doba potřebná ke čtení bloku je obvykle mnohem kratší než čas potřebný k jeho vyhledání. S touto konstrukcí vyžaduje hledání záznamu v dávce několika milionů pouze 2 nebo 3 operace.
Rejstříky lze přidat pomocí příkazu SQL . Existence indexů je zásadní pro urychlení operací manipulace s daty. Hlavní příčinou zklamání je nedostatečné používání indexů. Systém pro správu databází (zkráceně DBMS) nenajde indexy, které jsou nezbytné pro efektivní provedení operací, které jsou od něj požadovány. Důvody nedostatečného použití spočívají v tom, že dokumentace DBMS týkající se používání indexů je často vágní a stručná a zdůrazňuje spíše jejich nevýhody než jejich výhody.
Indexy používá zejména optimalizátor dotazů :
- Optimalizátor je složka DBMS, která najde nejekonomičtější způsob spuštění dotazu. Optimalizátor prozkoumá různé možné scénáře a odhadne počet operací požadovaných pro každý scénář a poté vybere scénář, který vyžaduje nejméně. Počet požadovaných operací závisí na přítomnosti indexů a také na počtu řádků v tabulce a rozložení hodnot.
Typy indexů
- Nejběžnější strukturou indexu je strom B ( strom b ). Uložením různých hodnot pole do vyváženého stromu bude DBMS schopen upřednostnit záznamy podle pole, jehož rozsah hodnot je nekonečný (nebo téměř).
- Dalším typem indexu je bitmapový index . Skládá se z jednoduché tabulky označující pro každou možnou hodnotu pole seznam záznamů, které mají tuto hodnotu pro toto pole.
- Existují také indexy podle hash tabulky . Hlavní nevýhodou takového indexu je, že umožňuje výběr pouze podle rovnosti, protože nezachovává pojem pořadí. Pokud n je počet záznamů v tabulce, pomocí vyvážené hašovací tabulky lze snížit počet záznamů, které chcete procházet , druhou odmocninu n (pak je tabulka tvořena hodnotami hash, které každý přistupují k záznamům). Stejná poznámka o efektivitě existuje i pro bitmapový index: DBMS musí být schopen přímého přístupu k dané hodnotě hash, aniž by musel procházet seznam možných hodnot hash.
Dopady na výkon modifikace
Při vkládání nebo aktualizaci záznamu databáze dochází k mírnému snížení výkonu: DBMS musí skutečně aktualizovat indexy tak, aby i nadále odrážely stav záznamů. Z tohoto důvodu se při navrhování databáze budeme snažit definovat pouze indexy, které bude systém používat. Ty budou navíc dobře identifikovány pouze analýzou systému (a zejména mechanismů dotazování databáze) s ohledem na jeho optimalizaci.
Jiné formy indexace
Další typy struktur nabízejí funkce indexování:
- Seskupené tabulky
- Zhmotněné zobrazení
Poznámka k vícesloupcovým indexům
V případě vícesloupcového indexu se může systém DBMS „rozhodnout“ použít jej částečně, v pořadí podle sloupců indexu. Jinými slovy, index na sloupcích (c1, c2, c3, c4) lze použít jako index (c1, c2, c3), (c1, c2) nebo (c1).
Poznámky a odkazy
- (en) Carlos Coronel, Steven Morris a Peter Rob, Database Systems: Design, Implementation, and Management , Cengage Learning - 2012, ( ISBN 9781111969608 )
- (en) SK Singh, Database Systems: Concepts, Design and Applications , Pearson Education India - 2009, ( ISBN 9788177585674 )
- (en) Gavin Powell, Beginning Database Design , John Wiley & Sons - 2006, ( ISBN 9780764574900 )
- (en) Tapio Lahdenmaki a Mike Leach, Relational Database Index Design and the Optimizers , John Wiley & Sons - 2005, ( ISBN 9780471721369 )
- (in) Ken England, Gavin JT Powell, Microsoft SQL Server 2005 Optimization Performance and Tuning Handbook , Digital Press - 2011 ( ISBN 9780080554082 )