DBI007
Organizace a zpracov´ an´ı dat I Sloˇ zen´ a ´ uloˇ ziˇ stˇ e, z´ aznamy, soubory
ˇ emliˇ RNDr. Michal Z cka, Ph.D.
D˚ uleˇ zit´ a organizaˇ cn´ı pˇ ripomenut´ı
• Zkouˇ sku lze skl´ adat, i kdyˇ z jeˇ stˇ e nejsou splnˇ eny vˇ sechny podm´ınky pro z´ apoˇ cet.
• Zkouˇ ska je zaps´ ana aˇ z ve chv´ıli, kdy je splnˇ en i z´ apoˇ cet.
• Povinnosti je tˇ reba m´ıt splnˇ en´ e do l´ eta – v z´ aˇ r´ı nebudu.
Hierarchie pamˇ et´ı poˇ c´ıtaˇ ce V poˇ c´ıtaˇ c´ıch najdeme mnoho r˚ uzn´ ych pamˇ et´ı: + Registry − Vyrovn´ avac´ı pamˇ et’ procesoru – pamˇ et’ova cache + Operaˇ cn´ı pamˇ et’ − Vyrovn´ avac´ı pamˇ et’ pro disky – diskov´ a cache + Sekund´ an´ı pamˇ et’ (disky)
Hardware Magnetick´ e p´ asky Optick´ e disky Jukeboxy Magnetick´ e disky Flash pamˇ eti RAID-y
Magnetick´ a p´ aska • umoˇ zˇ nuje sekvenˇ cn´ı ˇ cten´ı i rychl´ e pˇ rev´ıjen´ı • existuj´ı speci´ aln´ı zaˇ r´ızen´ı pro kontrolu kvality z´ aznamu • aplikace: – z´ alohov´ an´ı – proudov´ a data – vz´ acnˇ eji pˇ ristupovan´ a rozs´ ahl´ a data (spolu s optick´ ymi disky) • Dlouhodob´ e uchov´ an´ı dat (des´ıtky let)
Magnetick´ y disk – pohled z boku osa
povrchy
hlavy
Hardware – probl´ emy Pohybliv´ a m´ edia mohou podl´ ehat r˚ uzn´ ym deformac´ım, a tak je tˇ reba pr˚ ubˇ eˇ znˇ e ”dolad’ovat” nastaven´ı ˇ ctec´ıch/z´ aznamov´ ych ˇ c´ ast´ı. Tato m´ edia mohou b´ yt i mechanicky poˇ skozena; mus´ı se to umˇ et zdetekovat, pˇ r´ıpadnˇ e (v pˇ r´ıpadˇ e menˇ s´ıho poˇ skozen´ı) i opravit.
Bloky – moˇ zn´ a implementace znaˇ cka zaˇ c´ atek bloku ˇ c´ıslo bloku na stopˇ e/p´ asce znaˇ cka zaˇ c´ atku dat vlastn´ı data znaˇ cka konce dat pomocn´ e k´ ody na detekeci chyb a pˇ r´ıpadn´ e opravy znaˇ cka konce bloku Samotn´ e bloky maj´ı mezi sebou mezery – jednak aby se stihl blok zpracovat, neˇ z se bude ˇ c´ıst dalˇ s´ı, jednak aby se pˇ r´ıpadn´ ym nepˇ resn´ ym um´ıstˇ en´ım bloku nepˇ repsal blok sousedn´ı
Diskov´ a pole – RAID • Redundant Array of Inexpensive Disks • Slouˇ z´ı ke zv´ yˇ sen´ı kapacity, rychlosti, nebo bezpeˇ cnosti disk˚ u. • Navenek se chov´ a jako jedin´ a diskov´ a jednotka s pozmˇ enˇ en´ ymi vlastnostmi. • Existuje cel´ a ˇ rada r˚ uzn´ ych uspoˇ r´ ad´ an´ı. Kaˇ zd´ e z nich vhodn´ e pro jinou aplikaci.
RAID 0 – schema '
?
&
$
'
%
&
A1 &
%
B2 %
&
C1
%
C2 %
&
D1 &
%
&
B1
&
$
A2 %
&
?
%
D2 %
&
%
RAID 0 – Striping • Data rozloˇ zena na v´ıce disk˚ u • Nen´ı to klasick´ y RAID – nedoch´ az´ı k redundanci • Pˇ ri v´ ypadku jedin´ eho disku m˚ uˇ zeme pˇ rij´ıt o veˇ sker´ a data • Zvyˇ suje v´ ykon jak pro ˇ cten´ı, tak pro z´ apis • Podporov´ ano i velmi levn´ ymi ˇ radiˇ ci
RAID 1 – Zrcadlen´ı '
?
&
$
'
%
&
A &
%
B %
&
C
%
C %
&
D &
%
&
B
&
$
A %
&
?
%
D %
&
%
RAID 1 – Mirroring • Disky instalov´ any ve dvojic´ıch. • Vˇ zdy se zapisuje na oba disky v p´ aru. ˇ ten´ı se ralizuje tam, kde to jde rychleji. • C • Pˇ ri v´ ypadku jedin´ eho disku jej staˇ c´ı vymˇ enit a nakop´ırovat na nˇ ej data z jeho partnera. • M˚ uˇ ze ”pˇ reˇ z´ıt” i v´ ypadek aˇ z n disk˚ u z 2n – za pˇ redpokladu, ˇ ze z kaˇ zd´ e dvojice vypadne nejv´ yˇ se jeden.
RAID 0+1, 1+0 • Kombinace princip˚ u RAID 0 a 1 pro alespoˇ n 4 disky • 0+1: stripe + mirror ... levn´ e souborov´ e syst´ emy • 1+0: mirror + stripe ... datab´ aze • podpora jiˇ z u relativnˇ e levn´ ych a jednoduch´ ych ˇ radiˇ c˚ u (0,1,0+1) – dostupn´ e na mnoha z´ akladn´ıch desk´ ach
RAID 5 • Parita zapisov´ ana postupnˇ e na r˚ uzn´ e disky • Pouˇ ziteln´ y od 3 disk˚ u v´ yˇ se • Rozumn´ y kompromis mezi bezpeˇ cnost´ı dat, kapacitou a v´ ykonem • vyˇ zaduje sloˇ zitˇ ekˇ s´ı elektroniku (b´ yv´ a na ˇ radiˇ c´ıch s procesorem a vˇ etˇ s´ı pamˇ et´ı)
RAID 6 • Odoln´ y proti v´ ypadku aˇ z dvou disk˚ u • Zv´ yˇ sen´ a redundance • Menˇ s´ı vyuˇ zit´ı kapacity • Potˇ rebuje sloˇ zitˇ ejˇ s´ı ˇ radiˇ c • Vhodn´ e pro mission-critical aplikace
Optick´ e disky • CD, DVD, blue-ray, ... • Informace uchov´ av´ ana prostˇ rednictv´ım rozd´ıln´ e odrazivosti svˇ etla • Lisovan´ e – velk´ e s´ erie disk˚ u se stejn´ ym obsahem → velmi spolehliv´ e • Modifikovateln´ e m´ edium (R, RW, RAM) – mal´ e s´ erie + z´ alohov´ an´ı + pˇ renos dat (pouze RW a RAM)
Jukeboxy
• P´ asky i optick´ e disky mohou m´ıt menˇ s´ı kapacitu, neˇ z je tˇ reba – poˇ zadovan´ a data jsou pak uloˇ zena na v´ıce m´ edi´ıch
• Jednoduch´ a m´ edia je moˇ zn´ e automaticky vymˇ eˇ novat (staˇ c´ı jedna ˇ ci nˇ ekolik m´ alo mechanik + v´ ymˇ enn´ y mechanismus + prostor na des´ıtky ˇ ci stovky m´ edi´ı)
Jukeboxy (2) • Poskytuj´ı obrovskou ´ uloˇ znou kapacitu s pomal´ ym pˇ r´ıstupem (sekundy)
• Vˇ etˇ sinou vyuˇ zity jako terci´ aln´ı pamˇ et’ – jsou tam ukl´ ad´ aan data, co se nepotˇ rebuj´ı pˇ r´ıliˇ sˇ casto, ale pˇ resto by mˇ ela b´ yt dostupn´ a
• Z´ alohov´ an´ı dat ze sekund´ arn´ıch pamˇ et´ı
Syst´ emy v´ ymˇ enn´ ych disk˚ u • Zaˇ r´ızen´ı umoˇ zˇ nuj´ıc´ı bezobsluˇ zn´ y pˇ r´ıstup k v´ıce CD nebo DVD disk˚ um • Nˇ ekdy vˇ cetnˇ e podpory z´ apisu • Nˇ ekolik r˚ uzn´ ych forem: – mechanika na v´ıce CD – stojan s mnoha mechanikami po jednom CD – mechanika s pˇ r´ıdavn´ ym zaˇ r´ızen´ım na v´ ymˇ enu CD (jukebox)
Parametry Jukeboxu • Aˇ z stovky CD/DVD (tj. aˇ z 5,5 TB)
• M˚ uˇ ze obsahovat i v´ıce mechanik
• Doba v´ ymˇ eny disk˚ u 2,5 – 10 s
• Nˇ ekdy i moˇ znost ot´ aˇ cet m´ edia (u oboustrann´ ych)
P´ askov´ e v´ ymˇ enn´ e syst´ emy
• Obdobnˇ e jako u CD/DVD existuj´ı i bezobsluˇ zn´ e syst´ emy s jednou ˇ ci nˇ ekolika m´ alo mechanikami a mnoha p´ askami
• Kapacita aˇ z de´ıtky TB
Flash pamˇ eti • Velmi rychl´ e
• Drah´ e
ˇ asto jen omezen´ • C y poˇ cet pˇ reps´ an´ı
• Dnes bˇ eˇ znˇ e dod´ avan´ e kapacity v jednotk´ ach GB (”kl´ıˇ cenky”) nebo des´ıtk´ ach GB (”SSD – solid-state disky”)
Pˇ ripojov´ an´ı vnˇ ejˇ s´ıch pamˇ et´ı
• Disky pˇ ripojov´ any vˇ etˇ sinou pˇ r´ımo (DAS – disrect attached storage), nebo pˇ res s´ıt’ (NAS – network atatched storage), pˇ r´ıpadnˇ e se chovaj´ı jako blokov´ a´ uloˇ ziˇ stˇ e (SAN – storage area network)
• SAN i NAS se daj´ı poˇ r´ıdit jak velk´ a, tak SOHO; pozor, nˇ ekdy je v´ ykon SOHO zaˇ r´ızen´ı velmi n´ızk´ y
Bezpeˇ cnost dat • RAID b´ yv´ a bezpeˇ cnˇ ejˇ s´ı neˇ z samotn´ e disky (s v´ yjimkou RAID 0), ale i zde m˚ uˇ ze doj´ıt ke ztr´ at´ am dat =⇒ je tˇ reba z´ alohovat, pˇ r´ıpadnˇ e vyuˇ z´ıvat dalˇ s´ı typy pamˇ et´ı (diskov´ e a p´ askov´ e jukeboxy)
• Kritick´ e syst´ emy i jejich z´ aloˇ zn´ı kopie je d˚ uleˇ zit´ e m´ıt um´ıstˇ en´ e na dostateˇ cnˇ e vzd´ alen´ ych a r˚ uzn´ ych m´ıstech (poˇ z´ ary, povodnˇ e)
Vnˇ ejˇ s´ı pamˇ eti
• Mnoho druh˚ u liˇ s´ıc´ıch se rychlost´ı, dod´ avanou kapacitou i cenou
• Plat´ı, ˇ ze velk´ e kapacity b´ yvaj´ı dostupn´ e pomalu, mal´ e kapacity rychleji nebo jsou silnˇ e miniaturizov´ any
• Je moˇ zn´ e vytv´ aˇ ret kask´ ady pamˇ et´ı
Z´ aznam
Logick´ y • kolekce souvisej´ıc´ıch poloˇ zek – hodnot atribut˚ u Fyzick´ y • logick´ y z´ aznam doplnˇ en´ y o oddˇ elovaˇ ce, definice d´ elek, zar´ aˇ zky, ... • d´ elka fyzick´ eho z´ aznamu – R
Typ z´ aznamu
d´ an jm´ eny a dom´ enami atribut˚ u
Aj : dom(Aj )
A1 : D1, . . . , An : Dn
Fyzick´ y a logick´ y z´ aznam Logick´ y z´ aznam – mnoˇ zina atribut˚ u Fyzick´ y z´ aznam (d´ elky R) – fyzick´ a reprezentace logick´ eho z´ aznamu na m´ ediu (m˚ uˇ ze obsahovat pomocn´ a data nav´ıc) Fyzick´ e z´ aznamy se ukl´ adaj´ı do fyzick´ ych str´ anek (blok˚ u – jejich velikost znaˇ c´ıme B) Bloky jsou minim´ aln´ı entitou pˇ ren´ aˇ senou mezi prim´ arn´ı a sekund´ arn´ı pamˇ et´ı
Blokovac´ı faktor, blokov´ an´ı Blokovac´ı faktor (b) – pomˇ er B/R Blokov´ an´ı (um´ıst’ov´ an´ı z´ aznam˚ u do blok˚ u); ˇ r´ık´ ame, ˇ ze z´ aznamy jsou: neblokovan´ e ⇐⇒ b = 1, B = R; blokovan´ e ⇐⇒ b > 1; pˇ rerostl´ e ⇐⇒ b < 1; Pro implementaci je d˚ uleˇ zit´ e, zda se R mˇ en´ı, ˇ ci nikoliv −→ budeme pˇ redpokl´ adat, ˇ ze se nemˇ en´ı.
Soubor Soubor je identifikovan´ a kolekce logicky souvisej´ıc´ıch z´ aznam˚ u. Jsou-li z´ aznamy stejn´ eho typu a velikosti, ˇ r´ık´ ame, ˇ ze soubor je homogenn´ı. V opaˇ cn´ em pˇ r´ıpade je nehomogenn´ı.
Kl´ıˇ c
Kl´ıˇ c souboru je mnoˇ zina atribut˚ u Ai1 ..Aik , k ≤ n, takov´ a, ˇ ze k-tice atribut˚ u < a1..ak > (kl´ıˇ ce z´ aznamu) jednoznaˇ cnˇ e identifikuj´ı z´ aznamy.
Vyhled´ avac´ı kl´ıˇ c je atribut (ˇ ci mnoˇ zina atribut˚ u), k jehoˇ z hodnotˇ e vyhled´ av´ ame mnoˇ zinu z´ aznam˚ u obsahuj´ıc´ıch pro dan´ y atribut pr´ avˇ e uvedenou hodnotu
Typy vyhled´ avac´ıch kl´ıˇ c˚ u
Hodnotov´ e – hodnoty z dom(Ai)
Haˇ sovan´ e – algoritmick´ a transformace hodnot
Relativn´ı – ud´ ana pozice od zaˇ c´ atku souboru
Operace nad soubory INSERT – vloˇ zen´ı z´ aznamu do souboru DELETE – ruˇ sen´ı z´ aznamu v souboru UPDATE – zmˇ ena nˇ ekter´ ych poloˇ zek z´ aznamu v souboru
Aktualizace souboru – posloupnost operac´ı INSERT, DELETE a UPDATE FETCH – z´ısk´ an´ı z´ aznamu ze souboru do vnitˇ rn´ı pamˇ eti
Sch´ ema organizace souboru • popis logick´ e pamˇ et’ov´ e struktury, co n´ıˇ z m˚ uˇ ze b´ yt p˚ uvodn´ı soubor zobrazen, spolu s algoritmy prov´ adˇ ej´ıc´ımi operace nad touto strukturou • m˚ uˇ ze popisovat v´ıce logick´ ych soubor˚ u sv´ azan´ ych dohromady • prim´ arn´ı soubor – soubor obsahuj´ıc´ı uˇ zivatelsk´ a data; N – poˇ cet z´ aznam˚ u v nˇ em
Fyzick´ a ´ uroveˇ n • Abstrakce fyzick´ eho zaˇ r´ızen´ı – fyzick´ e sch´ ema souboru – fyzick´ y soubor
• Re´ aln´ e fyzick´ e zaˇ r´ızen´ı – implementaˇ cn´ı sch´ ema souboru
Abstrakce pˇ r´ıtupu k soubor˚ um
sch´ ema organizace souboru
logick´ e soubory
?
fyzick´ e sch´ ema souboru
?
implementaˇ cn´ı sch´ ema ´ uroveˇ n typu
fyzick´ e soubory
implementace fyzick´ ych soubor˚ u ´ uroveˇ n v´ yskytu
Operace SOS • operace nad soubory (insert, delete, update) • BUILD – vytvoˇ ren´ı struktury • REORGANIZATION – uveden´ı SOS do nov´ eho v´ ychoz´ıho stavu • Stav souboru S (S ∗; extenze souboru S) – podoba SOS mezi dvˇ ema ukonˇ cen´ ymi aktualizacemi • CLOSE – aktualizuje nˇ ekter´ a data o souboru
Souborov´ e syst´ emy
• podpora pr´ ace se soubory na ´ urovni z´ akladn´ıho SW
• uchov´ avaj´ı metadata o souborech
• umoˇ zˇ nuj´ı spr´ avu soubor˚ u vˇ cetnˇ e mapov´ an´ı soubor˚ u na m´ edium
Dotazy nad soubory
dotaz nad sch´ ematem souboru S – jak´ akoliv tot´ aln´ı funkce vyj´ adˇ riteln´ a programem definovan´ a nad mnoˇ zinou US . kter´ a kaˇ zd´ emu stavu pˇ riˇ rad´ı odpovˇ ed’ – zpravidla mnoˇ zinu z´ aznam˚ u
hity – prvky odpovˇ edi v pˇ r´ıpadˇ e dokument˚ u
V´ıcerozmˇ ern´ e/ortogon´ aln´ı dotazy • dotaz na ´ uplnou shodu – zad´ any hodnoty vˇ sech atribut˚ u • dotaz na ˇ c´ asteˇ cnou shodu – zad´ any hodnoty jen nˇ ekter´ ych atribut˚ u • dotaz na ´ uplnou intervalovou shodu – zad´ an interval hodnot pro kaˇ zd´ y z atribut˚ u • dotaz na ˇ c´ asteˇ cnou intervalovou shodu – zad´ any intervaly pro vybran´ e atributy
Dalˇ s´ı operace
READ ENTIRE FILE – ˇ cten´ı cel´ eho souboru • s´ eriovˇ e – podle zadan´ eho uspoˇ r´ ad´ an´ı • sekvenˇ cnˇ e – podle fyzick´ eho upoˇ r´ ad´ an´ı z´ aznam˚ u v souboru
Vyv´ aˇ zenost struktury • omezen´ı d´ elky cesty ve struktuˇ re pˇ ri vyhled´ an´ı z´ aznamu (napˇ r. O(log M ), kde M je poˇ cet logick´ ych str´ anek) • rovnomˇ ern´ a naplnˇ enost str´ anek – faktor naplnˇ en´ı str´ anky λ (0 ≤ α < λ < β ≤ 1) – nˇ ekdy se λ oznaˇ cuje pr˚ umˇ ern´ e naplnˇ en´ı str´ anek • SOS splˇ nuj´ıc´ı obˇ e podm´ınky → dynamick´ e, ostatn´ı → statick´ e
Hardware – d˚ usledky Datov´ e struktury pro sekund´ arn´ı pamˇ eti mus´ı splˇ novat tyto podm´ınky:
• Z´ akladn´ı jednotkou komunikace je blok (sektor) ˇ ci jeho celistv´ y n´ asobek.
• B´ yv´ a v´ yhodnˇ ejˇ s´ı ˇ c´ıst n blok˚ u souvisle uloˇ zen´ ych neˇ z n blok˚ u n´ ahodnˇ e rozm´ıstˇ en´ ych. Tot´ eˇ z plat´ı i pro zapisov´ an´ı.
´ Urovnˇ e abstrakce – vrstvy
Logick´ a . . . jak na to pohl´ıˇ z´ıme pˇ ri n´ avrhu (logick´ e soubory – co k sobˇ e patˇ r´ı).
Fyzick´ a . . . fyzick´ e soubory – jak je to oˇ cima souborov´ eho syst´ emu.
Implementaˇ cn´ı . . . jak je to re´ alnˇ e rozm´ıstˇ eno na disku
Z´ aznam
Logick´ y • kolekce souvisej´ıc´ıch poloˇ zek – hodnot atribut˚ u Fyzick´ y • logick´ y z´ aznam doplnˇ en´ y o oddˇ elovaˇ ce, definice d´ elek, zar´ aˇ zky, ... • d´ elka fyzick´ eho z´ aznamu – R
Typ z´ aznamu
d´ an jm´ eny a dom´ enami atribut˚ u
Aj : dom(Aj )
A1 : D1, . . . , An : Dn
Soubor Soubor je identifikovan´ a kolekce logicky souvisej´ıc´ıch z´ aznam˚ u. Pozor! Soubor je kolekce (z´ aznamy se obecnˇ e mohou opakovat), ne mnoˇ zina!
Homogenn´ı soubor
Hodnoty
primitivn´ı typy
Deklarace S(A1 : D1, . . . , An : Dn)
Obsahuje pouze z´ aznamy jedin´ eho typu.
Nehomogenn´ı soubor Opak homogenn´ıho souboru – obsahuje bud’ z´ aznamy r˚ uzn´ ych typ˚ u, z´ aznamy se sloˇ zitˇ ejˇ s´ı strukturou, nebo z´ aznamy r˚ uzn´ ych d´ elek. ´ mluva: nebude-li ˇ U reˇ ceno jinak, budeme uvaˇ zovat pouze homogenn´ı soubory.
Kl´ıˇ c
Kl´ıˇ c souboru je mnoˇ zina atribut˚ u Ai1 ..Aik , k ≤ n, takov´ a, ˇ ze k-tice atribut˚ u < a1..ak > (kl´ıˇ ce z´ aznamu) jednoznaˇ cnˇ e identifikuj´ı z´ aznamy.
Vyhled´ avac´ı kl´ıˇ c je atribut (ˇ ci mnoˇ zina atribut˚ u), k jehoˇ z hodnotˇ e vyhled´ av´ ame mnoˇ zinu z´ aznam˚ u obsahuj´ıc´ıch pro dan´ y atribut pr´ avˇ e uvedenou hodnotu
Typy vyhled´ avac´ıch kl´ıˇ c˚ u
Hodnotov´ e – hodnoty z dom(Ai)
Haˇ sovan´ e – algoritmick´ a transformace hodnot
Relativn´ı – ud´ ana pozice od zaˇ c´ atku souboru
Operace nad soubory INSERT – vloˇ zen´ı z´ aznamu do souboru DELETE – ruˇ sen´ı z´ aznamu v souboru UPDATE – zmˇ ena nˇ ekter´ ych poloˇ zek z´ aznamu v souboru Aktualizace souboru – posloupnost operac´ı INSERT, DELETE a UPDATE FETCH – z´ısk´ an´ı z´ aznamu ze souboru do vnitˇ rn´ı pamˇ eti
Fyzick´ y a logick´ y z´ aznam Logick´ y z´ aznam – mnoˇ zina atribut˚ u Fyzick´ y z´ aznam (d´ elky R) – fyzick´ a reprezentace logick´ eho z´ aznamu na m´ ediu (m˚ uˇ ze obsahovat pomocn´ a data nav´ıc) Fyzick´ e z´ aznamy se ukl´ adaj´ı do fyzick´ ych str´ anek (blok˚ u – jejich velikost znaˇ c´ıme B) Bloky jsou minim´ aln´ı entitou pˇ ren´ aˇ senou mezi prim´ arn´ı a sekund´ arn´ı pamˇ et´ı
Blokovac´ı faktor, blokov´ an´ı Blokovac´ı faktor (b) – pomˇ er B/R Blokov´ an´ı (um´ıst’ov´ an´ı z´ aznam˚ u do blok˚ u); ˇ r´ık´ ame, ˇ ze z´ aznamy jsou: neblokovan´ e ⇐⇒ b = 1, B = R; blokovan´ e ⇐⇒ b > 1; pˇ rerostl´ e ⇐⇒ b < 1; Pro implementaci je d˚ uleˇ zit´ e, zda se R mˇ en´ı, ˇ ci nikoliv −→ budeme pˇ redpokl´ adat, ˇ ze se nemˇ en´ı.
Sch´ ema organizace souboru • popis logick´ e pamˇ et’ov´ e struktury, co n´ıˇ z m˚ uˇ ze b´ yt p˚ uvodn´ı soubor zobrazen, spolu s algoritmy prov´ adˇ ej´ıc´ımi operace nad touto strukturou • m˚ uˇ ze popisovat v´ıce logick´ ych soubor˚ u sv´ azan´ ych dohromady • prim´ arn´ı soubor – soubor obsahuj´ıc´ı uˇ zivatelsk´ a data; N – poˇ cet z´ aznam˚ u v nˇ em
Fyzick´ a ´ uroveˇ n • Abstrakce fyzick´ eho zaˇ r´ızen´ı – fyzick´ e sch´ ema souboru – fyzick´ y soubor
• Re´ aln´ e fyzick´ e zaˇ r´ızen´ı – implementaˇ cn´ı sch´ ema souboru
Abstrakce pˇ r´ıtupu k soubor˚ um
sch´ ema organizace souboru
logick´ e soubory
?
fyzick´ e sch´ ema souboru
?
implementaˇ cn´ı sch´ ema ´ uroveˇ n typu
fyzick´ e soubory
implementace fyzick´ ych soubor˚ u ´ uroveˇ n v´ yskytu
Operace SOS • operace nad soubory (insert, delete, update) • BUILD – vytvoˇ ren´ı struktury • REORGANIZATION – uveden´ı SOS do nov´ eho v´ ychoz´ıho stavu • Stav souboru S (S ∗; extenze souboru S) – podoba SOS mezi dvˇ ema ukonˇ cen´ ymi aktualizacemi • CLOSE – aktualizuje nˇ ekter´ a data o souboru
Souborov´ e syst´ emy
• podpora pr´ ace se soubory na ´ urovni z´ akladn´ıho SW
• uchov´ avaj´ı metadata o souborech
• umoˇ zˇ nuj´ı spr´ avu soubor˚ u vˇ cetnˇ e mapov´ an´ı soubor˚ u na m´ edium
Dotazy nad soubory
dotaz nad sch´ ematem souboru S – jak´ akoliv tot´ aln´ı funkce vyj´ adˇ riteln´ a programem definovan´ a nad mnoˇ zinou US . kter´ a kaˇ zd´ emu stavu pˇ riˇ rad´ı odpovˇ ed’ – zpravidla mnoˇ zinu z´ aznam˚ u
hity – prvky odpovˇ edi v pˇ r´ıpadˇ e dokument˚ u
V´ıcerozmˇ ern´ e/ortogon´ aln´ı dotazy • dotaz na ´ uplnou shodu – zad´ any hodnoty vˇ sech atribut˚ u • dotaz na ˇ c´ asteˇ cnou shodu – zad´ any hodnoty jen nˇ ekter´ ych atribut˚ u • dotaz na ´ uplnou intervalovou shodu – zad´ an interval hodnot pro kaˇ zd´ y z atribut˚ u • dotaz na ˇ c´ asteˇ cnou intervalovou shodu – zad´ any intervaly pro vybran´ e atributy
Dalˇ s´ı operace
READ ENTIRE FILE – ˇ cten´ı cel´ eho souboru • s´ eriovˇ e – podle zadan´ eho uspoˇ r´ ad´ an´ı • sekvenˇ cnˇ e – podle fyzick´ eho upoˇ r´ ad´ an´ı z´ aznam˚ u v souboru
Vyv´ aˇ zenost struktury • omezen´ı d´ elky cesty ve struktuˇ re pˇ ri vyhled´ an´ı z´ aznamu (napˇ r. O(log M ), kde M je poˇ cet logick´ ych str´ anek) • rovnomˇ ern´ a naplnˇ enost str´ anek – faktor naplnˇ en´ı str´ anky λ (0 ≤ α < λ < β ≤ 1) – nˇ ekdy se λ oznaˇ cuje pr˚ umˇ ern´ e naplnˇ en´ı str´ anek • SOS splˇ nuj´ıc´ı obˇ e podm´ınky → dynamick´ e, ostatn´ı → statick´ e
Sch´ ema organizace souboru (SOS)
• abstrakce zobecˇ nuj´ıc´ı soubory s urˇ cit´ ymi vlastnostmi
• mapov´ an´ı souboru na logick´ e´ urovni do ´ urovnˇ e fyzick´ e, pˇ r´ıpadnˇ e i implementaˇ cn´ı
Sch´ emata organizace souboru • Sekvenˇ cn´ı soubor
• Index-sekvenˇ cn´ı soubor
• Indexovan´ y soubor
• Soubor s pˇ r´ım´ ym pˇ r´ıstupem
Hromada
• Nehomogenn´ı soubor
• V pˇ r´ıpadˇ e z´ aznam˚ u s promˇ ennou strukturou se uv´ adˇ ej´ı i jm´ ena ˇ ci k´ ody atribut˚ u
• Vyhled´ an´ı z´ aznamu O(N )
Sekvenˇ cn´ı soubor
• Nejjednoduˇ sˇ s´ı SOS
• Homogenn´ı – soubor obsahuje pouze z´ aznamy dan´ eho typu
• V d´ avkov´ ych syst´ emech velmi ˇ cast´ y
Nesetˇ r´ıdˇ en´ y sekvenˇ cn´ı soubor • Pouˇ ziteln´ y pro uloˇ zen´ı sesb´ıran´ ych dat • Vhodn´ y pro pˇ r´ıpady, kdy prob´ır´ ame jeden z´ aznam za druh´ ym a nˇ eco s nimi dˇ el´ ame bez vazby na okol´ı (napˇ r. kontrolujeme jejich integritu) • Operace READ, WRITE • Vyhled´ an´ı z´ aznamu O(N ), resp. O(N/bbc)
Uspoˇ r´ adan´ y sekvenˇ cn´ı soubor
• Poˇ rad´ı dle (vyhled´ avac´ıho) kl´ıˇ ce
• Vhodn´ y zejm´ ena pro pr´ aci se vˇ semi z´ aznamy s vazbou na jin´ a data – aktualizace ´ uloˇ ziˇ stˇ e, sl´ ev´ an´ı
• Pro pr´ aci s jednotliv´ ymi z´ aznamy se moc nehod´ı
Uspoˇ r´ adan´ y sekvenˇ cn´ı soubor (2)
• Prim´ arn´ı soubor + soubor aktualizac´ı (dodateˇ cn´ ych zmˇ en)
• Soubor aktualizac´ı neb´ yv´ a setˇ r´ıdˇ en (dopisuje se na konec)
• Reorganizace: setˇ r´ıd´ıme soubor aktualizac´ı + zatˇ r´ıd´ıme s prim´ arn´ım souborem do nov´ eho prim´ arn´ eho souboru
Uspoˇ r´ adan´ y sekvenˇ cn´ı soubor Vyhled´ an´ı z´ aznamu Nesetˇ r´ıdˇ en´ em O(N ), setˇ r´ıdˇ en´ em O(log2 N ) TF = dlog2(N/bbc)e(s + r + btt )
Pˇ reps´ an´ı z´ aznamu (Update): TU = TF + 2r Kl´ıˇ c se nemˇ en´ı TU = TI kl´ıˇ c se mˇ en´ı
Index-sekvenˇ cn´ı soubor • Pˇ r´ıstup k z´ aznam˚ um je moˇ zn´ y jak sekvenˇ cnˇ e, tak i pˇ r´ımo ˇ´ • C asti: prim´ arn´ı soubor, index a oblast pˇ reteˇ cen´ı • Vhodn´ y zejm´ ena tenkr´ at, kdyˇ z potˇ rebujeme jak pˇ r´ıstup k jednotliv´ ym z´ aznam˚ um dle prim´ arn´ıho kl´ıˇ ce (jeˇ stˇ e l´ epe, kdyˇ z nen´ı tˇ reba kl´ıˇ c mˇ enit, jen data), tak i ke vˇ sem z´ aznam˚ um najednou
Index-sekvenˇ cn´ı soubor – Aplikace
´ˇ • U cetn´ı syst´ em platebn´ıch karet – individu´ aln´ı pˇ r´ıstup pˇ ri manipulaci s kartou/´ uˇ ctem; – d´ avkov´ y pˇ r´ıstup pro generov´ an´ı sum´ aˇ r˚ u, mˇ es´ıˇ cn´ıch vy´ uˇ ctov´ an´ı, apod.
Index-sekvenˇ cn´ı soubor – Struktura
2. ´ uroveˇ n Ab Oi Q Q
´ ´
Q
´
Q
´ ´
´
index
Q Q
´
Q
´
Q QQ s
´ ´ +
My Oi . . . Bx Eh Kd 1. ´ uroveˇ n Ab XX © H ©
¤
©©
¤
©
©©
¤
© ©©
¤
©
©© ¼
©©
Ab Ak Bf Bp
¤
²¤¤
¤
XXX XXX H XXX HH XXX H XXX HH XXX H XXX HH XXX H XXX HH z X j
HH
Bx Ck Dl Ea
Eh Fu Gh Ha
¡ µ
¡ ¡ ª
¡
¡
prim´ arn´ı soubor
oblast pˇ reteˇ cen´ı
-
Jm
¡
¡
Kd
Index-sekvenˇ cn´ı soubor: Odkazy do oblasti pˇ reteˇ cen´ı • Za kaˇ zd´ ym z´ aznamem − zabere to v´ıce m´ısta + kratˇ s´ı sekvence v oblasti pˇ reteˇ cen´ı • Na konci kaˇ zd´ eho bloku − mohou se tvoˇ rit delˇ s´ı sekvence v oblasti pˇ reteˇ cen´ı + menˇ s´ı n´ aroky na m´ısto v bloku; je moˇ zn´ e si v bloc´ıch nechat volno na pozdˇ eji pˇ ridan´ e prvky
Index-sekvenˇ cn´ı soubor – kapsy
• implementace index-sekvenˇ cn´ıho souboru pomoc´ı kapes
• kapsa (bucket) je mnoˇ zina blok˚ u organizovan´ ych jako spojov´ y seznam
• indexuj´ı se kapsy
Index-sekvenˇ cn´ı soubor – kapsy (2) 00 Babka
10
Kol´ aˇ r
20
index 1. ´ urovnˇ e
odkaz na dalˇ s´ı bloky kapsy
ˇ c´ıslo bloku ?
?
00 00000
0
10 11111 Babka Codr
Couf
Colt
Cuc
20 11110 Kol´ c Mac´ aˇ r Kotrˇ ak Maloˇ n 6
bitov´ a mapa
6
bloky (kapsy) se z´ aznamy
0 0
Index-sekvenˇ cn´ı soubor – kapsy (2) Aktualizace: I(Danˇ ek), I(Alfons), D(Kotrˇ c) 00 Babka
10
Kol´ aˇ r
20
00 00000 Alfons 10 11111 Babka Codr 20 10110 Kol´ aˇ r 30 10000 Danˇ ek
0 Couf
Colt
Mac´ ak Maloˇ n
Cuc
30 0 0
Index-sekvenˇ cn´ı soubor – ´ urovnˇ e Maxim´ aln´ı poˇ cet ´ urovn´ı x = dlogp N/bbce; b = bB/Rc. Pˇ ripomeˇ nme, ˇ ze B je velikost bloku a R (pr˚ umˇ ern´ a) velikost z´ aznamu. Poˇ cet pˇ r´ıstup˚ u na disk odpov´ıd´ a poˇ ctu ´ urovn´ı. Minimalizace poˇ ctu pˇ r´ıstup˚ u na disk: • prakticky pouze maximalizac´ı B; • omezeno kapacitou stopy.
Index-sekvenˇ cn´ı soubor – ISAM Pˇ r´ım´ a podpora index-sekvenˇ cn´ıch soubor˚ u v runtime COBOLu ´ roveˇ U n 1 2 3
Um´ıstˇ en´ı stopa index stop na 0. stopˇ e kaˇ zd´ eho v´ alce urˇ cuje pozice v prim´ arn´ım souboru v´ alec index v´ alc˚ u (na zaˇ c´ atku oblasti souboru) urˇ cuje lokality s indexy stop svazek master index po OPEN v RAM; urˇ cuje lokality s indexy v´ alc˚ u
TF = 2(s + r + btt ) + r + btt = 2s + 3r + 3btt
Index-sekvenˇ cn´ı soubor – ISAM (2) Oblast pˇ reteˇ cen´ı – na kaˇ zd´ em v´ alci + spoleˇ cn´ a pro cel´ y soubor Statick´ y soubor =⇒ nutn´ a reorganizace – po naplnˇ en´ı oblasti pˇ reteˇ cen´ı nebo periodicky
ISAM – struktura indexu Cylindry i stopy ˇ c´ıslov´ any od 0. Index stop – na 0. stopˇ e cylindru 1 150 6
stopa
2 200
3 400
...
H Y HH
H
nejvˇ etˇ s´ı kl´ıˇ c na stopˇ e
Index cylindr˚ u – um´ıstˇ en kdekoliv jinde 13 1650 6
cylindr
14 1750
15 2000
H YH
HH
nejvˇ etˇ s´ı kl´ıˇ c na cylindru
...
ISAM – struktura indexu (2) • Z´ aznamy v bloc´ıch (stop´ ach) setˇ r´ıdˇ eny • Hlavn´ı (master) index pro velk´ e soubory na v´ıce disc´ıch ukazuje na stopy indexu cylindr˚ u • Oblast pˇ reteˇ cen´ı: – vytlaˇ cen nejvˇ etˇ s´ı kl´ıˇ c na stopˇ e – aktualizace indexu
ISAM – index s oblast´ı pˇ reteˇ cen´ı index stop 1 120 1 120 2 200 2 200 3 250 N
Ov
N
Ov
N
prim´ arn´ı soubor 130 145 150
...
Insert(185):
180 190 200 ©
© © ¼©
stopa pro pˇ reteˇ cen´ı
1 120 1 120 2 190 10 1 200 3 250 130 145 150
...
180 185 190
ISAM – index s oblast´ı pˇ reteˇ cen´ı (2) Insert(185):
©© © ¼©
nemˇ en´ı se
1 120 1 120 2 186 10 2 200 3 250 130 145 150
...
180 185 186
Insert(194): oblast pˇ reteˇ cen´ı 10 194 . . . # 200 10 190 3 1 ˇ retˇ ezec v oblasti pˇ reteˇ cen´ı
Index-sekvenˇ cn´ı soubor – v´ yhody
• Rychl´ y pˇ r´ıtup dle prim´ arn´ıho kl´ıˇ ce.
• Zachov´ av´ a vˇ etˇ sinu dobr´ ych vlastnost´ı setˇ r´ıdˇ en´ eho sekvenˇ cn´ıho souboru.
Index-sekvenˇ cn´ı soubor – nev´ yhody • Rychl´ e vyhled´ av´ an´ı jen pro prim´ arn´ı kl´ıˇ c • Probl´ emy s dynamikou prim´ arn´ıho souboru – Oblast pˇ reteˇ cen´ı → vede ke zpomalen´ı pˇ r´ıstupu k dat˚ um – Bloky inicializov´ any jako ne zcela zaplnˇ en´ e → vˇ etˇ s´ı n´ aroky na prostor • Pˇ r´ıpadn´ a potˇ reba reorganizac´ı
Index-sekvenˇ cn´ı soubor – n´ avrh • Uspoˇ r´ ad´ an´ı poloˇ zek v seznamu • Definice prim´ arn´ıho kl´ıˇ ce • Anal´ yza doplˇ nov´ an´ı z´ aznam˚ u (Poˇ c´ ateˇ cn´ı naplnˇ en´ı str´ anek – max. 60 %) • Prostor pro prim´ arn´ı soubor, index a oblast pˇ reteˇ cen´ı • Poˇ cet ´ urovn´ı indexu • Blokovac´ı faktor prim´ arn´ı oblasti, indexu
Index-sekvenˇ cn´ı soubor – z´ avˇ er
• Blokov´ an´ı zvyˇ suje ´ uˇ cinnost • Rychl´ y pˇ r´ım´ y pˇ r´ıstup – koˇ sat´ y index ˇ´ • Z ad´ a se pouze sekvenˇ cn´ı pˇ r´ıstup → pouˇ z´ıt sekvenˇ cn´ı soubor → nejsou tˇ reba indexy ˇ´ • Z ad´ a se pouze pˇ r´ım´ y pˇ r´ıstup → pouˇ z´ıt soubor s pˇ r´ım´ ym pˇ r´ıstupem → nen´ı tˇ reba uspoˇ r´ adanost
Indexovan´ y soubor • Umoˇ zˇ nuje vyhled´ avat z´ aznamy podle r˚ uzn´ ych kl´ıˇ c˚ u
• Odpov´ıd´ a tabulce v DB
• Prim´ arn´ı soubor a indexy
• Indexy mohou b´ yt mnoha r˚ uzn´ ych typ˚ u (a to i v r´ amci jedin´ eho indexovan´ eho souboru)
Indexovan´ y soubor – obr´ azek 4.1 1.1
Jir´ asek Nˇ emcov´ a Svˇ etl´ a index 2. ´ urovnˇ e (master/hlavn´ı index)
2.1
Jir´ asek
4.1
Jir´ asek
4.3
Jir´ asek
5.2
Nˇ emcov´ a 4.2 Nˇ emcov´ a 5.2 Nˇ emcov´ a 5.3 Nˇ emcov´ a 6.3
3.1
Nˇ emcov´ a 7.2 6.2 Svˇ etl´ a index 1. ´ urovnˇ e
Vyhled´ avac´ı kl´ıˇ c: Pˇ r´ıjmen´ı
Jir´ asek Nˇ emcov´ a Jir´ asek Svˇ etl´ a
5.1
Jir´ asek Nˇ emcov´ a Nˇ emcov´ a ...
6.1
... Svˇ etl´ a Nˇ emcov´ a ... prim´ arn´ı soubor
Indexovan´ y soubor – ´ urovnˇ e indexu Poˇ cet ´ urovn´ı indexu poˇ c´ıt´ ame podobnˇ e jako u index-sekvenˇ cn´ıho souboru, ale indexujeme jednotliv´ e z´ aznamy a ne bloky. x = dlogb N e, b = bB/Rc; B ... velikost fyzick´ e str´ anky R ... (pr˚ umˇ ern´ a) velikost fyzick´ eho indexov´ eho z´ aznamu
Indexovan´ y soubor – ˇ c´ asteˇ cn´ a shoda ˇ eˇ R sen´ı dotaz˚ u na ˇ c´ asteˇ cnou shodu
• Vytv´ aˇ ren´ı pr˚ unik˚ u seznam˚ u adres (ukazatel˚ u) prim´ arn´ıch z´ aznam˚ u – Netrivi´ aln´ı pˇ ri velk´ em objemu, tj. velk´ a N mal´ a aktu´ aln´ı dom´ ena A
• Kombinovan´ y index – pro v´ıce atribut˚ u souˇ casnˇ e (A,B,C)
Indexovan´ y soubor – implementace • Nepˇ r´ım´ e adresov´ an´ı: – prim´ arn´ı kl´ıˇ c, sekund´ arn´ı kl´ıˇ c – sekund´ arn´ı kl´ıˇ c se indexuje na prim´ arn´ı kl´ıˇ c
• Moˇ zn´ a reorganizace, restrukturalizace souboru bez ovlivnˇ en´ı indexu • Vyˇ sˇ s´ı reˇ zie dotazu
Bitov´ a mapa • Vhodn´ a pro malou dom´ enu hodnot • Boolsk´ e dotazy se ˇ reˇ s´ı logick´ ymi operacemi • Bitov´ e vektory lze vytv´ aˇ ret pro v´ıce atribut˚ u – Obecnˇ ejˇ s´ı Boolsk´ e dotazy A Poˇ rad´ı z´ aznamu v S α 1 0 0 1 0 0 0 1 0 0 1 1 0 β 0 1 0 0 0 1 0 0 1 1 0 0 0
Bitov´ e mapy
• Pˇ ri zachov´ an´ı velikosti dom´ eny jejich velikost roste s poˇ ctem z´ aznam˚ u pouze line´ arnˇ e
• Je moˇ zn´ e sdruˇ zovat procesy proch´ azej´ıc´ı bitovou mapu – nov´ y proces nejprve se st´ avaj´ıc´ım doˇ cte to, co ten st´ avaj´ıc´ı jeˇ stˇ e nem´ a zpracovan´ e, a pak se vr´ at´ı k tomu zbytku (piggybacking)
Seznamy adres Odstranˇ en´ı duplicity kl´ıˇ c˚ u Chemik
90
Mechanik 91 Referent
92
90 3 1.1 1.4 2.3 91 1 1.2 92 3 1.3 2.1 2.2
Prim´ arn´ı soubor
Indexy indexovan´ eho souboru • statick´ e • seznamy adres • bitov´ e mapy • B-stromy a jejich varianty • kombinovan´ e indexy • v´ıcerozmˇ ern´ e indexy
