Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Statické metody organizace souboru

Definice (Schéma organizace souboru)

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

Poznámka (Časové odhady)

Pro schémata organizace souborů se počítají časové odhady provedení jednotlivých operací - jednodušších, jako je přístup k záznamu (), rewrite - přepis během 1 otáčky disku (), příp. sekvenční čtení; dále i složitějších jako vyhledání záznamu, přidání, smazání a úprava záznamu, reorganizace struktury nebo načtení celého souboru.

Hromada (neuspořádaný sekvenční soubor)

Hromada(heap) je naprosto nejjednodušší schéma organizace souboru, kdy jsou záznamy v souboru jen náhodně seřazeny za sebou. Časová složitost vyhledávání je , pokud je počet záznamů. Jde o nehomogenní soubor, kde záznamy obvykle nemají pevnou délku.

Uspořádaný sekvenční soubor

V uspořádaném sekvenčním souboru jsou záznamy řazeny podle 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. Složitost nalezení záznamu je také , 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 .

Index-sekvenční soubor

Toto schéma uvažuje primární soubor jako sekvenční, uspořádaný podle primárního klíče. Nad ním je pak vytvořen (třeba i víceúrovňový) index. Ten sestává ze seznamu čísel stránek a minimálních hodnot klíče jim odpovídajících záznamů. Pokud má index víc úrovní, provádí se pro vyšší úrovně to samé na blocích indexů úrovně o 1 nižší. Nejvyšší úroveň indexu se obvykle vejde do 1 bloku, tzv. master.

Počet potřebných úrovní pro záznamů se dá spočítat jako , kde při velikosti klíče a pointeru na stránku . Problémem je přidávání nových záznamů, kdy se tyto řetězí za sebe v tzv. oblasti přetečení (každý z nich má pointer na další záznam v oblasti přetečení). Pro oddálení nutnosti vkládání do oblasti přetečení lze iniciálně bloky plnit na méně než 100%.

Indexovaný soubor

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ě setříděný. 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.

Existuje i několik dalších variant indexů. Pro zmenšení náročnosti dotazů na kombinovanou částečnou shodu se používá kombinovaný index pro více atributů, u něhož je ale nutné předem zjistit na které kombinace atributů budou často pokládány dotazy, a pro takové kombinace tento index teprve vytvořit. Clusterovaný index zaručuje, že záznamy s podobnou hodnotou indexovaného atributu jsou blízko sebe v primárním souboru - např. pokud je primární soubor podle tohoto atributu setříděny. Tento index lze použít jen pro 1 atribut.

Bitové mapy se dají použít jako index pro atributy s malou doménou (množinou možných hodnot) - pro každou hodnotu této domény se vyrobí vektor bitů stejné délky, jako je počet záznamu v primárním souboru, kde jednička na -té pozici indikuje, že -tý záznam má právě tuto hodnotu atributu. To umožňuje jednoduché provádění booleovských dotazů na tento atribut. Vektory bitů navíc lze komprimovat, takže nezabírají tolik místa.

Soubor s přímým přístupem

V tomto schématu jsou záznamy v primárním souboru (adresovém prostoru velikosti ) rozptýleny pomocí hashovací funkce. Často se používá funkce , kde je nejbližší prvočíslo menší než velikost adresového prostoru. Hashovací funkcí se určuje buď jenom číslo stránky, nebo i relativní pozice v ní. Při hashování vznikají kolize, které se dají řešit otevřeným adresováním (řetězením kolizních záznamů za sebe), rehashováním (další funkcí) nebo použitím oblasti přetečení. Snaha je většinou umístit kolizní záznamy do stejné stránky.

Pokud je hashovací funkce prostá, jedná se o perfektní hashování. Toho ale v praxi vlastně nelze dosáhnout, takže se tento výraz používá i pro označení stavu, kdy je pro nalezení záznamu potřeba nejvýš přístupů k médiu. Očekávaná délka řetězce kolizí při počtu záznamů v prostoru velikosti je .