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.

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

1. 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.
2. 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.

Delovanje razpršilne funkcije

Prednosti in težave razprševanja

Prednost: iskanje je zelo hitro (ko se izracuna 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 (vec kandidatov za enak naslov) in
• pretirane porabe prostora (datoteka ima veliko ‘lukenj’).

Razpršene datoteke niso primerne za zaporedno obdelavo podatkov.

Avtorji: Tea Lončarić , Andreja Vehovec, Marko Kastelic , David Drofenik, Saša Divjak, Alenka Kavčič , Matija Marolt, Marko Privošnik , Milan Podbršček, Janko Harej, Andrej Florjančič