Soubor, souborove organizace
PV 062 Organizace souboru Jan Staudek http://www. .muni.cz/usr/staudek/vyuka/
}
w A| y < 5 4 23 1 0 / -. , )+ ( %&' $ # !"
Æ
Verze : jaro 2016
Osnova predna sky 2 2 2 2
Pojem soubor, klc , operace se souborem, zaznam Model, schema organizace souboru Dotaz nad souborem Klasi kace souborovych organizac
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
1
Databaze, soubor, zaznam, polozka (atribut)
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
2
Databaze, soubor, zaznam, polozka (atribut) 2
zakladn nastroj informacnch sluzeb pro dlouhodobe uchovav an a zprstupnov an dat { databaze databaze = kolekce souvisejcch dat vztahy mezi elementy dat v databazi jsou explicitn databaze je navrhovana pro pouzit aplikacnmy systemy databaze se v poctaci (na vnejsch pametech) uchovavaj jako kolekce pojmenovanych mnozin dat { souboru X databaze byv a spravovana systemem r zen baze dat, ktery je obvykle nezavisl y na operacnm systemu, mu ze vsak vyuzvat r adu sluzeb poskytovanych soucast OS { systemem souboru System r zen baze dat byv a soucast middleware { funkcn vrstvy mezi operacnm systemem a aplikacnmi systemy X X X X
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
3
Databaze, soubor, zaznam, polozka (atribut) 2
zakladn prvkem dat je pole, field, resp. polozka (item), resp. atribut, vlastnost (attribute) X s kazdym atributem souvis datovy typ urcujc obor moznych hodnot
atributu a mnozinu operac nad nimi X datove typy atributu jsou obvykle standardn datove typy pouzvane pri programovan integer, long integer, oating point, Boolean (0/1 nebo TRUE/FALSE), r etez znaku (pevne c i promenne delky), specialn e kodovan e datum a c as, . . . X atribut mu ze mt xn delku nebo promennou delku (ta pak mus byt explicitne udana nebo vyznacena de novanym oddelovacem) X atribut mu ze byt pojmenovany
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
4
Databaze, soubor, zaznam, polozka (atribut) 2
bazov a datova jednotka reprezentujc objekt zpracovavan y aplikac (osoba, mstnost, predmet, . . . ) je zaznam (redord) X zaznam tvor kolekce polozek X X X X X
se kterou aplikacn system pracuje jako s jednotkou dat zaznamy jsou tudz chrakterizovatelne svymi vlastnostmi, atributy implementacne jsou zaznamy tvoreny posloupnostmi polozek obsahujcch hodnoty atributu kolekce identi kac polozek a de nic jejich typu vytva r de nici formatu zaznamu, tj. typ zaznamu zaznamy mohou mt pevnou delku (a pevnou skladbu polozek) zaznamy mohou mt promennou delku, pokud obsahuj polozky promenne delky nebo pokud maj promennou skladbu polozek (pak polozky mus byt explicitne pojmenovavan e) a delka zaznamu byv a explicitne vyjad rena Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
5
Databaze, soubor, zaznam, polozka (atribut) 2
soubor (file) je pojmenovana kolekce zaznam u formujc nejakou relaci nebo prostor odpovdajc nejake trde X soubor je kolekc podobnych, souvisejcch zaznam u X neformaln e { soubor je kolekc dat umstenych
na energeticky nezavisl e pameti (disku, pasce, SSD, . . . ) X soubor mu ze byt manipulacn jednotkou stejne jako zaznam (atributy byvaj manipulacn jednotkou pouze na urovni aplikace, prpadne lze pomoc hodnot atributu vyhledavat zaznamy v souboru, resp. zaznamy v souboru usporad avat podle hodnot atributu) X soubory s jednotnou, deklarovatelnou strukturou zaznam u nazyv ame homogenn soubory X Soubory, ktere nejsou homogenn, obsahuj zaznamy promenneho, nejednotneho, nedeklarovatelneho typu
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
6
Soubory a vnejs pameti 2
soubory se dlouhodobe uchovavaj v energeticky nezavisl ych vnejsch pametch X zobrazuj se do bloku/aloka cnch bloku/fyzick ych stranek/sektor u/ ... X blok vnejs pameti mu ze obsahovat prav e jeden zaznam,
mu ze obsahovat vce zaznam u, prp. zaznam mu ze byt uchovavan y ve vce blocch vnejs pameti X pro aplikacn manipulace s daty mus byt prstupne soubory jako celky { to r es adresa rove sluzby system u souboru { jsou implementovane vesmes jako sluzby operacnho systemu X pro aplikacn manipulace s daty mus byt rovnez (efektivne) prstupne zaznamy souboru { to r es (standardizovane prp. proprietarn ) organizace souboru { typicky jsou implementovane jako knihovn sluzby vyuzvajc bazov e sluzby poskytovane operacnm systemem Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
7
Dotaz 2
Prstupnen jisteho zaznamu souboru se r es dotazem typu udany vy ctem hodnot atributu / "kde je zaznam poradm v souboru . . . ?\
2
pro efektivn r esen dotazu nad soubory a modi kac souboru se soubory doplnuj { indexy, resp. indexovymi strukturami, nebo { algoritmickymi postupy (hasovan ), umoznuj cmi efektivn r esen dotazu nad soubory a/nebo navazujcch modi kac souboru
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
8
System souboru, File System 2
sestava sluzeb pro manipulaci se soubory X poskytovane operacnm systemem prpadne systemov ymi programy
2
System souboru mus (typicke pozadavky) X umoznit uzivatelum/proces um manipulaci s daty na vnejsch pametech
X X X X
{ kazdy u/p mu ze vytva ret/rusit/cst/modi kovat/. . . soubory { kazdy u/p mu ze r zenym zpusobem zprstupnovat soubory jinych u/p { kazdy u/p mu ze r dit povolene prstupy k jeho souborum { kazdy u/p mu ze restrukturalizovat sve soubory, presunovat mezi nimi data, . . . { kazdy u/p mu ze sva data zalohovat a obnovovat po poruse { kazdy u/p mu ze identi kovat sve soubory svymi symbolickymi jmeny zajist'ovat, z e data v souborech jsou validn, eliminovat ztratu dat optimalizovat vykon sluzeb z hlediska jak systemu tak i aplikac podporovat na ruzn ych typech zarzen de novane API umoznit soubez nou c innost vce uzivatelu / aplikac Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
9
Prehled bazov ych problem u souborovych struktur 2
cl navrhu souborovych struktur X minimalizace doby prstupu do sekundarn pameti (disk), tj.
minimalizace poctu prstupu na disk { idealem je 1 prstup / 1 operaci se zaznamem { clem je seskupen informac takovym zpusobem, z e bude pravdepodobne, z e zskame vse co potrebujeme jedinym nebo nekolika malo mstne lokalizovanymi prstupy na disk bez ohledu na rozsah, velikost souboru
2
Staticke × dynamicke soubory X cl navrhu souborovych struktur je relativne snadno dosazitelny,
pokud soubory jsou staticke, nemen svuj obsah X dosazen cle navrhu souborovych struktur je podstatne obtz nejs, pokud jsou soubory dynamicke, tj. { dochaz k doplnov an , modi kaci a odstranov an dat (zaznam u) v souboru Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
10
Co vlastne soubor obsahuje? 2
v tomto predmetu studovany problem { jak jsou data organizovana ? X popis atributu / struktury je ulozen obvykle v adresa rove polozce
de nujc existenci souboru
2
v tomto predmetu nestudovany problem { co soubor vlastne obsahuje ? X popis dat {
{ implicitn { predpoklad a se, z e aplikace/uzivatel data zna { metadata { uvedena typicky v zahlav souboru, { c asto pro danou trdu aplikac standardizovana, { techniky: klc ova slova, prznaky, . . . { napr. TIFF, Target Image File Format
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
11
Historie { disky, indexy, stromy 2
pravek (50. { 60. leta XX. stolet) X soubory jen na pask ach ⇒ pouze sekvencn prstup X cena prstupu byla linearn e zavisl a na rozmeru souboru
2
Objev disku (60. { 70. leta XX. stolet) X moznost nesekvencnho, prmeho prstupu k zaznam um X algoritmickym vypo ctem { hasovan m : adresa-zaznamu-na-disku = F (hodnota-kl´ıcˇ ov´e-poloˇzky) ´ X pomoc indexu tvorenych dvojicemi {hodnota-kl´ıcˇ ov´e-poloˇzky, adresa-zaznamu-na-disku} ´
{ puvodn e ukladan ych do sekvencne prochazen ych struktur (tabulek) { posleze objev pouzitelnosti stromu pro implementaci indexu moznost zmeny omezen doby hledan zaznamu linearn funkc na omezen logaritmickou funkc poctu zaznam u v souboru Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
12
Historie { disky, indexy, stromy Objev pouzitelnosti stromu pro implementaci indexu 2
2 2
rozsahl e indexy ulozene v sekvencne organizovanych strukturach se prohledavaj sekvencne { tj. dlouho, neefektivne jiz v 60.letech XX. stolet se objevila idea manipulovat s indexy pomoc stromovych struktur dobra myslenka mela ale nedostatky: { stromy mohou pri pridav an a rusen zaznam u do/v souboru rust velmi nevyva zene { pro operaci nalezen zaznam u je pak potreba mnoho prstupu na disk a hledan pak trva neum erne dlouho Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
13
Historie { disky, indexy, stromy 2
AVL stromy X 1963, objev jak umravnit rust stromu
udrzenm (skoro) shodnych delek vetv (vyva zenost) X vhodne pro RAM, ne pro disky X v uzlu AVL stromu mu ze byt 1 zaznam a ne tucty c i stovky zaznam u X AVL strom roste shora dolu { slozita reorganizace pri vyvazovan stromu 2
B-stromy X 70. leta XX. stolet, dodnes hodne pouzvana technika X zavislost doby prstupu je O(logk N ), N { pocet zaznam u v souboru, k arita uzlu B-stromu X lze nalezt 1 zaznam mezi miliony zaznam u 3 az 4 prstupy na disk X B-strom roste zdola nahoru {
jednoduss reorganizace pri vyvazovan stromu Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
14
Historie { hasovan na vnejsch pametech 2
(staticke) hasovan X velmi stara technika znam a od dob navrhu prvnch prekladacu
(ty ale r esily hasovan v RAM pameti { prace s tabulkou identi kator u) X omezen na 3 { 4 prstupy na disk / 1 operaci je dobry vysledek X clem je vsak 1 prstup na disk / 1 operaci X tento cl lze pomoc hasovan dosahnout relativne snadno pro staticke, tj. ,,tem er xn"soubory 2
dynamicke hasovan X technika z konce 80. a 90. let XX. stolet X zarucuje 1 { 2 prstupy na disk / 1 operaci bez ohledu na to,
jak se men pocet zaznam u v souboru
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
15
Zpracovan dat ulozenych v souborech po zaznamech 2 2
Aplikace si uchovavaj logicky souvisejc data na vnejs pameti organizovane po souborech Aplikace si zprstupnuj data uchovavan e v souborech po zaznamech X informace o osobe, predmetu, oddelen, . . . X po te, co si aplikace zprstupn zaznam, mu ze opravit hodnotu
jisteho atributu operacemi na urovni procesoru a hlavn pameti a zaznam zpetne zapsat na vnejs pamet' X dlc atributy na disku si aplikace nezprstupnuje izolovane
2
zaznam =
X mnozina polozek, ktere spolu souvis, polozka { atribut, vlastnost X jde o logickou notaci v souborove strukture X c asto plat zaznam ≈ datovy objekt a zapis / c ten zaznamu ≈ uklid / obnova datoveho objektu Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
16
Zaznamy pevne / promenne delky 2
metody vyclenov an zaznam u v souboru / polozek v zaznamu X implicitn ( xn) delka zaznam u { neuvad ej se oddelovace zaznam u X variabiln delka zaznamu se vyjadruje:
{ explicitne, hodnotou udanou napr. na pocatku zaznamu, { oddelovacem na konci zaznamu, { ukazatelem na zaznam v primarn ho souboru s aplikacnmi daty ulozenym v nejakem sekundarn m souboru (v indexu) X xn struktura polozek { neuvad ej se oddelovace polozek v zaznamu X variabiln delka polozky se vyjadruje: { explicitne, hodnotou udanou napr. na pocatku polozky, { oddelovacem na konci polozky, 2
prace s promennymi delkami zvysuje pamet'ovou naro cnost Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
17
Zaznamy pevne / promenne delky
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
18
Proc se pouzva promenna delka zaznam u ? 2
obsahuj polozky promenne delky ... X PR I JMENI , BYDLIS TE,
2
nektera polozka se v zaznamu vcekrat opakuje X zaznam obsahuje seznam hodnot
2 2
nektera polozka v zaznamu je deklarovana jako volitelna soubor obsahuje zaznamy, jejichz polozkami mohou byt zaznamy X tzv. clustered records, mixed file
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
19
Terminologicke poznamky 2
zaznam = kolekce atributu (polozek) charakterizujcch jisty objekt X logicky zaznam {
kolekce hodnot atributu vytva rejcch zaznam X fyzicky zaznam { ma delku R kolekce hodnot atributu vytva rejcch zaznam (tj. logicky zaznam) + de nice delek atributu, oddelovace atributu, ... 2
De nice delek atributu X atributy konstantn delky { ta obvykle byv a implicitn X atributy promenne delky {
{ nede novane delky, delka je vymezena oddelovacem { de novane delky, vyjadrovane explicitne (pocet bitu/po cet bytu)
2 pamet'ovy prostor pro zobrazen zaznamu ve vnejs pameti { blok 2 pamet'ovy prostor pro zobrazen atributu ve vnejs pameti { pole Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
20
Blokovan zaznam u 2
blok vnejs pameti nebo take fyzicka stranka vnejs pameti X samostatne manipulovatelna, resp. adresovatelna datova jednotka X je predmetem I/O prenosu podporovanych OS a provad enych jako celek, ma delku B
2
Vztah zaznam { blok X neblokovany zaznam { blok obsahuje prav e jeden (fyzicky) zaznam
{ smyslem je jednoducha manipulace { 1 IO operace / 1 zaznam X blokovane zaznamy { blok obsahuje/,,blokuje"celistvy pocet zaznam u, blokovac faktor b = bB/Rc, kde R je delka zaznamu kde bξc znac nejvyss cele c slo ≤ ξ { clem je efektivita vyuzvan pamet'oveho prostoru X prerostle zaznamy { fyzicke zaznamy jsou zapisovane do bloku bez ohledu na hranice bloku ve vnejs pameti { c aste r esen pro soubory se zaznamy promenne delky, napr. zdrojove textove soubory, . . . Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
21
Blokovane a prerostle zaznamy
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
22
Soubor, homogenn soubor, nehomogenn soubor 2
soubor { identi kovatelna kolekce logicky souvisejcch zaznam u X v souboru mohou byt i totozne zaznamy
2
homogenn soubor X hodnoty polozek jeho zaznam u jsou primitivn (nestrukturovane) typy X je deklarovatelny formou S(A1 : D1, . . . , An : Dn), (jm´eno-atributu:dom´ena-hodnot)
tj. obsahuje zaznamy jednoho typu
2
nehomogenn soubor X hodnoty polozek jeho zaznam u nejsou primitivn typy nebo X zaznamy nejsou jednoho typu X nehomogenn soubory nejsou predmetem studia v PV062 Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
23
Klc 2
klc , key { c ast zaznamu, polozka(y), identi kujc zaznam X kdyz hledame konkretn zaznam,
mnohdy identi kujeme hledany zaznam jeho obsahem nikoli poradm v souboru
2
2 2
klc souboru, kj , je mnozina atributu Aj1, . . . Ajm, m je pocet atributu zahrnutych do klc e kj , m ≤ n, n je pocet atributu zaznamu mnozina klc u souboru { vsechny mozne klc e souboru homogenn soubor S lze chapat jako klc ovy typ
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
24
Klc 2
primarn klc identi kuje zaznam jedinecne X pokud se jako primarn klc vol jeden klc z mnoziny klc u souboru,
mus jeho atributy svymi hodnotami identi kovat jednotlive zaznamy jednoznacne { soubor mus byt mnozina X v idealn m prpade, by primarn klc nemel obsahovat aplikacne zavisl a data { mel by byt tzv. dataless key 2
sekundarn klc , resp. vyhledavac klc nebo take pomocny klc X jeden klc z mnoziny vsech klc u souboru X sekundarn klc nemus zaznam identi kovat jednoznacne
2
Typy klc u X hodnotovy { nabyv a hodnoty z domen atributu, ktere ho tvor X hasovany { algoritmicka transformace hodnotoveho klc e X relativn { pozice zaznamu vzhledem k pocatku souboru Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
25
Operace se souborem Soubor chapan y jako abstraktn datovy typ, ADT 2 konstruktory / destruktor { vytvoren / zrusen souboru X CREATE, BUILD, REMOVE 2
modi katory { aktualizace souboru X vlozen zaznamu { INSERT, (PUT) X rusen zaznamu { DELETE X modi kace polozek zaznamu { UPDATE, (WRITE), (MODIFY)
2
inspektory { zskan zaznamu ze souboru X ze souboru do vnitrn pameti { READ, (FETCH), (GET) X dotaz { QUERY, (FIND) X generovan zpravy { LIST
2
udr zba souboru X restrukturalizace, reorganizace { REORGANIZATION, OPEN, CLOSE Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
26
Dotaz nad souborem 2 2 2
totaln vycslitelna funkce de novana na universu souboru prklad: odpovˇed’ = FETCH (soubor, kl´ıcˇ ) odpoved' = zaznam nebo kolekce zaznam u jednorozmerny dotaz X jednoatributovy klc
2
Trdy vcerozmernych (ortogonaln´ ´ ıch) dotazu X na uplnou shodu { zadano vsech n atributu X na c aste cnou shodu { zadano s ≤ n atributu X na uplnou intervalovou shodu { zadano vsech n atributu
{ pro kazdy atribut je dan interval moznych hodnot X na c aste cnou intervalovou shodu { zadano s ≤ n atributu { pro kazdy atribut je dan interval moznych hodnot Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
27
Model, schema organizace souboru 2
Hierarchicka abstrakce organizace souboru ve 3 urovn ch X C´ıl { umoznit optimaln e r esit operace nad zaznamy souboru
nezavisle na konkretn m fyzickem zarzen vnejs pameti
2
Logicke schema X ex. hypoteticka logicka pamet' se strukturou optimalizovanou tak,
aby umoznila efektivn r esen operac nad zaznamy X logicka pamet' se c len na logicke stranky, LS, ty mohou byt usporadan e sekvencne, hierarchicky, . . . X logicka pamet' obsahuje { jednak primarn soubor { aplikacn data { jednak sekundarn (pomocne) soubory { indexy, rejstrky, . . . X zaznamy primarn ho souboru i sekundarn ch souboru mohou byt v logickych strank ach blokovane (vce zaznam u v 1 LS) { blokovac faktor, resp. faktor naplnen (logicke) stranky: λ = skutecny pocet zaznam u v LS / mozny pocet zaznam u v LS Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
28
Model, schemata organizace souboru 2
Logicke schema, pokracovan X c´ıl { poskytnout takovou pamet'ovou strukturu, ktera umozn
minimalizovat pocet operac provad enych pri manipulacch (insert, delete, search, . . . ) se zaznamy souboru umstenymi v logickych strank ach X popis na urovni typu { { vztahy mezi logickymi strankami { vnitrn struktura logicke stranky { algoritmy operac s logickymi strankami pri zprstupnov an dat a pri udr zbe jejich struktury, { operace s logickymi strankami { s tepen stranky, slev an stranek { stanoven mez faktoru naplnen logicke stranky, ...
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
29
Logicke schema organizace souboru
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
30
Fyzicke schema organizace souboru 2
Fyzicke schema X zobrazen logickych stranek do fyzickych stranek konkretn ho,
pouziteho typu vnejs pameti
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
31
Logicke a fyzicke schema organizace souboru
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
32
Implementacn schema organizace souboru 2
Implementacn schema X rozmsten, alokace fyzickych stranek v pouzitem zarzen X u klasickych organizac souboru implementovanych
na sdlenych discch standardne r es OS nezavisle na aplikacch X aplikace r es ve vyjime cnych prpadech na dedikovanych discch 2
slozitost schematu organizace souboru X prostorova { potrebny objem fyzickych stranek pro zobrazen souboru X c asova { pocet V/V operac s fyzickymi strankami
pro jednotlive operace s logickymi strankami { pocet nactanych fyzickych stranek (do RAM) { pocet zapisovanych fyzickych stranek (do zarzen)
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
33
Model, schemata organizace souboru
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
34
Model, schemata organizace souboru
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
35
Klasi kace souborovych organizac 2
Souborova organizace se sekvencnm prstupem k zaznam um X aplikovatelna na pasce, na disku X slozitost dotazu { prstupu k zaznamu s udanym klc em { je linearn , O(N ), X slozitost dotazu { prstupu k zaznamu s udanym klc em {
v prpade pouzit binarn ho hledan v setrdenem souboru podle vyhledavac ho klc e, je logaritmicka, O(log2 N )
2
Souborova organizace s prmym prstupem k zaznam um X aplikovatelna na disku X urcen msta se zaznamem lze dosahnout pomoc indexu X urcen msta se zaznamem lze dosahnout pomoc hasovan
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
36
Souborova organizace s prmym prstupem k zaznam um 2
s urcenm msta se zaznamem pomoc indexu X index { sekvencn struktura usporad an ukazatelu na zaznamy { tabulka/pole/seznam dvojic {kl´ıcˇ , ukazatel na zaznam} ) ´
{ slozitost pruchodu takovym indexem je linearn az logaritmicka (pri pouzit binarn ho hledan v setrdenem indexu podle klc u) X index { stromova struktura usporad an ukazatelu na zaznamy { vyva zene (balanced) stromy, B stromy / B+ stromy, { slozitost logk N , k >> 2, i pro dynamicke soubory, { B stromy { ztrata moznosti sekvencnho prstupu { B+ stromy umoznuj i sekvencn prstup, 2
s urcenm msta se zaznamem pomoc hasovan X algoritmickym odvozenm ukazatele zaznamu z hodnoty klc e X konstantn slozitost Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
37
Operace se zaznamy pevne delky { ulozen zaznamu i Zaznam i se uloz pocnaje bytem n × (i − 1), kde n je rozmer zaznamu { prstup k zaznam um po kroku n, trivialn operace, pokud hranice zaznam u sleduj hranice bloku { rusen zaznamu i, alternativy: a) presun zaznam u i + 1, . . . , m do mst i, . . . , m − 1 b) presun zaznamu m do msta i c) nic se nepresouva, volna msta se r etez do seznamu volnych mst Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
38
Zaznamy pevne delky, r etezen zaznam u 2
rusen zaznamu { pouzit seznamu volnych mst
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
39
Zaznamy promenne delky 2
prklad reprezentace zaznam u promenne delky v souboru se zaznamy s nasobn e opakovanymi polozkami X na konci kazdeho zaznamu se uvede oddelovac (rdic znak, jedinecny bitovy vzorek, . . . ) End-Of-Record (⊥) X obtz ne rusen a doplnov an zaznam u
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
40
Zaznamy promenne delky 2
reprezentace zaznam u promenne delky kapsou zaznam u v bloku (slotted page, slotted block) X blok = zahlav´ ı, voln´e m´ısto, zaznamy ´ ´ X zahlav = poˇcet zaznam u˚ v kapse, ukazatel na konec voln´eho m´ısta, ´ ukazatel a d´elka kaˇzd´eho zaznamu ´ X volne msto se udrzuje souvisle X ukazatele v adresa ri neukazuj prmo na zaznam,
ukazuj na ukazatel zaznamu v zahlav kapsy
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
41
Zaznamy promenne delky 2
reprezentace zaznam u promenne delky pomoc rezervovaneho prostoru X modul = prostor pro zaznam se znamou maximaln delkou X nevyuzity prostor lze vyplnit symbolem null nebo End-Of-Record
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
42
Zaznamy promenne delky 2
reprezentace zaznam u promenne delky pomoc ukazatelu X zaznam promenne delky je reprezentovan
seznamem generickych zaznam u pevne delky r etezenych ukazateli X vyhoda { pouzitelne i pri neznalosti maximaln delky zaznamu
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
43
Zaznamy promenne delky 2
nedostatek pouzit ukazatelu v predchozm prkladu
X uchovavaj se prazdn e, nevyuzitelne prostory X r esen { 2 typy bloku, kotva, anchor { obsahuje 1. zaznamy r etezcu, pretoky, overflow { obsahuje ostatn zaznamy r etezcu
Jan Staudek, FI MU Brno
|
PV 062, Souborove systemy { organizace
44