Organizacija datotek in indeksiranje

Skoči na: navigacija, iskanje

Potrebno je določiti stroškovni model, ki opredeljuje stroške dostopanja do podatkov

Analizirali bomo tri osnovne datotečne organizacije:

• neurejeno datoteko
• urejeno datoteko
• razpršeno datoteko (vsi zapisi z istim hash-em se shranijo v isto datoteko)

• Namen analize je pravilna izbira datotečne organizacije, glede na potrebe. Nobena organizacija ne ustreza za vse potrebe.
• Rešitev za hitrejši dostop do zapisov je indeksiranje

• Stroškovni model omogoča oceniti stroške (v smislu izvajalnega časa) I/O operacij nad stranmi v PB
• Za analizo bomo uporabljali naslednje parametre:

B

število podatkovnih strani,

R

število zapisov na stran,

D

(povprečen) čas, potreben za branje ali pisanje strani,

C

čas za procesiranje zapisa,

H

čas, ki je potreben za uporabo hash funkcije nad zapisom (pri razpršenih datotekah).

• Tipične vrednosti znašajo: D=15 ms, C in H=100 ns

• Poenostavitve:

• Ker so I/O operacije časovno obsežnejše, stroške procesiranja lahko zanemarimo (C = H = 0),
• natančen model bi bil preveč zapleten, zato se zaradi lažjega razumevanja osredotočimo le na število strani, ki se jih prebere ali zapiše na disk in nam služijo kot število I/O operacij.

• Kot stroškovno metriko torej uporabljamo število I/O operacij, ki prenašajo (branje in pisanje) strani

• Poenostavitve lahko uporabimo, saj se izkaže, da predstavljeni model kljub poenostavitvi odraža dejanske trende pri uporabi različnih datotečnih organizacij

• Primerjamo stroške preprostih operacij za tri vrste datotek:

• neurejeno datoteko (heap): zapisi si vrstijo naključno,
• urejeno datoteko (sorted): vrstni red zapisov je določen glede na iskalni ključ),
• razpršeno datoteko (hashed): zapisi so grupirani v skupine na podlagi razpršilne funkcije (hash function).

• Cilj je poudariti, kako pomembna je pravilna izbira datotečne organizacije

Elementarne operacije

skeniranje

preberi vse zapise v datoteki. Vse strani iz datoteke je potrebno prenesti v Buffer pool

iskanje s pogojem ekvivalence

poišči vse zapise, ki ustrezajo določenemu pogoju. Strani, ki vsebujejo ustrezne zapise je potrebno prenesti z diska in na teh straneh je potrebno locirati želene zapise

iskanje z definiranjem območja

poišče vse zapise iz določenega območja. Ustrezne strani je potrebno prenesti z diska

vstavljanje

Vstavi dan zapis v datoteko. Potrebno je identificirati stran datoteke, v katero se bo zapis vstavil, prebrati to stran z diska, jo ažurirati in zapisati nazaj na disk. Od datotečne organizacije je odvisno ali bo potrebno poleg želene strani, z diska brati in nanj pisati še dodatne strani

brisanje

Brisanje zapisa s podanim rid (record id). Potrebno je identificirati stran z danim zapisom, jo prebrati z diska, jo ažurirati in zapisati nazaj na disk

Značilnosti datotečnih organizacij

Ko zanemarimo v izračunih vrednosti za C in H, potem dobimo naslednjo primerjalno tabelo z ocenami za posamezno datotečno organizacijo

neurejena datoteka

hitro skeniranje, vstavljanje in brisanje; počasno iskanje

urejena datoteka

omogoča hitro iskanje območja; srednja hitrost pri iskanju; počasno vstavljanje in brisanje

razpršena datoteka

hitro vstavljanje in brisanje zapisov; zelo hitro je iskanje na osnovi enakosti; nobene podpore izboru območja; skeniranje celotne datoteke je nekoliko počasnejše

• Nobena organizacija ni dobra za vse operacije.
• Neurejena datoteka je zelo primerna za skeniranje celotne datoteke
• Razpršena datoteka je najprimernejša pri uporabi iskanja s pogojem ekvivalence
• Urejena datoteka je najprimernejša pri iskanju intervalov

Indeksi

Včasih hočemo najti vse zapise, ki imajo določeno vrednost v določenem polju Organizacija neurejene datoteke nam ne pomaga pri iskanju zapisov INDEKS je zunanja podatkovna struktura, ki pomaga najti rid-je zapisov, ki ustrezajo določenemu pogoju INDEKS pospeši iskanje

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 Datoteki, ki jo indeksiramo, pravimo pogosto 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 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 indeksna polja enake ključu

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 (prejšnja 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 en 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, 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.

Gosti indeks

na vsak zapis osnovne datoteke, kaže kazalec iz indeksa

Redki indeks

kazalci iz indeksa kažejo na skupine zapisov osnovne datoteke

Primarni indeks

indeksiranje osnovne datoteke je izvedeno po njenem ključu (ključ indeksa in ključ osnovne datoteke sta enaka)

Sekundarni indeks

indeksiranje osnovne datoteke je izvedeno po podatkovnem elementu (polju), ki nastopa v zapisu osnoven datoteke, vendar pa ni ključ.

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.

Večnivojsko indeksiranje

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

Statično indeksiranje

indeks ostaja nespremenjen, čeprav se osnovni datoteki zapisi dodajajo ali iz nje brišejo; ko postane iskanje neučinkovito, se izvede reorganizacija indeksa.

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.

Osnovna datoteka ima strani s po tremi zapisi Zapis ima tri polja (name, age, sal) Redki indeks indeksira osnovno datoteko po polju name Gosti indeks pa indeksira osnovno datoteko po polju age