====== AP12 Organizace souborů ======
 
===== Zadání =====
(Schémata organizace souborů. Statické organizace souborů, sekvenční soubory, indexové a přímé organizace souborů, statické hašování. Implementace souborů. Dynamické organizace souborů, dynamické hašování, B-stromy a jejich varianty. Základy teorie informace, komprese dat)








===== Schémata organizace souborů =====
**Cíl** = umožnit optimálně řešit operace nad záznamy souboru nezávisle na konkrétním fyzickém zařízení vnější paměti
**Schéma organizace souborů** = způsob, jak jsou zakódovaná data počítačem uložená do paměti. Schéma organizace souboru je popis logické paměťové struktury, do níž lze zobrazit logický soubor, spolu s algoritmy operací nad touto strukturou. Ta je obvykle tvořena z logických stránek (bloků pevné délky) a může popisovat více provázaných log. souborů, z nichž primární soubor je ten, který obsahuje uživatelská data. Operace definované nad schématem org. souboru jsou kromě operací nad soubory ještě build, reorganization, open a close.

Proti němu stojí fyzické schéma souboru - struktura nad fyzickými soubory, nejblíže hardwaru je implementační schéma souboru.

Zajištění Vyváženosti struktury znamená zajištění omezení cesty při vyhledávání nějakým výrazem (zaručení asymptotické složitosti), navíc zaručení rovnoměrnosti zaplnění struktury - faktor naplnění stránek. Schémata, která splňují obě podmínky, se nazývají dynamická, ostatní jsou označována jako statická.
**Logické schéma souboru** -- Obsahuje primární soubor a pomocné soubory (indexy, rejstříky...). Výběrem vhodného logického schématu souboru se snažíme dosáhnout minimalizace počtu přístupů do sekundární paměti (na disky) -- ideální stav je 1 požadavek = 1 přístup.
**Fyzické schéma souboru** -- Zobrazuje logické soubory do paměťových jednotek konkrétního použitého typu paměti.
**Implementační schéma** -- Popisuje rozmístění dat na konkrétním uchovávacím médiu. Standardně řeší OS nezávisle na aplikacích

===== Statické organizace souborů =====
  * homogenní soubor -- hodnoty položek jsou primitivní typy, všechny záznamy jsou jednoho typu
      *je deklarovatelný formou S(A1:D1,...,An:Dn), kde Ax je jméno atributu a Dx je doména hodnot
  * nehomogenní soubor -- hodnoty položek jeho záznamů nejsou primitivní typy nebo záznamy nejsou jednoho typu

**Do statické organizace souborů patří:**
  * **hromada (neuspořádaný sekvenční soubor)**
    * Hromada (heap) je nejjednodušší schéma organizace souboru, kdy jsou záznamy v souboru jen náhodně naházeny za sebou. Časová složitost vyhledávání je O(n) (lineární), pokud n je počet záznamů. Jde o nehomogenní soubor, kde záznamy obvykle nemají pevnou délku.
  * **neuspořádaný sekvenční soubor**
    * homogenní soubor
    * sekvenční přístup
    * homogenní obdoba hromady
{{:home:prog:neusek.jpg|}}
  * **uspořádaný sekvenční soubor**
      * V uspořádaném sekvenčním souboru jsou záznamy řazeny podle vyhledávacího klíče. Aktualizované záznamy se umístí do zvláštního souboru a až při další operaci //reorganization// jsou přidány do primárního souboru. Složitost nalezení záznamu je také O(n) (lineární), ale pokud se hledá podle klíče, podle kterého jsou záznamy seřazeny, a navíc je soubor na médiu s přímým přístupem, sníží se na O(log n) (logaritmická).
      * **Primární soubor** + **soubor aktualizací** (dodatečných změn)
      * **Soubor aktualizací** nebývá seřazený (dopisuje se na konec)
      * **Reorganizace**: seřadíme soubor aktualizací + zatřídíme s primárním souborem do nového primárního souboru
      * nevýhody primárního souboru -- při vkládání je nutná náročná reorganizace
      *  **keysort** -- snižuje náklady na reorganizaci -- udržuje se soubor (nemusí být seřazený) + index (je vždy seřazený)
      * **řetězené struktury** -- řetězení usnadní následná vkládání a rušení záznamů
Ukázka uspořádaného sekvenčního souboru -- keysort:
{{:home:prog:usp_sekv_soubor_1_obr.png| Uspořádaný sekvenční soubor -- keysort}}
Ukázka uspořádaného sekvenčního souboru -- řetězené struktury:
{{:home:prog:usp_sekv_soubor_2_obr.png| Uspořádaný sekvenční soubor -- řetězené struktury}}
  * **index-sekvenční soubor**
    * části: primární soubor, index a oblast přetečení
    * primární soubor je seřazený podle primárního klíče, ke kterému je vytvořena struktura indexů
    * 2 možné přístupy -- indexový i sekvenční
    * Indexem se vymezuje oblast stránek v primárním souboru, kde záznam může ležet, tato oblast se prohlíží sekvenčně
    * buckety pro přesahy, nutná občasná reorganizace
{{:home:prog:index-sekvencni.png|}}
  * **indexovaný soubor**
    * seřadí se index, primární soubor se záznamy je neseřazený
    * Indexovaný soubor znamená primární soubor plus indexy pro různé vyhledávací klíče. Neindexují se už stránky, ale přímo záznamy, a proto primární soubor nemusí být nutně seřazený. Index může být podobný jako u index-sekvenčního souboru, pro záznamy se stejným klíčem je ale vhodné, aby byly na všech úrovních indexu kromě poslední sloučené. Při aktualizaci se nepoužívá oblast přetečení, mění se pouze index.
{{:home:prog:index.png|}}
  * **soubor s přímým přístupem** (tak kdyz je tam hash tak to asi patri do dynamickych struktur)
    * algoritmická transformace vyhledávacího klíče na adresu záznamu
    * hašování

===== Indexování v souborech =====
  * procházení přímo záznamů je při operacích velice pomalé -- indexy mají řádově menší velikost než samotné záznamy a jejich prohledávání je výrazně rychlejší
  * díky menší velikosti je možné indexy držet v operační paměti bez nutnosti přístupu na disk
  * často stačí pro vyřešení některých dotazů zpřístupnit pouze malou část záznamů -- na základě indexů je možné efektivně provádět filtrování
  * forma indexu: <color blue>{ vyhledávací klíč ; ukazatel na záznam }</color>
  * __typy indexů:__
    *řádné, lineární indexy -- v tabulce uspořádané dvojice { vyhledávací klíč ; ukazatel na záznam } podle hodnoty vyhl. klíče
    *hašované indexy -- využití hašovací funkce vyhledávacího klíče
    *stromové indexy -- využití grafové struktury strom
    *indexové bitové mapy -- pozice bitů v bitovém vektoru určují lokality záznamů
  * indexy mohou být víceúrovňové -- "index do indexu" -- nejnižší úroveň může být přímo primární soubor, výše jsou řídké indexy

==== Řádné indexy ====
Obvykle pokud se mluví o indexech, jsou myšleny řádné.
**Dělení 1**
  - primární index -- podle jeho klíče je uspořádán primární soubor se záznamy; může být hustý nebo řídký
  - sekundární index -- určený pro dotazy založené na jiném vyhledávacím klíči než na primárním; musí být hustý
**Dělení 2**
//hustý// -- indexový záznam pro každou hodnotu vyhledávacího klíče. Typicky bývá uspořádán podle hodnoty klíče
{{:home:prog:husty.jpg|}}
//řídký// -- indexový záznam pouze pro některé hodnoty vyhledávacího klíče; použitelné pouze v případě, kdy je soubor podle tohoto klíče uspořádán
{{:home:prog:ridky.jpg|}}

<box 90% orange | Příklad>
**Uložený soubor se záznamy:**

^ ID (2B) ^ Jméno (20B)      ^ Rok narození (2B)       ^ Místo narození (16B)          ^ Telefon (4B) ^ Bydliště (16B) ^
| 1 | Bílá Alena | 1972 | Ostrava | xxxxxxxx | Brno |
| 2 | Novák Jan | 1952 | Praha | 123456789| Kladno |
| 3 | Novotný Tomáš | 1987 | Brno | 565656565| Vyškov |
| 4 | Procházka Petr | 1964 | Brno | 100001011| Řestoky |

**Hustý index pro atribut jméno:**
^ Jméno ^ ID ^
|Bílá Alena|1|
|Novák Jan|2|
|Novotný Tomáš|3|
|Procházka Petr|4|
Pokud chceme vyhledat místo narození Tomáše Novotného, pak je při sekvenčním prohledávání nutné načíst 2 · (2 B + 20 B + 2 B + 16 B + 4 B + 16 B) + 2 B + 20 B + 2 B + 16 B = 160 B. Při použití hustého indexu stačí načíst 3 · (20 B + 2 B) + 2 B + 20 B + 2 B + 16 B = 106 B. Pokud je index uložen v operační paměti, pak v obou případech stačí pouze jeden přístup na disk, avšak v prvním případě bude třeba číst výrazně více dat.

**Řídký index pro atribut jméno:**
^ Jméno ^ ID ^
|Bílá Alena|1|
|Novotný Tomáš|3|
Pokud je požadavek na vyhledání například Jana Nováka, nalezne se poslední záznam v uspořádání před ním (Alena Bílá) a dál se postupuje sekvenčně.

**Sekundární index pro atribut místo narození:**
^ Místo narození ^ ID ^
|Brno|3,4|
|Ostrava|1|
|Praha|2|
</box>

===== Implementace souborů =====
<box 90% round blue | Definice>**soubor 1** = pojmenovaná kolekce souvisejících záznamů
**soubor 2** = logická paměťová jednotka zobrazovaná operačním systémem do fyzického paměťového zařízení
**záznam** = kolekce atributů charakterizujících jistý objekt
**adresář** = kolekce dat obsahující informace o souborech uchovávaných na disku (jméno, typ, adresa, délka, maximální délka, čas posledního přístupu...)</box>

==== Možná formátování ====
  - volné formátování -- sekvenčně řazené záznamy pevné i proměnlivé délky
  - komplexní formátování -- soubor obsahuje vhodné řídící struktury nebo se k záznamům přistupuje přes přístupové funkce (B-stromy, haše...)

==== Uložení souborů na disku ====
  -  souvislá alokace datových bloků
    * soubor je na disku uložen v souvislé posloupnosti datových bloků
  -  alokace datových bloků pomocí zřetězeného seznamu
    * každý datový blok obsahuje data a ukazatel na následující datový blok
  -  alokace datových bloků pomocí tabulky
    * alokace datových bloků je založená na zřetězeném seznamu, ale ukazatele na následující datový blok jsou uloženy v tabulce FAT
  - i-nodes
    * i-node je struktura, která obsahuje jak atributy souboru, tak adresy datových bloků, ve kterých je uložen obsah souboru

===== Dynamické organizace souborů =====
Motivace: změny dat neznamenají velké (globální) reorganizace, které jsou drahé, ale spíše reorganizace lokální.
  - B-strom
  - dynamický haš soubor
    * založený na rozšiřitelném hašování nebo lineárním hašování









===== Hašování =====
<box 90% round blue | Definice>**hašovací funkce (obecně)** = převedení libovolně dlouhého vstupu na výstup pevné délky
**hašovací funkce (ve smyslu organizace souborů)** = funkce řešící přístup k záznamům souboru s konstantní složitostí
**kolize** = situace, kdy je pro více záznamů spočítána stejná adresa
  * obvykle se řeší pomocí bucketů -- každé paměťové místo má předepsanou kapacitu záznamů, ve které se následně vyhledává lineárně 
</box>
Perfektní hašovací funkce -- hašovací funkce //h//, která je prostá.
Požadované vlastnosti hašovací funkce:
  * je deterministická
  * je rychlá  
  * vypočítává se z hodnot všech nebo alespoň většiny bitů klíče
  * pokrývá cílový prostor rovnoměrně





==== Statické hašování ====
  * používá se u souborů, které procházejí jen minimem změn
  * případné změny mohou negativně ovlivnit efektivitu hašování -- pokud se sejde na stejné adrese více záznamů než je kapacita bucketu, vyhledávání v rámci těchto záznamů má lineární složitost
==== Dynamické hašování ====
  * k výpočtu adresy se používá pouze prvních //i// bitů z výstupu hašovací funkce; toto //i// se dynamicky mění -- pokud je potřeba více adres, tak se zvyšuje, naopak při malém počtu se //i// zmenšuje
  * používá se u souborů s proměnným počtem záznamů
  * buckety jsou naplněné rovnoměrně -- pokud jsou plné, tak se štěpí, pokud jsou prázdné, tak se spojují
  * Druhy:
     * rozšiřitelné hašování
{{:home:prog:rozhas.jpg|}}
<note>
  * hašovací funkce rozmisťuje záznamy do kapes (kapsa = záznamy s jistou podmnožinou klíčů, vymezuje je hašovací funkce)
  * jako index v adresáři kapes se používá dynamicky určovaný prefix výsledku hašovací funkce **//h//(//k//)**
  * délku indexu vymezuje globální hloubka adresy kapsy
  * štěpení
    * globální hloubka > lokální hloubka -- na blok ukazuje více ukazatelů, jednoduše se rozdělí na dva
    * globální hloubka = lokální hloubka -- musí vzniknout nová kapsa a také se zdvojnásobí rozměr adresáře kapes
</note>
       * lineární hašování
<note>  
  * řeší nedostatky rozšiřitelného hašování za cenu vyšší režie dané manipulací s **přetokovými kapsami**
  * počet kapes udržuje tak, aby byly naplněny z např. 80 %
  * rozdíl oproti rozšiřitelnému hašování: **nemusí se vytvářet ani udržovat adresář kapes**, přesto počet kapes roste **lineárně**.
</note>





===== B stromy a jejich varianty =====
<box 90% round blue | Definice>**strom** = souvislý orientovaný acyklický (jednoduchý) graf
**B strom** = //m//-ární vyhledávací strom s omezujícími podmínkami (viz dále)
**B+ strom** = redundantní varianta B stromu</box>Vyhledávací B stromy a jejich varianty se používají pro efektivní ukládání a zpětné zpřístupňování dat. Nejčastěji jsou používány v databázích. Na B+ stromech jsou také založeny například souborové systémy XFS, ReiserFS či NTFS.

==== B strom ====
  * každý uzel až na kořen a listy má aspoň <math>\lceil m/2 \rceil</math> potomků
  * kořen má aspoň 2 potomky, pokud není jediným uzlem stromu
  * uzel s (//g// ≤ //m//) potomky obsahuje (//g// − 1) vyhledávacích klíčů
  * všechny listy jsou na stejné úrovni, v listu je max. **//m// − 1** klíčů
  * klíče se v celém stromu vyskytují právě jednou, záznamy jsou umístěny přímo v uzlech s klíči nebo jsou z nich adresované
  * vlevo od klíče je ukazatel na podstrom obsahující klíče menší než klíč v uzlu, vpravo od klíče je ukazatel na záznam a vedle něj ukazatel na podstrom obsahující klíče větší než klíč v uzlu
  * operace přidání, vyjmutí i vyhledávání prvku v B stromě probíhají v **logaritmickém čase**
{{:home:prog:bstrom2.jpg|}}

==== B+ strom ====
  * záznamy s daty jsou adresovány pouze z listů
  * vnitřní uzly B+ stromu hrají roli indexu k listům (vytvářejí víceúrovňový řídký index listů)
  * ve vnitřních uzlech se hraniční klíče mohou opakovat
  * Výhody oproti B stromům:
    * uzly jsou menší o ukazatele dat, strom jde více do šířky, průchod stromem je rychlejší
    * vkládání a rušení záznamů je snadnější, jednodušší je celá implementace B+ stromu
    * každý list obsahuje odkaz na následující list (tedy **listy jsou zřetězené**) -- umožňuje velice **rychlé procházení** celým stromem.
{{:home:prog:b_.jpg|}}

<note> 
** B* strom** -- Obdoba B stromu, která pracuje s uzly naplněnými minimálně do 2/3, místo 1/2 jako u klasického B stromu.

** B# strom ** -- Obdoba B+ stromu s povolenou rotací hodnot mezi sousedními uzly.
** Trie** -- Klíče jsou uchovávány na cestách z kořene k externímu uzlu a nikoliv jako celky v jednotlivých uzlech. (Trie **není** //m//-ární vyhledávací strom.)
{{:home:prog:trie.jpg|}}
</note>

===== Základy teorie informace =====
<box 90% round blue | Definice>**Teorie informace** = větev matematiky zabývající se efektivností a přesností uchovávání, přenosu a reprezentace informace
**Informace** = to, co přijímáme formou textů, řeči, obrazy... (zprávami)
  * informační objem zprávy je přímo úměrný entropii zprávy (méně pravděpodobná zpráva nese více informace)
**1 bit** = ekvivalent volby mezi dvěma stejně pravděpodobnými zprávami
</box90% round blue | Definice>

==== Entropie ====
**Entropie** je míra neurčitosti; snížením neurčitosti získáváme informaci, množství získané informace odpovídá velikosti odstraněné neurčitosti.
<box 90% round blue| Vzorec na výpočet entropie>

<math>H = - \sum^{M}_{i=1} P_{i} \log_{2} P_{i} [b/symbol]</math>

<math>P_{i}</math> je pravděpodobnost výskytu symbolu s měřenou informací

<math>M</math> je počet symbolů

<math>log_{2} P_{i}</math> je překvapení z výskytu daného symbolu i
</box>
<box 90% round blue| Maximální neurčitost>
Při stejné pravděpodobnosti výstupu každého z M symbolů je <math>P_{i} = \frac{1}{M}</math>
Maximální neurčitost potom je  <math>H_{max} = - \sum^{M}_{i=1} \frac{1}{M} \log_{2} \frac{1}{M} = \log_{2} M</math>
</box>

==== Kódování ====
**Kódování** = nahrazování jedné posloupnosti symbolů jinou posloupností symbolů (pořizování dat, šifrování, opravné kódy, komprese...).
  * Pro zobrazení každého symbolu zprávy potřebujeme alespoň <math>\log_{2} N</math> bitů, pokud nechceme snížit množství informace v zobrazené zprávě.
  * Kompresní teorém: Je-li **H** entropie zdroje, pak lze neztrátově komprimovat zdrojový text až do vyjádření každého symbolu v průměru H bity.
  * **Shannon-Fanovo kódování** -- využívá pravděpodobnosti výskytu jednotlivých prvků a rekurzivně rozděluje vždy na dvě skupiny s prefixem 0 či 1
  * **Huffmanovo kódování** -- symboly s vyšší pravděpodobností výskytu mají kratší kódová slova
 

Další kódování: Brailovo písmo, RLE kódování (náhrada opakujících se symbolů), Aritmetické kódování (pro malé abecedy)

===== Komprese dat =====
<box 90% round blue | Definice>**komprese dat** = proces identifikace a odstraňování redundance v datech </box>Cílem komprese je minimalizovat velikost komprimovaných dat, ať už pro ukládání nebo přenášení po síti.

**Dělení 1**
  - **neztrátová komprese** -- dekompresí se získají původní data (Huffmanovo kódování, Run-Length kódování...)
  - **ztrátová komprese** -- za cenu zefektivnění komprese se snižují nároky na přesnost rekonstrukce (MP3, JPEG...)
**Dělení 2**
  - **statická komprese** -- neměnný algoritmus, probíhá nezávisle na komprimovaných datech
  - **adaptivní komprese** -- dynamicky se měnící algoritmus, specifický pro komprimovaná data
**Dělení 3**
  - **fyzická komprese** -- ignoruje význam dat, odstraňuje se pouze formální redundance
  - **logická komprese** -- zohledňuje význam komprimovaných dat, obvykle se jedná o ztrátovou kompresi 

==== Typy kompresních metod ====
  - **základní (intuitivní) techniky** -- <color blue>Braillovo písmo, Run-Length kódování...</color>
  - **statistické metody** -- <color blue>Huffmanovo kódování, Shannon-Fanovo kódování...</color>
    * prvkům vstupní abecedy s větší pravděpodobností výskytu ve zprávě se přiřazují prvky výstupní abecedy kódované kratšími bitovými řetězci
    * **aritmetické metody**
      * každá posloupnost symbolů se reprezentuje značkou; množinou značek je interval <0;1); máme funkci, která mapuje posloupnost symbolů do tohoto intervalu
  - **slovníkové metody** -- <color blue>LZ77, LZ78, LZW...</color>
    * některé vzorky se vyskytují v mnoha typech dat; pokud se kóduje celý vzorek místo jednotlivých symbolů, které jej tvoří, bude kódovaný text kratší
  - **další** -- <color blue>MP3, JPEG, MPEG...</color>
    * věsměs specializované ztrátové kompresní metody na hudbu, obrázky a video


===== Předměty =====

[[https://is.muni.cz/auth/predmety/predmet.pl?kod=PV062;fakulta=1433;jazyk=cs|PV062: Organizace souborů]], doc. Ing. Jan Staudek, CSc.

===== Použitá literatura =====
[[http://www.fi.muni.cz/usr/staudek/vyuka/filesys/PV062.xhtml|Slidy předmětu PV062]], doc. Ing. Jan Staudek, CSc.
[[http://student.cvut.cz/cwut/index.php/Implementace_soubor%C5%AF_-_datov%C3%A9_bloky%2C_zp%C5%AFsoby_ulo%C5%BEen%C3%AD_atributy%2C_spr%C3%A1va_voln%C3%BDch_blok%C5%AF | Implementace souborů - ČVUT WIKI]] 

===== Kam dál =====
[[http://cs.wikipedia.org/wiki/B_strom|B strom WIKI]]
[[http://cs.wikipedia.org/wiki/B%2B_strom|B+ strom WIKI]]
[[http://cs.wikipedia.org/wiki/Komprese |Komprese WIKI]]
[[http://cs.wikipedia.org/wiki/He%C5%A1ov%C3%A1n%C3%AD|Hašovací funkce WIKI]]
[[http://en.wikipedia.org/wiki/Information_theory |Informační teorie EN WIKI]]
[[http://cs.wikipedia.org/wiki/Trie|Trie WIKI]]

==== Animace ====
B-Tree [[http://slady.net/java/bt/view.php]]
B+Tree [[http://www.seanster.com/BplusTree/BplusTree.html]]

===== Vypracuje =====


Otázku si přečetl pan RNDr. Vlastislav Dohnal a rámcově prošel. Jeho podněty pro doplnění textu, opravy nesrovnalostí a odstranění matoucích či k otázce se nevztahujících textů byly do otázky zaneseny. Tato kontrola je jen **rámcová**, stále se může stát, že v otázce zůstala zapomenutá chybka či nesrovnalost, vyučující za toto nenese odpovědnost, berte tuto rámcovou kontrolu jako formu pomoci od vyučujících pro studenty.

~~DISCUSSION~~