Indeksi
Indeksi
Razlogi za uporabo indeksov
Dostikrat (največkrat) uporabniki iščejo podatke tako, da:
- podajo vrednost enega ali več podatkovnih elementov – primer:
SELECT * FROM Dijak WHERE Razred=‘G1A’; // Poišči vse dijake razreda G1A
- podajo interval vrednosti nekega podatkovnega elementa – primer:
SELECT * FROM Matura WHERE Tocke BETWEEN 30 AND 33; // Poišči podatke o maturi za kandidate, ki so dosegli med 30 in 33 točk
Indeksi so podatkovne strukture, ki omogočajo učinkovito izvedbo tovrstnih poizvedb.
Indeks je datoteka, katere vsebina omogoča hiter dostop do zapisov v osnovni fizični datoteki, ki je z indeksom indeksirana.
Uporaba indeksa - za hiter dostop do podatkov osnovne datoteke; dostop s pomočjo indeksa je hitrejši, kot ga sicer omogoča organizacija osnovne datoteke.
Redundantnost indeksa - indeks je možno vedno znova kreirati (na osnovi podatkov v osnovni datoteki).
Vrste indeksov: primarni in sekundarni indeksi
Primarni indeks
- Indeksiranje osnovne datoteke je izvedeno po njenem ključu (ključ indeksa in ključ osnovne datoteke sta enaka).
- Lastnosti: razločevalnost (unique), določa privzeto urejenost zapisov osnovne datoteke, največkrat tudi zahtevan vnos (required).
- Uporaba: za povezovanje tabel (kreiranje relacij).
- Vsaka tabela ima največ en primarni indeks.
Sekundarni indeksi
- Indeksiranje osnovne datoteke je izvedeno po podatkovnem elementu (skupini podatkovnih elementov), ki nastopa v tipu zapisa osnovne datoteke, vendar ni ključ.
- Tabele imajo lahko tudi več sekundarnih indeksov
Vrste indeksov: gosti in redki indeksi
Gosti indeksi
- Za vsak zapis osnovne datoteke obstaja zapis v indeksni datoteki.
- Vrednosti podatkovnih elementov, ki tvorijo ključ indeksnega zapisa se ujemajo z enako imenovanimi podatkovnimi elementi v zapisu osnovne datoteke.
- Kazalec indeksnega zapisa kaže na polje, v katerem se nahaja pripadajoči osnovni zapis.
- Ažuriranje: hkrati se spremenita osnovna in indeksna datoteka.
Redki indeksi
- Pogoj za uporabo redkega indeksa: osnovna datoteka je zaporedna + primarni indeks.
- V indeksu se nahaja po en zapis s kazalcem na vsako skupino polj z zapisi v osnovni datoteki
- Polja, ki tvorijo skupino, so polja, do katerih je možen hiter dostop npr. polja enega fizičnega bloka
- Indeks vsebuje tolikokrat manj zapisov od osnovne datoteke, kolikor polj vsebuje fizični blok osnovne datoteke; zato je iskanje po indeksu je bistveno hitrejše kot iskanje po osnovni datoteki.
- Redki primarni indeks sestavljajo indeksni zapisi, v katerih nastopata v paru kazalec na skupino polj in vrednost ključa zadnjega zapisa v skupini.
Redki in gosti indeks
Kaj pa, če je kljub vsemu indeksna datoteka prevelika?
- Uporabijo se večnivojski indeksi.
- Danes so najbolj uporabljani indeksi B+. Na spletni strani http://www.seanster.com/BplusTree/BplusTree.html si lahko ogledate dodajanje elementov v drevo B+, lahko pa tudi naredite svoje drevo.
Primer večnivojskega indeksa