Metody uložení dat
Doc. Dr. Vladimír Homola, Ph.D.
Problematika uložení dat je problematikou proto, že se data ukládají na lineárním fyzickém mediu. Paměť počítače je lineární posloupnost paměťových prvků adresovaných od nuly. Magnetická páska je lineárním mediem už z fyzikální podstaty. Disky a diskety z různou technickou konstrukcí jsou jednotným vzorcem linearizovány na shodnou (nanejvýš různě dlouhou) posloupnost paměťových elementů. Data z klávesnice jsou linearizována reálným časem (jak postupně v čase přichází "do počítače") apod. Datové struktury však lineární zdaleka být nemusí.
V celé této kapitole se nadále pod pojmem paměť bude rozumět jakékoliv shora naznačené linearizované medium schopné "zapamatovat si" data.
Toto uložení je charakteristické tím, že při uložení záznamů využívá paměť od počátku (= od adresy nula) a bez mezer. Volná zůstávají paměťová místa s nejvyššími adresami v případě, že objem dat je menší než kapacita paměti.
Další rozlišovací úrovní postupného uložení dat je jejich uspořádání v paměti.
Sekvenční uložení je takové, při němž se záznamy ukládají v pořadí, jak v čase přicházejí - tvoří vstupní sekvenci. Pokud je zapotřebí nějaký záznam najít, je nutno projít všechny záznamy od počátku.
Při sériovém uložení řídí pořadí záznamů hodnota nějakého klíče - posloupnost klíčů tvoří uspořádanou sérii. Záznam s nejmenší (největší) hodnotou je prvním záznamem, záznam s největší (nejmenší) hodnotou je poslední. Řazení dat je vzestupné (sestupné).
Vyhledávání záznamů se v sériovém uložení velmi zjednoduší. Největší nevýhodou je nutnost fyzicky reorganizovat záznamy, když dojde požadavek na přidání nebo vypuštění záznamů (nebo ke změně hodnoty klíče záznamu).
Z ostatních typů se občas používá řazení podle četnosti vyhledávání. Vyhledávání je pak celkově rychlejší než při sekvenčním uložení. Je však podmíněno jednak znalostí této četnosti (nutnost experimentů), jednak stálosti této četnosti v čase.
Zásadní rozdíl oproti postupnému uložení je v tom, že mezi jednotlivými záznamy mohou být mezery a že jsou uloženy bez ohledu na nějaké uspořádání.
Při zápisu dat rozptýleného uložení se používají dvě metody:
Je jedno, kam bude zapisovaný záznam uložen. Proto se uloží do kteréhokoliv volného, délkově vyhovujícího místa v paměti. Tato metoda - má-li být rozumně rychlá a efektivně využívat paměť - používá pomocnou evidenci volného místa v paměti; z této evidence lze kdykoliv zjistit adresy a velikosti volných míst. Při zápisu se pak pomocí této evidence volí optimální strategie ukládání - např. se nejprve hledá přesně stejně veliké volné místo, jako má zapisovaný záznam.
Místo, kam bude záznam zapsán, se určí na základě obsahu záznamu. V naprosté většině se k tomu používá hodnot klíčů. Existuje tedy zobrazení množiny hodnot klíčů do množiny adres. Toto zobrazení nemusí být prosté. Funkce taková zobrazení definující se nazývají Hash - funkce.
Příklad: Nechť každý z 13 vrtů v terénu má číselný kód od 1 do 13 (vrty jsou tedy "očíslovány"). Nechť délka záznamu obsahující údaje o každém vrtu je 67. (První závěr: pro uložení těchto dat je zapotřebí minimálně 13 x 67 = 871 elementů paměti, tzn. např. adresový prostor <0,870>). Funkce A
A = A (v) = (v-1) * 67
kde v je kód vrtu, je hash - funkce, která každému záznamu s daným číslem vrtu přiřadí adresu uložení, která je z intervalu <0,804> (804 = 871 - 67). Tato funkce je prostá (dva různé vrty jsou umístěny na dvě různá místa). Funkce není zobrazením množiny kódů <1,13> na interval <0,804>, ale jen do tohoto intervalu (obrazy jsou jen počáteční adresy záznamů).
Tato metoda kombinuje sériové a rozptýlené uložení. Při primárním vytvoření je soubor vytvářen sériově (tj. ve vzrůstajícím nebo klesajícím pořadí klíčů) s ohledem na Hash - funkci. Nově přidávané záznamy jsou - většinou rozptýleným způsobem - zapisovány do tzv. zóny přeplnění (overflow area).
V případě, že v souboru může existovat větší či menší počet záznamů se stejnou hodnotou klíče, modifikuje se metoda tak, že jsou vytvářeny tzv. skupiny záznamů (záznamy se stejným klíčem), přičemž se předpokládá stejnoměrné rozdělení četnosti výskytu. Proto se každé skupině vyhradí stejné místo. Záznamy se stejným klíčem jsou zapisovány sekvenčně v prostoru paměti vyhrazené skupině a jednotlivé skupiny jsou zapisovány sériově v prostoru paměti vyhrazené skupinám. Dojde-li během zápisu záznamu do skupiny k vyčerpání místa určeného skupině, zapisují se tyto záznamy do zóny přeplnění.
Viz rovněž metody nepřímé adresace pro hledání v datech.
V moderních databázových (zvláště relačních) systémech jde o jedno z nejužívanějších uložení. Zásadně se týká záznamů, pro něž je definován alespoň jeden klíč.
Jde v podstatě o tzv. uložení s odkazy. Kromě záznamů jsou ukládány také odkazy na ně. Tyto odkazy však nejsou většinou ukládány přímo v datovém souboru, ale v samostatných souborech.
Při tomto způsobu uložení jsou data záznamy ukládány sekvenčně do souboru dat. Zároveň je pro každý záznam dat vytvořen záznam indexu. Záznam indexu má dvě pole: prvním je hodnota klíče daného záznamu, druhým je adresa v souboru dat, počínaje kterou byl tento záznam uložen. Takto vytvořený záznam indexu je zapsán do souboru indexů. Záznamy týkající se jednoho klíče jsou souhrnně označovány jako indexová tabulka. Každá indexová tabulka může být uložena v samostatném souboru, nebo mohou být všechny indexové tabulky uloženy v jediném souboru (nebo některé tabulky v jednom, některé v jiném souboru apod). Tyto soubory se nazývají indexové soubory.
Soubor indexů mívá nejrůznější organizaci (snad kromě sekvenční). Nejčastěji to bývá struktura s odkazy nebo jiné rozptýlené uložení, méně často uložení sériové.
Zvláště pro velké objemy dat je tento způsob uložení jedním z nejefektivnějších z hlediska využitého paměťového prostoru i (při vhodně zvolené metodě hledání v indexových souborech) při zpracování přímým způsobem.
Efektivita při ukládání spočívá jak v časovém hledisku (data jsou ukládána bez jakékoliv další reorganizace souboru vždy přímo na konec souboru), tak v hledisku hospodárnosti (v datovém souboru nejsou nevyužitá místa). Nutnost zpracovat současně i indexové soubory však je daleko menším zatížením, protože jednak jsou záznamy indexového souboru krátké (pouze dvě pole oproti např. desítkám polí vlastního datového souboru), jednak mohou být organizována zcela odlišně od vlastního souboru dat. Navíc, protože jsou poměrně málo objemné, mohou být celé umístěny v operační paměti, čímž se jak vytváření, tak zpracování dále nesmírně urychlí.
I když to není vždy pevným pravidlem, jde nejčastěji o sekvenční uložení záznamů, přičemž se při ukládání provádí dodatečné akce.
Odkazem se rozumí takový údaj v záznamu, který popisuje, kde se nachází jiný záznam; pro jednoduchost bude nejprve popsána situace, kdy tímto jiným záznamem je (logicky) další záznam. Odkaz je tedy datové pole, které však na rozdíl od běžných polí nenaplňuje uživatel, ale obslužný program.
Poznámka: Protože vztah před - za je binární operací porovnávání, musí být pro záznamy takovým způsobem ukládané definován výraz, nad jehož hodnotami se porovnávání provádí. Takový výraz je (viz výše) klíčem záznamu.
Odkazem může být např.
adresa v paměti (např. disková adresa)
pořadové číslo záznamu (program si pořadové číslo převede na adresu v paměti)
symbolický odkaz (program musí mít k disposici prostou hash-funkci)
Při popisované organizaci uložení existuje jedna hodnota odkazu (většinou označovaná NIL), která "neukazuje nikam". Tato hodnota je volena tak, že jí nemůže nabýt žádná reálná adresa, pořadové číslo nebo odkaz. Touto hodnotou musí být např. obsazen odkaz logicky posledního záznamu, protože za ním "už nic není".
Při popisu struktury s odkazy se používá pro vyznačení vztahu mezi dvěma bezprostředně souvisejícími záznamy zřejmá terminologie: předchůdce - následovník, nadřízený - podřízený, rodič - dítě. Poslední termíny (angl. parent record - child record) se používá snad nejčastěji.
Záznamy se zapisují tak, jak přichází; z tohoto hlediska jde o sekvenční organizaci. Při ukládání záznamů se při této organizaci postupuje následovně:
První příchozí záznam se zapíše jako první, přičemž pole odkazu na další se naplní hodnotou NIL. V tomto okamžiku je totiž první záznam také záznamem logicky posledním, za ním "už není nic".
Druhý příchozí záznam se zapíše jako druhý. Nyní však mohou nastat dvě situace:
Klíč druhého záznamu je větší nebo roven klíči prvního záznamu. Jinak řečeno, druhý záznam je logicky za prvním záznamem. Proto je nutno pole odkazu na následníka v prvním záznamu (doposud NIL) přepsat odkazem na druhý záznam, a pole odkazu na následníka ve druhém záznamu obsadit hodnotou NIL (druhý záznam se stává záznamem posledním).
Klíč druhého záznamu je menší než klíč prvního záznamu. V tom případě první záznam zůstává logicky posledním záznamem (v poli odkazu na následníka zůstává NIL), kdežto druhý záznam je prvním logickým záznamem, je před prvním záznamem, proto pole odkazu na následníka druhého záznamu se obsadí odkazem na první záznam.
Třetí příchozí záznam se zapíše jako třetí. Teď nastane jedna ze třech situací: třetí záznam je před prvním, mezi prvním a druhým, nebo za druhým. Upraví se tedy pole odkazů na následníka jen ve třetím záznamu, v prvním a třetím, nebo ve druhém a třetím.
Takovým způsobem se postupuje dále. Je zřejmé, že při zápisu každého dalšího záznamu se musí najít v již zapsaných záznamech dva klíče, mezi které klíč nově příchozího záznamu patří, tam stávající řetěz odkazů "rozpojit" a (pomocí odkazů) tam vložit nově příchozí záznam.
Velmi jednoduché je však logické vypuštění záznamu. Obsah pole odkazu na následníka vypouštěného záznamu se prostě přepíše do pole odkazu předchůdce.
Výše byl popsán způsob vytváření odkazu na následovníky. Zcela stejně se může vytvořit druhé pole odkazu v záznamu, odkaz na předchůdce. V tomto případě je hodnota NIL hodnotou odkazu na předchůdce logicky prvního záznamu.
Sousedem záznamu A je takový záznam B, který má stejný klíč jako záznam A. Stejně jako odkazy na předchůdce a následovníka mohou být v záznamech pole odkazů na sousedy. Z hlediska popisované metody je dále možno rozdělit sousedy na levé a pravé. Levý soused je ten, který je zapsán dříve, pravý soused je zapsán později. Tedy "nejlevější" soused má odkaz na levého souseda obsazený hodnotou NIL, "nejpravější" soused má hodnotou NIL obsazený odkaz na pravého souseda.
Tato metoda již ve fázi ukládání používá metod pro hledání; vlastní ukládání tedy probíhá daleko pomaleji než např. prostý sekvenční zápis. Je to však na podporu pozdějšího zpracování souboru, které se stává daleko efektivnějším. Protože se soubor vytváří jen jednou, ale zpracovává násobně, je tato metoda často využívána.
Poznámka: Soubory s indexy jsou takovým případem souboru s odkazy, kdy odkazy spolu s hodnotami klíčů jsou uloženy v samostatném souboru.
Rev. 11/2007