Razpršena datoteka
Razpršena datoteka
Lastnosti razpršene datoteke:
- zapisi so urejeni po vrednosti ključa;
- lego zapisa določa razpršilna funkcija;
- Ak=razpršilna_funkcija(KljučK);
- razpršilna funkcija priredi zapisu na osnovi njegovega ključa K naslov polja (ali skupine polj) Ak, v katero se zapis shrani.
Slika 1 Delovanje razpršilne funkcije
Pričakovano število zapisov v datoteki je (praviloma) veliko manjše od števila možnih vrednosti ključa. Zato je naloga razpršilne funkcije r, da opravi čim enakomernejšo porazdelitev vrednosti ključev zapisov preko naslovnega področja (da bi prihajalo do minimalnega števila kolizij).
Variante razprševanja
- Razpršilna funkcija takoj izračuna naslov fizičnega bloka v katerem so ostali podatki (glej sl. 1). Ta način je primeren za primarni indeks.
- Razpršilna funkcija izračuna naslov bloka v katerem se nahaja kazalec na blok s podatki (glej sl. 2). Ta način je primeren za sekundarne indekse.
Slika 2 Delovanje razpršilne funkcije
Prednosti in težave razprševanja
Prednost: iskanje je zelo hitro (ko se izračuna vrednost razpršilne funkcije je dobljen naslov bloka, ki se ga nato le prebere z diska; za dostop do podatka potrebujemo le en dostop do diska).
Slabost: težko je definirati dobro razpršilno funkcijo. Zato prihaja do
• kolizij (več kandidatov za enak naslov) in
• pretirane porabe prostora (datoteka ima veliko ‘lukenj’).
Razpršene datoteke niso primerne za zaporedno obdelavo podatkov.
Primer razpršilne funkcije
- ključ = ‘x1 x2 … xn’ // niz n znakov
- imamo b fizičnih blokov datoteke
- razpršilna funkcija: h = (x1 + x2 + … + xn) mod b // preslika vse ključe v območje 0, 1, …, b-1
Razglabljanje
Kdaj bo predlagana rapršilna funkcija primerna?
Primeri težav pri uporabi razpršene datotečne organizacije
Izkoristek prostora razpršene datoteke se računa po formuli:
Izkoristek = število uporabljenih ključev / maximalna zapolnjenost blokov
Priporočilo je, naj bo izkoristek med 50% in 80%.
- Če je izkoristek < 50% gre za pretirana izguba prostora
- Če je izkoristek > 80% je uporaba prelivnega področja je močno odvisna od kakovosti razpršilne funkcije in od številka ključev v bloku.
Ukrepi pri odpravljanju težav z naraščanjem velikosti datotek z razpršeno datotečno organizacijo
- Uporabljamo prelivna področja in po potrebi izvajamo reorganizacije.
- Uporabljamo dinamično razprševanje – število fizičnih blokov se lahko spreminja:
- Razširljivo // uporabi se:
- i bitov vrednosti razpršilne funkcije, i se s časom povečuje ali
- direktorij kazalcev na fizične bloke (v direktoriju je 2i kazalcev)
- Linearno // število fizičnih blokov se povečuje za 1