Vrste indeksov

Gosti/redki indeks

Gosti indeks

na vsako polje iz osnovne datoteke kaže posamezen kazelec iz indeksa

velja: (P1, P2, ... Pn) -> (P1, P2, ... Pn, D1, D2, ... Dm) elementi ki tvorijo ključ indeksa se ujemajo z enakoimenovanimi elementi v zapisu osnovne datoteke.

za iskanje po gostem indeksu lahko uporabimo kateri koli algoritem za iskanje po zaporednih datotekah.

Redki indeks

kazalci iz indeksa kažejo na skupine zapisov osnovne datoteke

Redki indeks se uporablja le če je osnovna datoteka zaporedna in je indeks primarni indeks. Redki primarni indeks sestavljajo zapisi, v katerih nastopa kazalec na skupino k zaporednih polj in ključ katerega elementi se ujemajo z enakoimenovanimi elementi v prvem zapisu skupine.

Dense/Sparse Indices

Primarni/sekundarni indeks

• Primarni indeks ne vsebuje duplikatov
• Sekundarni indeks lahko vsebuje duplikate
• Če vemo, da duplikati ne obstajajo, potem pravimo temu indeksu unique indeks
• Za dva podatkovna vpisa pravimo, da sta duplikata, če vsebujeta enaki vrednosti za iskalni ključ

Primarni indeks

indeksiranje datoteke je izvedeno po njenem ključu (datoteka je urejena po nekem iskalnem ključu, primarni indeks pa je povezan s tem ključem)

Primary indices

Sekundarni indeks

sekundarni indeks indeksira datoteko po nekem elementu, ki ni ključ datoteke.

Secondary indices

Enonivojsko/večnivojsko indeksiranje

Enonivojsko indeksiranje

indeksirana je osnovna datoteka – v indeksu poiščemo kazalec na polje ali skupino polj v osnovni datoteki, kjer nato poiščemo iskani zapis

Index -> Datoteka

Večnivojsko indeksiranje

indeksirana je osnovna datoteka, indeksiran je indeks na osnovno datoteko, indeksiran je indeks na indeks itd.

IndexN -> ... -> Index2 -> Index1 -> Datoteka

Statični/dinamični indeks

Statično indeksiranje

indeks ostaja nespremenjen med spremembami datoteke (dodajanje in brisanje podatkov). Ko postane iskanje s pomočjo indeksa prepočasno, se izvede reorganizacija.

Dinamično indeksiranje

indeks se ob dodajanju in brisanju zapisov osnovne datoteke prilagaja vsebini, tako da so iskalne poti do vseh zapisov v osnovni datoteki enako dolge; indeksa ni potrebno nikoli reorganizirati