![]() |
![]() | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Index
Přirozeným požadavkem na každou databázi je rychlé vyhledávání. To se dá v SŘBD zařídit různými (i když ne mnoha) způsoby, z nichž jeden se nazývá indexování. Co je index? Odedávna to byl obyčejný seznam. Někdy i ne zcela obyčejný, připomeneme-li např. Index librorum prohibitorum. Index má na svém konci každá dobrá odborná kniha, jako malý, ale užitečný index, nám poslouží písmenka abecedy našeho telefonního notýsku. Index je tvořen záznamy < klíč, adresa> , kde klíč je hodnota nějakého vhodného atributu, např. pro index v odborné knize by se takový atribut mohl jmenovat VÝZNAMNÉ_POJMY. Index si pak lze představit jako soubor záznamů, nebo jako speciální dvousloupcovou tabulku. Přirozeně, ve světě relačních databázích budeme indexovat podle vybraných atributů relace, indexovány budou řádky tabulky. Že je to jednoduché? Ano, ale bez problémů to nepůjde. Hledáme-li významný pojem v indexu VÝZNAMNÉ_POJMY, běžíme vlastně očima po záznamech indexů, které jsou naštěstí seřazeny abecedně. Ve skutečnosti se strefíme do nějakého místa, hledáme buď před ním nebo za ním atd. a po několika krocích jsme obvykle úspěšní. Počítač by to dělal podobně. Představme si ale nějakou větší databázovou tabulku a atribut s dlouhými klíči, např. FILM(JMÉNO_F, REŽISÉR, HVĚZDA), kde JMÉNO_F je dlouhé maximálně 68 Byte. Uvažujme velikost adresy 4 Byte (tj. lze adresovat 4 GByte). Pak by každý záznam indexu vyžadoval 100 Byte. Pro 524 288 (tj. 219) filmů bychom tedy na index potřebovali skoro 53 MByte. Uvážíme-li typickou velikost stránky 2 KByte, pak je nutné v nejhorším případě přečíst 26 215 stránek a to je příliš mnoho (řádově několik minut). První zlepšení, které nás napadne, bude kopírovat náš “oční” přístup. Algoritmicky ho lze simulovat “půlením intervalu”, tj. budeme číst prostřední stránku (v polovině indexu), další v polovině poloviny (ve čtvrtině indexu) atd. Počet čtení stránek je log2(219 /20), tj. zaokrouhleně 15. I to se ale stále považuje za mnoho. Vhodnější zlepšení spočívá ve více úrovních indexu. Považujeme-li dosud vytvořený index za první úroveň, pak stejným stylem můžeme k němu vytvořit další index - index druhé úrovně. Jeho záznamy budou obsahovat vždy první klíč na stránce první úrovně a adresu této stránky. Záznamů tedy bude 26 215 a umístěny budou v 1311 stránkách. 3. úroveň vyžaduje 66 stránek, 4. úroveň 4 stránky. Konečně na poslední, 5. úroveň, stačí jedna stránka. Při vyhledávání záznamu o filmu daného jména, požadovaný počet čtení stránek je pouhých 5 pro 5ti-úrovňový index a jedno čtení stránky obsahující řádky tabulky FILM. Pracuje-li se s touto tabulkou, je obvykle stránka s vrcholovou úrovní indexu (tzv. master index nebo česky hlavní index) načtena do vnitřní paměti, takže při eventuálních dalších hledáních filmů se jedno čtení ušetří. Tato idea je základem tzv. indexovaných nebo indexsekvenčních souborů. Skutečně - záznamy o filmech tvoří jistý (primární) soubor, který není nutně ani sekvenční, ani setříděný podle atributu JMÉNO_F, je však indexován podle vybraného atributu. Kdyby primární soubor splňoval obě přídavné vlastnosti, šlo by využít uspořádání k jinému způsobu indexace. Neindexovali bychom totiž záznamy primárního souboru, ale celé jeho stránky. V první úrovni indexu by tedy byly záznamy s prvním klíčem v dané stránce primárního souboru. Těchto záznamů je méně než 26215, protože se zřejmě vejde několik řádků tabulky FILM do jedné stránky. Obdrželi bychom indexsekvenční soubor. Víceúrovňový index byl znám již v 60. letech. Mezi nejznámější, dnes již historické, implementace patří metoda ISAM (IBM) v operačním systému OS/360. Základní idea byla ale dovedena do poněkud odlišné implementace, která využívala hardwarových vlastností magnetického disku. Byl-li soubor uložen na několika cylindrech disku, pak existovala jedna úroveň indexu, kde bylo možno zjistit, na kterém cylindru se nachází záznam s daných klíčem a na každém cylindru byl opět kus indexu, kde se zase dalo zjistit, na které stopě tohoto cylindru se nachází záznam s daným klíčem. Uvedené postupy mají ovšem jednu zcela zásadní vadu. Jsou totiž statické. Představme si, jak se index chová v dynamickém prostředí. Vyjděme ze situace, že primární soubor je znám, je k dispozici. Pak se jednotlivé úrovně indexu vytvoří speciálním programem a index je připraven k použití. Co se však bude dít, budeme-li aktualizovat primární soubor? Při vkládání záznamu není vůbec zřejmé, kam jej vlastně uložit. Začněme od indexsekvenčního souboru. Protože primární soubor musí být stále setříděný, znamenalo by to celý primární soubor spolu s novým záznamem znovu setřídit a vytvořit kompletně znovu všechny úrovně indexu. Tak se to samozřejmě nedělá. Nový záznam se vloží do oblasti přetečení, což je část disku, kde se nové záznamy skladují za sebe. Uspořádání se docílí tím, že do místa, kam by nový záznam patřil v primárním souboru, se umístí ukazatel do oblasti přetečení, kde skutečně nový záznam leží. To obecně vede k tomu, že všechny záznamy patřící mezi dva záznamy v primárním souboru se řetězí v oblasti přetečení tak, že řetězec zachovává uspořádání (viz obr. 1).
1.1 3.1 4.1 2 .úroveň indexů 5.1
2.1 6.1 2.2 7.1
8.1 1. úroveň indexů primární soubor
10.1 10.2 10.3 oblast přetečení Obr. 1 Příklad indexsekvenčního souboru Je pochopitelné, že záznamy řetězce mohou být “daleko” od sebe, tj. na různých stránkách. Hledání se tak komplikuje. Místo konstantního počtu přístupů na disk, který je dán počtem původních úrovní indexu, se přibírají další stránky a vyhledávání indexsekvenčního souboru se tak stává lineární. Teprve, když již se celkové chování datové struktury zhorší natolik, že je neúnosné, provede se reorganizace. Jde o speciální, časově náročnou akci, kdy se všechny záznamy primárního souboru včetně těch, co jsou v oblasti přetečení, zařadí do nového primárního souboru, vytvoří se nový index a zase se začne s čistým štítem, tj. prázdnou oblastí přetečení. Všimněte si, že index, tak jak byl na počátku vytvořen, zůstává u indexsekvenčního souboru pevný, veškeré změny se odehrávají hlavně v oblasti přetečení. Indexovaný soubor není již závislý na uspořádání primárního souboru, tj. nový záznam může být umístěn dost libovolně. Bohužel, je ale nutné reorganizovat průběžně indexové úrovně, což je opět drahá záležitost. V praxi to může např. znamenat odkládání aktualizace indexu a její provádění dávkově jednou za den. Shrneme-li, je zřejmé že pro dynamické prostředí databází se takto vystavěné indexové struktury vůbec nehodí a také se v SŘBD nepoužívají. Zabývali jsme se jimi tak trochu z historických důvodů, ale i proto, že se na nich dá hezky ukázat základní myšlenka indexace. Pověstné B-stromy nebo bitové mapy, které se dnes používají pro implementaci indexových struktur v databázích (např. pro realizaci příkazu CREATE INDEX v SQL) odkládáme do dalších hesel databázové abecedy. <seznam dílů seriálu> <COMPUTERWORLD> |