Indeks
Iz E-študij, proste zakladnice študentskega znanja
Indeks je zunanja podatkovna struktura, ki pomaga najti zapise, ki ustrezajo določenemu pogoju in lahko bistveno pospeši iskanje.
Včasih hočemo najti vse zapise, ki imajo določeno vrednost v določenem polju
Vsak indeks vsebuje iskalni ključ, ki je sestavljen iz enega ali več polj zapisov, ki se nahajajo v datoteki. Iskalni ključ je lahko katerikoli podmnožica polj zapisov v datoteki
Primer: Indeks nad tabelo ŠTUDENT ima lahko indekse nad naslednjimi polji oz. iskalnimi ključi:
- Indeks1: <Vpisna stevilka>
- Indeks2: <ime, priimek> (kompozitni ključ)
- Indeks3: <kraj, ime, priimek>
Datoteki, ki jo indeksiramo, pravimo tudi indeksirana datoteka
Indeks je datoteka, katere vsebina omogoča hiter dostop do zapisov v osnovni datoteki, ki je z indeksom indeksirana. Pod hitrim dostopom pojmujemo dostop, ki je (občutneje) hitrejši, kot pa ga sicer omogoča organizacija osnovne datoteke.
Indeks si lahko predstavljamo kot zbirko vpisov k*, kjer je k ključ indeksa, * pa kazalec(ci) na zapise, ki imajo polja v zapisu enaka ključu indeksa
Pojavita se 2 vprašanji:
- Kako so podatkovni vpisi v indeksu organizirani, da bodo podpirali hitro in učinkovito iskanje zapisov?
- Ena rešitev za organizacijo indeksa je uporaba razpršene datoteke (naslednja slika), ki omogoča hitro iskanje zapisov
- Obstaja tudi več drugih indeksnih struktur, ki omogočajo hitro iskanje in bodo predstavljene v nadaljevanju
- Kaj natančno je shranjeno v podatkovnem vpisu (Podatkovni vpis k* nam omogoča dobiti enega ali več zapisov z vrednostjo ključa k)
- k* je dejanski zapis (z iskalnim ključem k),
- podatkovni vpis je par <k, rid>, kjer rid predstavlja record id zapisa z vrednostjo indeksnega ključa k,
- podatkovni vpis je par <k, rid-list>, kjer je rid-list seznam record id-jev tistih zapisov, ki imajo v poljih vrednost enako indeksnemu ključu.
