Cvičení předmětu KIV/DB1
2. týden výuky, cvičící: Ing. Tomáš Kotouč

Na této stránce se ještě pracuje

Seznamová organizace dat, Invertová organizace dat

• Organizace dat
  • Jedná se o prostředek k rychlejšímu vyhledání požadovaného záznamu.
  • Každá z organizací má své výhody a nevýhody. Nejhlavnější hlediska, podle kterých se organizace posuzují jsou rychlost, kterou se dostanu k požadované informaci a množství obsazeného prostoru.
  • Při výběru dané organizace nezáleží jen na poměru rychlosti a množství obsazeného prostoru, ale záleží také na druhu dat = jestli jsou hodnoty, podle kterých se záznamy řadí, jedinečné nebo se opakují.
  • My se nyní budeme zaobírat Seznamovou organizací, Invertovou organizací a B-strom. Existují i další organizace, ale ty nás natolik nezajímají. Prezentované organizace se používají pro organizaci velkého množství záznamů a představují hlavní organizace používané ve velkých databázích k zrychlenému přístupu k datům, tzv. indexy.

• Seznamová organizace dat
  • Máme nějaký soubor dat.
    
  • Na záznam, který obsahuje nejnižší hodnotu nám ukazuje hlavička. Abychom věděli, kam hlavička ukazuje, je nutné aby každý záznam měl své číslo, aby záznamy byly očíslovány = měli svou adresu.
    
  • Logicky sousední věty jsou spojeny ukazovátkem, který se vyskytuje přímo v souboru jako další slopec = jednocestný seznam.
    
  • Když nyní chceme vyhledat určitý záznam s určitou hodnotou, začneme hlavičkou, zjistíme kam ukazuje, přejdeme na tento záznam, zjistíme zda se jedná o danou hodnotu, pokud ne, tak přejdeme na záznam, na který daný záznam ukazuje a takto se daná operace opakuje, dokud nenalezneme požadovaný záznam.
  • Když nyní chceme přejít na předchozí záznam, musíme v jednocestném seznamu problém, protože na předchozí záznam nám neukazuje žádné ukazovátko a musíme projít celou strukturu znovu od hlavičky. Toto se dá odstranit zavedením dvoucestného seznamu. U dvoucestného seznamu nám přibude i další "hlavička", která ukazuje na poslední záznam, takže ji spíše nazýváme patičkou.
    
  • Pokud se v systému vyskytují záznamy se stejnou hodnotou, můžeme z hlavičky a patičky udělat soubor hlaviček a patiček, u kterých vždy evidujenme hodnotu, kterou tento seznam představuje.
    
  • INSERT = záznam přidám na libovolné místo takže např. na konec souboru a včlením ho do seznammu. Někdy se nevčleňuje hned na správné místo, ale pouze na začátek či konec seznamu a k setřídění dochází až při nižším zatížení aplikace (v noci).
  • UPDATE = změní se hodnota, seznam se příslušně přeorganizuje podle nové hodnoty.
  • DELETE = záznam se označí a vyřadí ze seznamu, smaže se až při nižším zatížení aplikace (v noci).
  • Rychlost versus datový prostor = nižší vyhledávací rychlost, méně náročný na paměť.

• Invertová organizace dat
  • Máme opět nějaký soubor dat, např. tabulku pracovníků s jejich zařazením na pracoviště.
    
  • Pro každý klíč tohoto souboru se vytváří tzv. invertovaný soubor (= indexová tabulka).
    
  • Tento typ invertovaného souboru má jednu nevýhodu a to nestejnou délku věty = to není vhodné pro rychlý výběr. Toto lze vyřešit přesunem seznamu výskytů do oficiální oblasti zvané tabulka výskytů.
    
  • Invertovaný soubor se nemusí pořizovat pouze pro jeden sloupec, může být vytvořeno několik invertovaných souborů pro několik sloupců.
  • Úplný invertovaný soubor = pro všechny sloupce tabulky jsou vytvořeny invertované soubory.
  • SELECT
    • Sekvenční = projdu pomocí invertovaného souboru vytvořeného pro primární klíč.
    • Náhodný = nemusí se ani použít invertovaný soubor.
  • INSERT = nový záznam uložíme na libovolné místo a upravíme invertovaný soubor (aktualizace invertovaného souboru a zatřídění do tabulky výskytů).
  • UPDATE = změna hodnoty a tím pádem i změna příslušného invertovaného souboru.
  • DELETE = označení záznamu a vyřazení jen z invertovaného souboru. Tím pádem je záznam nedostupný. Z vlastní tabulky se smaže např. v noci. Vhodný pro tabulky s několikanásobným výskytem stejných hodnot.
  • Rychlost versus datový prostor = poměrně vysoká vyhledávací rychlost, náročnější na paměť.