AP12 Organizace souborů

(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)

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

• 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

• 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:
Ukázka uspořádaného sekvenčního souboru – ř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

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

• 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í

• 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: { vyhledávací klíč ; ukazatel na záznam }
• 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

Obvykle pokud se mluví o indexech, jsou myšleny řádné.
Dělení 1

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ý
2. 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
ří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

1. volné formátování – sekvenčně řazené záznamy pevné i proměnlivé délky
2. 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…)

1. souvislá alokace datových bloků
   • soubor je na disku uložen v souvislé posloupnosti datových bloků
2. alokace datových bloků pomocí zřetězeného seznamu
   • každý datový blok obsahuje data a ukazatel na následující datový blok
3. 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
4. i-nodes
   • i-node je struktura, která obsahuje jak atributy souboru, tak adresy datových bloků, ve kterých je uložen obsah souboru

Motivace: změny dat neznamenají velké (globální) reorganizace, které jsou drahé, ale spíše reorganizace lokální.

1. B-strom
2. dynamický haš soubor
   • založený na rozšiřitelném hašování nebo lineárním hašování

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ě

• 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

• 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í

• lineární hašování

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.

• každý uzel až na kořen a listy má aspoň 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

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

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.

Maximální neurčitost

Při stejné pravděpodobnosti výstupu každého z M symbolů je Maximální neurčitost potom je

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ň 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)

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

1. neztrátová komprese – dekompresí se získají původní data (Huffmanovo kódování, Run-Length kódování…)
2. ztrátová komprese – za cenu zefektivnění komprese se snižují nároky na přesnost rekonstrukce (MP3, JPEG…)

Dělení 2

1. statická komprese – neměnný algoritmus, probíhá nezávisle na komprimovaných datech
2. adaptivní komprese – dynamicky se měnící algoritmus, specifický pro komprimovaná data

Dělení 3

1. fyzická komprese – ignoruje význam dat, odstraňuje se pouze formální redundance
2. logická komprese – zohledňuje význam komprimovaných dat, obvykle se jedná o ztrátovou kompresi

1. základní (intuitivní) techniky – Braillovo písmo, Run-Length kódování…
2. statistické metody – Huffmanovo kódování, Shannon-Fanovo kódování…
   • 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
3. slovníkové metody – LZ77, LZ78, LZW…
   • 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ší
4. další – MP3, JPEG, MPEG…
   • věsměs specializované ztrátové kompresní metody na hudbu, obrázky a video

PV062: Organizace souborů, doc. Ing. Jan Staudek, CSc.

Slidy předmětu PV062, doc. Ing. Jan Staudek, CSc.
Implementace souborů - ČVUT WIKI

B strom WIKI B+ strom WIKI Komprese WIKI Hašovací funkce WIKI Informační teorie EN WIKI Trie WIKI

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

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.