Soubor, souborov e organizace

Osnova predna sky 2

Soubor, souborove organizace

2 2

PV 062 Organizace souboru

2

Pojem souboru Model, schema organizace souboru Dotaz nad souborem Klasi kace souborovych organizac

Jan Staudek http://www. .muni.cz/usr/staudek/vyuka/

}

w A| y < 5 4 23 1 0 / -. , )+ ( %&' $ # !"

Æ

Verze : jaro 2017 Jan Staudek, FI MU Brno

2

2

2

Pro dlouhodobe a na energii nezavisl e uchovav an dat v poctaci slouz pamet'ove zarzen typu vnejs (sekundarn , terciarn ) pamet' (disk, paska, ...) Data ulozena na vnejsch pametech jsou reprezentac jedne ze trd zdroju tvorcch vypo cetn system ktery r es aplikacn ulohy Abstrakce zdroju srozumitelne aplikacm a sluzby pro manipulaci a zprstupnov an techto zdroju poskytuje svymi funkcemi operacn system zakladn nastroj dostupny aplikacnm uloh am pro poskytovan informacnch sluzeb pro dlouhodobe uchovav an a zprstupnov an dat na vnejsch pametech { databaze Jan Staudek, FI MU Brno

|

PV 062, Souborove systemy { organizace


1

Soubor { pojem, imaginace

Soubor { pojem, imaginace 2

|

2

2

databaze = kolekce souvisejcch dat X Vztahy mezi elementy dat v databazi jsou explicitn X Databaze je navrhovana pro pouzit aplikacnmy systemy X Databaze se v poctaci (na vnejsch pametech) uchovavaj jako kolekce pojmenovanych mnozin dat { souboru, (file).

Soubor je dominantn datovou jednotkou na vnejsch pameti z pohledu aplikac, je pojmenovanou kolekc dat ulozenou na vnejs pameti. Soubory byvaj vnitrne strukturovany na { zaznamy, records, zaznamy byvaj vnitrne strukturovany na vlastnosti (atributy, polozky), attributes 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 Jan Staudek, FI MU Brno

|


3

Databaze, soubor, zaznam, polozka (atribut)

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 X atribut mu ze byt nepojmenovany, identi kovatelny svym umstenm v zaznamu Jan Staudek, FI MU Brno

|


4

Jan Staudek, FI MU Brno

Databaze, soubor, zaznam, polozka (atribut) 2

2

X zaznam tvor kolekce polozek (atributu)

X X X

|


5

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

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


Databaze, soubor, zaznam, polozka (atribut)

datova jednotka reprezentujc objekt zpracovavan y aplikac (osoba, mstnost, predmet, . . . ) je zaznam (redord) X X

|

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

6


|


7

Soubor, system souboru { pojem, imaginace

Soubor, system souboru { pojem, imaginace 2 2

Koncept souboru je velmi volny Z pohledu aplikac/uzivatelu je soubor nejmensm pridelovatelnym dlem logickeho prostoru vnejs pameti

2

X data lze zapsat do vnejs pameti pouze

2

X vyznam stavebnch elementu de nuje tvurce / uzivatel souboru

kdyz jsou soucast nektereho souboru

2

X X X X X X

fotogra e, . . .

Soubory mohou byt formatov any X volne { napr. textove soubory (znaky, r adky, prp. stranky) X prsne, rigidne { soubory s vnucenou vnitrn indexacn strukturou, . . . Jan Staudek, FI MU Brno

|



2

X X


9

ri pojmy charakterizujc strukturu souboru jsou Cty X Pole, Field { elementarn datova jednotka (jmeno, vek, . . . )

obsahuje jednu hodnotu, mu ze mt pevnou nebo promennou delku X Zaznam, Record { strukturovana jednotka (udaje o osobe, . . . ) kolekce pol, aplikacemi povazovana za jeden strukturovany celek, mu ze mt pevnou nebo promennou delku a/nebo strukturu X Soubor, File { pojmenovana kolekce prbuznych zaznam u (zamestnanci) manipulovatelna jako jednotka, predmet r zen prstupu X Baze dat, Database { kolekce vzajemn e explicitne souvisejcch dat, sestavaj c z jednoho nebo prpadne i vce souboru (instituce)

X soubory maj byt uchovavan e dlouhodobe,

X

|

Soubor, system souboru { pojem, imaginace

existuje rozdl mezi souborem a datovou strukturou v operacn pameti ? ANO:

X X

jeho umsten ve strukture souboru Delete { odstranen souboru, resp. c asti souboru (zaznamu) Open { zprstupnen souboru Close { zrusen prstupove vazby se souborem Read { c ten c asti zprstupneneho souboru (zaznamu) Write { modi kace c asti zprstupneneho souboru (zaznamu) Dir { vypis seznamu souboru z adresa re systemu souboru . . .

8

Soubor, system souboru { pojem, imaginace 2

Operacn system svoj funkcn soucast zvanou system souboru poskytuje sluzby operujc se soubory, napr. X Create { vytvoren noveho souboru a

Soubory mohou obsahovat X programy { ve zdrojovych i clovych (binarn ch) formach X data { numericka, alfabeticka, alfanumericka, obrazova, video, hudba,

2

Soubory mohou byt tvoreny posloupnostmi bitu, bytu, r adk u, zaznam u

nezavisle na dodavce energie soubory maj byt premstitelne/kop rovatelne z msta na jine msto soubory mohou byt dostupne vce procesum a uzivatelum a ti je mohou sdlet doba existence souboru je nezavisl a na dobe existence procesu, ktery jej vytvoril soubory jsou chapan e c asto jako vstupy aplikacnch system u ...

2

Vsechny systemy souboru nemus strukturalizaci podporovat X bazov y system souboru v unixovych systemech chape soubor jako

posloupnost bytu


|


10


|


11

Soubory a vnejs pameti

Soubor, system souboru { pojem, imaginace 2

logicky pohled na soubor (pohled programatora){ jak data v souboru vid uzivatel (aplikacn system)

2

X zobrazuj se do bloku/aloka cnch bloku/fyzick ych stranek/sektor u/ ... X blok vnejs pameti mu ze obsahovat prav e jeden zaznam,

X logickou strukturu vlastnch (primarn ch) dat v souboru mu ze

doprovazet sestava pomocnych (sekundarn ch) dat r escch napr. indexovany prstup k zaznam um X manipulacn jednotky jsou zaznamy, soubory, baze dat, adresa re, . . . 2

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

fyzicky pohled na soubor (pohled OS) { co a jak je ve skutecnosti ulozene na disku X implementace logicke struktury na konkretn e pouzite zarzen X manipulacn jednotky (na disku) jsou bloky, stopy, valce, svazky, . . .


|


12


System souboru, File System 2

sestava sluzeb pro manipulaci se soubory

2

{ 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 |


13

cl navrhu souborovych struktur 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

X umoznit uzivatelum/proces um manipulaci s daty na vnejsch pametech



X minimalizace doby prstupu do sekundarn pameti (disk), tj.

System souboru mus (typicke pozadavky)

X X X X

|

Prehled bazov ych problem u souborovych struktur

X poskytovane operacnm systemem prpadne systemov ymi programy 2

soubory se dlouhodobe uchovavaj v energeticky nezavisl ych vnejsch pametch

14

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

|


15

Zprstupnov an dat organizovanych v souborech

Co vlastne soubor obsahuje? 2

v tomto predmetu studovany problem { jak jsou data organizovana ?

2

X soubory na pask ach ⇒ pouze sekvencn prstup k zaznam um souboru X cena prstupu byla linearn e zavisl a na rozmeru souboru

X popis atributu / struktury je ulozen obvykle v adresa rove polozce

de nujc existenci souboru

2

2

v tomto predmetu nestudovany problem { co soubor vlastne obsahuje ? { 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

|


{ 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

16



2 2

2

2

B stromy

B+ stromy X varianta B stromu umoznuj c prmy prstup kombinovat

se sekvencnm prstupem

{ pro operaci nalezen zaznam u je pak potreba mnoho prstupu na disk a hledan pak trva neum erne dlouho PV 062, Souborove systemy { organizace

17

jednoduss reorganizace pri vyvazovan stromu

{ stromy mohou pri pridav an a rusen zaznam u do/v souboru rust velmi nevyva zene

|


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 {

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:


|


Objev pouzitelnosti stromu pro implementaci indexu 2

Objev disku (60. { 70. leta XX. stolet) X moznost nesekvencnho, prmeho prstupu k zaznam um souboru X prmy prstup algoritmickym vypo ctem { hasovan m : adresa-zaznamu-na-disku = F (hodnota-kl´ıcˇ ové-poloˇzky) ´ X prmy prstup pomoc indexu tvorenych dvojicemi {hodnota-kl´ıcˇ ové-poloˇzky, adresa-zaznamu-na-disku} ´

X popis dat {


pravek (50. { 60. leta XX. stolet)

18


|


19

Zpracovan dat ulozenych v souborech po zaznamech

Zprstupnov an dat organizovanych v souborech 2

(staticke) hasovan

2

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

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

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,

2

jak se men pocet zaznam u v souboru


|


20

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

|


21

Zaznamy pevne / promenne delky

Zaznamy pevne / promenne delky 2

2

Aplikace si uchovavaj logicky souvisejc data na vnejs pameti organizovane po souborech Aplikace si zprstupnuj data uchovavan e v souborech po zaznamech

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

|


22


|


23

Terminologicke poznamky

Proc se pouzva promenna delka zaznam u ? 2

obsahuj polozky promenne delky

2

... X PR I JMENI , BYDLIS TE, 2

X logicky zaznam {

kolekce hodnot atributu vytva rejcch zaznam

nektera polozka se v zaznamu vcekrat opakuje

X fyzicky zaznam { ma delku R

X zaznam obsahuje seznam hodnot 2 2

zaznam = kolekce atributu (polozek) charakterizujcch jisty objekt

kolekce hodnot atributu vytva rejcch zaznam (tj. logicky zaznam) + de nice delek atributu, oddelovace atributu, ...

nektera polozka v zaznamu je deklarovana jako volitelna soubor obsahuje zaznamy, jejichz polozkami mohou byt zaznamy

2

De nice delek atributu X atributy konstantn delky { ta obvykle byv a implicitn X atributy promenne delky {

X tzv. clustered records, mixed file

{ 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

|



24

Blokovan zaznam u 2 2

X 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 X jeden nebo vce sektoru na disku, blok na magneticke pasce, ... X na disku vesmes pevne delky X prenos do hlavn pameti typicky pomoc DMA X vets bloky urychluj I/O prenosy, spravu vyr. pamet c in slozitejs

|


25

Blokovan zaznam u

Zaznam { manipulacn jednotka dat z pohledu aplikace pracujc se soubory strukturovanymi do zaznam u Blok { manipulacn jednotka dat z pohledu I/O se sekundarn pamet


|


26

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 preklenovane (separovane) 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, . . .


|


27

Blokovan zaznam u

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éno-atributu:doména-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


|


28


Klc 2

klc , key { c ast zaznamu, polozka(y), identi kujc zaznam

2

2

Typy klc u


sekundarn klc , resp. vyhledavac klc nebo take pomocny klc X jeden klc z mnoziny vsech de novanych klc u souboru X sekundarn klc nemus zaznam identi kovat jednoznacne

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

|

primarn klc identi kuje zaznam jedinecne 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

klc souboru, kj , je mnozina atributu Aj1, . . . Ajm, m je pocet atributu zahrnutych do klc e kj , m ≤ n, n je pocet atributu zaznamu


29

X pokud se jako primarn klc vol jeden klc z mnoziny klc u souboru,

mnohdy identi kujeme hledany zaznam jeho obsahem nikoli poradm v souboru

2


Primarn x sekundarn lc

X kdyz hledame konkretn zaznam,

2

|

30


|


31

Operace se souborem

Dotaz nad souborem

Soubor chapan y jako abstraktn datovy typ, ADT 2 konstruktory / destruktor { vytvoren / zrusen souboru

2

Prstupnen jisteho zaznamu souboru se r es dotazem typu

2

pro efektivn r esen dotazu nad soubory a modi kac souboru se soubory doplnuj { indexy, resp. indexovymi strukturami, nebo { algoritmickymi postupy (hasovan m), umoznuj cmi efektivn r esen dotazu nad soubory a/nebo navazujcch modi kac 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

udany vy ctem hodnot atributu / "kde je zaznam poradm v souboru . . . ?\

udr zba souboru

X restrukturalizace, reorganizace { REORGANIZATION, OPEN, CLOSE Jan Staudek, FI MU Brno

|


32


2 2 2


33

Model, schema organizace souboru

Dotaz nad souborem 2

|

totaln vycslitelna funkce de novana na universu souboru prklad: odpovˇed’ = FETCH (soubor, kl´ıcˇ ) odpoved' = zaznam nebo kolekce zaznam u jednorozmerny dotaz

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

X jednoatributovy klc

Logicke schema X ex. hypoteticka logicka pamet' se strukturou optimalizovanou tak,

aby umoznila efektivn r esen operac nad zaznamy

Trdy vcerozmernych (ortogonaln´ ´ ıch) dotazu

X logicka pamet' se c len na logicke stranky, LS,

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

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

{ 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

|


34


|


35

Logicke schema organizace souboru

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, ...


|


36

|


37

Logicke a fyzicke schema organizace souboru

Fyzicke schema organizace souboru 2


Fyzicke schema X zobrazen logickych stranek do fyzickych stranek konkretn ho,

pouziteho typu vnejs pameti


|


38


|


39

Model, schemata organizace souboru

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)


|



40

Model, schemata organizace souboru

|


41

Typy souboru 2

typy souboru { podle obsazenych dat v souboru X numericka, textova, binarn , . . . data X program (binarn data), ...

2


|


42

Obvykle typy souboru (typ lze mnohdy zahrnout jako prponu za ,,."ke jmenu)


|


43

Struktura (organizace) souboru

Typy souboru 2 2 2 2 2 2

clovy typ souboru ma smysl deklarovat (podporovat) pro primarn soubor dat typy se typicky deklaruj prponou oddelenou teckou od jmena (.txt, .xls, .doc, . . . , .exe, . . . ) udrzuj se takto textove, binarn , . . . soubory, soubory konkretn ch aplikac (Excel, Word, . . . ) S typem souboru mu ze byt svazan y relevantn program, ktery data v souboru zpracovav a vesmes kazdy OS de nuje, rozpoznav a soubory s interpretovatelnym programem (executable file format) rozpoznav an typu souboru na zaklad e uveden prpony nemus nutne podporovat OS, mu ze se jm r dit az aplikace Jan Staudek, FI MU Brno

|


2

X relativne volna { textova data v r adc ch, posloupnosti bytu, ... X rigidne formatovan a { zaznamy, indexy zaznam u, ... 2

{ r adky textu { strukturovane zaznamy (,,tabulky") pevne delky { strukturovane zaznamy promenne delky

2

X dosahuje se vklad an m vhodnych r dicch struktur a/nebo

poskytnutm komplexnch prstupovych funkc X formatovan e dokumenty

X Relocatable load files X soubory s indexy na bazi B + stromu, s hasovanymi indexy, . . . Jan Staudek, FI MU Brno

nestrukturovany soubor sprava souboru v OS velmi jednoducha aplikace mohou vnutit sve vlastn struktury uplatnuje UNIX, Windows, vetsina soudobych OS |


|


45

Struktura souboru, pohled OS

2


komplexn (az rigidn) organizace souboru

44

posloupnost bajtu X X X X

volna organizace souboru s jednoduchymi datovymi zaznamy X vesmes sekvencne uchovavan e

Struktura souboru, pohled OS

2

struktura (organizace) souboru mu ze byt

posloupnost zaznam u

X zaznam = kolekce pol bajtu zpracovavan a jako aplikacn jednotka

soubor = kolekce zaznam u

X system souboru poskytuje operace pro praci se zaznamy (read, write) X OS mu ze operace se zaznamy optimalizovat

(houpackove vyrovnav an , . . . )

46


|


47

Organizace souboru

Struktura souboru, pohled OS 2 2

2

X X X X X

strom zaznam u

2

X typicky struktura podporujc vyhledav an zaznamu v souboru X vyhledav an zaznam u je zalozeno na koncepci klc u,


|


minimalizace doby prstupu jednoduchost aktualizace minimalizace pamet'ove slozitosti jednoduchost udr zby spolehlivost

Vyznamnost kriteri vymezuje aplikace X pri davkov em zprstupnov an vsech zaznam u v souboru nehraje roli

minimalizace doby prstupu k jednotlivym zaznam um X pro soubor na CD-ROM nehraje roli jednoduchost aktualizace

de novanych polozek zaznam u, a vyhledavac ch stromu

48


Organizace souboru 2

Logicke strukturovan zaznam u v souboru vynucene zpusobem, kterym se k zaznam um pristupuje Volbu organizace souboru vhodne pro danou aplikaci mohou ovlivnovat kriteria:

|


49

Souborove organizace

Nektera kriteria mohou byt protichudn a

2

X minimalizace pamet'ove slozitosti ⇒ minimalizace redundance

Usporad an zaznam u v souboru s clem X optimaln ho zprstupnen zaznamu pro aplikaci

(at' se zaznam zprstupn tak rychle, jak je to jen mozne) X vkladac , modi kacn a rusc transakce na zaznamech maj byt rychle, jednoduche a nesm porusit ostatn zaznamy X vkladac , modi kacn a rusc transakce na zaznamech nesm zpusobit vznik duplicitnch zaznam u X zaznamy maj byt ulozeny efektivne, tak aby cena potrebne pameti byla minimaln

minimalizace doby prstupu { napr. duplikac dat, zvy sen redundance

2

Metod organizace je vce, jiste metody jsou vhodne pro jisty zpusob zprstupnov an zaznam u X Designer aplikace obvykle vol vhodnou metodu organizace


|


50


|


51

Organizace souboru, prstupove metody 2

Organizace souboru

Sekvencn prstup

2

X sekvencn c ten zaznamu po zaznamu, typicky od pocatku souboru X nelze ,,skakat"po souboru, lze prejt jen na zacatek nebo dals zaznam X vyhovujc organizace v dobach, kdy jedinym mediem byla mg paska,

X X X X X

dodnes nepominutelna organizace pro r adu aplikac (kompilace, . . . )

X pr. operac: read next, write next, reset nebo rewind 2

Forem organizac souboru je mnoho, 5 zakladn ch je

Prmy prstup, ,,libovolny"( random) prstup

hromada (pile, heap) sekvencn soubor (sequential file) indexovany sekvencn soubor (index-sequential file) indexovany soubor (indexed file) hasovany soubor (hashed file), resp. soubor s prmym prstupem (random access file)

X zaznamy lze zprstupnovat v libovolnem porad X vyznamn a organizace pro DBS X read n, write n, prp. seek n nasledovan e read next nebo write next, n { oset zaznamu, urcen zaznamu obsahem (klc em), . . . , 2

Ostatn organizace lze budovat nad temito 2 bazov ymi metodami Jan Staudek, FI MU Brno

|


52


Souborova organizace se sekvencnm prstupem k zaznam um

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

2

Souborova organizace vymezuje pouzitou prstupovou metodu podporovanou sluzbou systemu souboru Jan Staudek, FI MU Brno

|


s urcenm msta se zaznamem pomoc indexu { 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,

v prpade pouzit binarn ho hledan v setrdenem souboru podle vyhledavac ho klc e, je logaritmicka, O(log2 N )

2

53

X index { sekvencn struktura usporad an ukazatelu na zaznamy { tabulka/pole/seznam dvojic {kl´ıcˇ , ukazatel na zaznam} ) ´

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 {

2


Souborova organizace s prmym prstupem k zaznam um

Klasi kace souborovych organizac 2

|

54

s urcenm msta se zaznamem pomoc hasovan X algoritmickym odvozenm ukazatele zaznamu z hodnoty klc e X konstantn slozitost Jan Staudek, FI MU Brno

|


55

Prklady struktur organizac souboru


|


Prklady struktur organizac souboru

56


Charakteristicke vlastnosti organizac souboru

|


57

Hromada 2 2 2

Data se shromazd'uj v porad vlozen do souboru Zaznam ma formu davky dat Zaznam mu ze mt vce pol odlisne delky a i typu, X pole mus byt samoidenti kovatelne (jmeno + hodnota) X pole mus byt oddelena separatory nebo udav an m delky

2 2

Prstup k zaznam um { sekvencn hledan Aplikacn vyuzitelnost je mala X masa dat se typicky shroma zd a uloz pred zpracovan m X data se obvykle silne lis rozmerem a strukturou


|


58


|


59

Hromada 2 2

Sekvencn soubor

nehomogenn soubor mu ze obsahovat zaznamy promenne struktury

2

X uvad se i jmena atributu jako klc ova slova,

2

2

napr. vypis 3 variant obedu z jdelnho lstku: POLEVKA=milansk a; HLAVNI=stroganov; NAPOJ=pivo⊥ HLAVNI=halusky; NAPOJ=mleko ⊥ NAPOJ=gin⊥

2 2 2 2

2 2

sekvencn uklad an zaznam u ve vymezenem prostoru levna, jednoducha metoda pro masvn vklad an malych zaznam u do malych souboru slozitost vyhledan zaznamu, O(N ) nehomogennmi soubory se dale nezabyv ame Jan Staudek, FI MU Brno

|


2

60

Soubor se sekvencnm prstupem, sekvencn soubor

zaznamy maj z hlediska skladby z pol pevny format skladba pol v zaznamu je znam a a priori jmena a obory hodnot pol se oznacuj jako vlastnosti (zaznamu) vlastnosti pouzite pro vyhledan zaznamu se oznacuj pojmem klc pole obsahujc hodnoty, podle kterych se zaznamy vyhledavaj , klc e, jsou klc ova pole vyhledan zaznamu se standardne dela sekvencnm prohlz enm, zaznamy se vkladaj sekvencne


|


61

Soubor se sekvencnm prstupem, sekvencn soubor Simulace sekvencnho prstupu na souboru s prmym prstupem cp { current position, poradove c slo zaznamu

X sekvencn soubor je optimaln organizace pro davkov e zpracovan

vsech zaznam u v souboru X sekvencn soubor lze uchovavat v setrdenem usporad an podle klc e, coz zvysuje rezii vklad an a rusen zaznam u a prohlz et ho binarn m hledan m Jan Staudek, FI MU Brno

|


62


|


63

Indexovany soubor

Indexovany sekvencn soubor 2 2

Zaznamy sekvencnho souboru jsou usporadan e podle klc e Soubor je doplneny o

2

X index vymezujc skupiny zaznam u

2

2

s hodnotou klc e z udaneho intervalu X pretokovou oblast pro zaznamy doplnene do souboru po setrden 2

X soubor nen usporadan y, X predpoklad a se hledan podle vce klc u

Indexy mohou byt hierarchicke

2

X index sam je sekvencn soubor (dvojic hodnota, ukazatel) X k indexu lze vypracovat index (index vyss urovn e) 2

2

X sekvencne se prohlz oblast souboru vymezena indexem,

2

nikoli soubor cely

2 |


Soubor je doplneny o indexy, jeden pro kazdy typ dotazu X zaznamy se zprstupnuj pouze pres indexy

Optimalizuje se c as prstupu k zaznamu


zaznamy maj z hlediska skladby pol pevny format skladba pol zaznamu je znam a a priori zaznamy se shromazd'uj v porad vlozen do souboru

Optimaln organizace pro aplikace s kritickym faktorem doba prstupu, zaznamy se zprstupnuj jeden po druhem Index mu ze mt linearn (tabulkovou) strukturu Index mu ze mt hierarchickou strukturu, napr. B-strom

64


Indexovan zaznam u souboru, prklad

|


65

Hasovany soubor, soubor s prmym prstupem 2 2 2

zaznamy maj z hlediska skladby pol pevny format skladba pol zaznamu je znam a a priori zaznamy se shromazd'uj v porad vlozen do souboru X soubor nen usporadan y,

2 2 2


|


66

lokalizace hledaneho zaznamu se odvod algoritmicky, hasovac funkc se vstupnm parametrem { vyhledavac klc optimaln organizace pro aplikace s kritickym faktorem doba prstupu zaznamy se zprstupnuj jeden po druhem v porad danem aplikac


|


67

Operace se zaznamy pevne delky

Zaznamy pevne delky, r etezen zaznam u

{ 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

2

|


68


|


69

Zaznamy promenne delky

Zaznamy promenne delky 2

rusen zaznamu { pouzit seznamu volnych mst

2

prklad reprezentace zaznam u promenne delky v souboru se zaznamy s nasobn e opakovanymi polozkami

reprezentace zaznam u promenne delky kapsou zaznam u v bloku (slotted page, slotted block) X blok = zahlav´ ı, volné m´ısto, zaznamy ´ ´ X zahlav = poˇcet zaznam u˚ v kapse, ukazatel na konec volného m´ısta, ´ ukazatel a délka kaˇzdého zaznamu ´ X volne msto se udrzuje souvisle X ukazatele v adresa ri neukazuj prmo na zaznam,

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

ukazuj na ukazatel zaznamu v zahlav kapsy


|


70


|


71

Zaznamy promenne delky


2

reprezentace zaznam u promenne delky pomoc rezervovaneho prostoru

|


72


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


|


X zaznam promenne delky je reprezentovan

seznamem generickych zaznam u pevne delky r etezenych ukazateli X vyhoda { pouzitelne i pri neznalosti maximaln delky zaznamu

X modul = prostor pro zaznam se znamou maximaln delkou X nevyuzity prostor lze vyplnit symbolem null nebo End-Of-Record


reprezentace zaznam u promenne delky pomoc ukazatelu

74


|


73

Soubor, souborov e organizace

Recommend Documents