ISAM

ISAM (Indexed Sequential Access Method):

• je statičen indeks,
• učinkovit v primerih, ko osnovna datoteka ne spreminja pogosto,
• ni učinkovit pri datotekah, ki se hitro povečujejo ali krčijo.

Za primer vzemimo sortirano datoteko oseb, po atributu “starost”.

Če hočemo najti vse osebe starejše od 30 let, moramo najprej najti prvo (s pomočjo binarnega iskanja), ki je starejša od 30 in od te naprej prebrati preostale zapise datoteke.

Lahko bi izdelali dodatno datoteko, s po enim zapisom za vsako stran v osnovni datoteki (dodatna datoteka je tudi urejena po atributu starost)

Format strani v indeksni datoteki

• Vsaka stran v indeksu vsebuje en kazalec več, kot pa je ključev na strani. Ključ predstavlja separator vsebine, na katero kažeta levi in desni kazalec
• Binarno iskanje se sedaj izvede nad indeksno datoteko, ki je manjša od osnovne datoteke. Na ta način smo dosegli hitrejše iskanje

Velikost indeksne datoteke poraja idejo o ISAM indeksu: Zakaj ne bi pri gradnji indeksa uporabili REKURZIJO, tako da bi velikost vsakega posameznega indeksa znašala samo eno stran?

• Gradnja indeksa nas pripelje do drevesne strukture

Vozlišča

Vozlišča

ISAM indeks sestavljajo tri vrste strani, ki vsebujejo:

• Vozlišča, ki niso listi (non-leaf pages)
• Vozlišča, ki so primarni list in so alocirani sekvenčno (vozlišča, ki so bila listi takoj po kreiranju indeksa) (primary leaf pages)
• Vozlišča, ki so dodana primarnim listom (in so tudi primarni listi) zaradi spreminjanja vsebine tabele in s tem indeksa (overflow pages)

• Struktura ISAM indeksa je od njegovega kreiranja dalje popolnoma statična (razen overflow strani)
• Vsako indeksno vozlišče je velikosti ene strani, vsi podatki (pari: podatek, kazalec na podatkovno stran) pa se nahajajo v listih drevesa
• Ko se indeksna datoteka kreira, so vse strani v listih urejene zaporedno in urejene po ključu

• Ko se podatkovno datoteko in posledično v listne strani dodaja podatke, je lahko potrebno v indeks dodati nove strani (overflow pages), kajti drevesna struktura indeksa je statična

• Ko je enkrat indeks kreiran, brisanja in vstavljanja vplivajo le na spremembe listov
• Dobilo lahko dolge verige overflow strani => počasno delovanje
• REŠITEV: ponovna gradnja indeksa (znebimo se overflow strani)
• ISAM je dober za datoteke, ki se jih malo ažurira. Začetni indeks se lahko zgradi tako, da so strani v listih 20% nezasedene (imamo nekaj maneverskega prostora za vstavljanje)

Iskanje in vstavljanje

Vozlišča nas usmerjajo do cilja, kazalec cilja nam pokaže naš podatek.

Brisanje

Pobrisana 51

• Če ostane vozlišče na overflow strani prazno, sta vozlišče (in stran) odstranjena
• Če zbrišemo zapis, ki ima vrednost ključa enako podatku v primarnem listu, potem pustimo stran (kjer je primarni list) nespremenjeno (lahko ostane tudi prazna). Namenjena je bodočim vstavljanjem
• Če zbrišemo zapis, ki ima ključ enak vrednosti v vozlišču, potem vozlišča, ki ni list, ne spreminjamo. Vozlišča, ki niso listi, so usmerjevalnega značaja za iskanje in ostale operacije

• Po brisanju vrednosti 51 je ta vrednost ostala v vozlišču, ki ni list. Če bi naknadno iskali vrednost 51, bi šele v primarnem listu ugotovili, da je ni .

Kompleksnost iskanja

Kompleksnost iskanja je

N

število strani s primarnimi listi

F

število naslednikov indeksnega vozlišča (strani, ki vsebuje vmesna vozlišča, ki niso listi – nonleaf pages)

To je dosti hitreje kot binarno iskanje. Dobra stran ISAM je, da zaradi statičnosti niso potrebna zaklepanja strani, ki niso listi, ker se vsebina le teh nikoli ne spreminja.