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. 2¹⁹) 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 log₂(2¹⁹ /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.