Lucka Žoltá

Datové struktury

Datové struktury se skládají buďto ze stránek, nebo z uzlů v případě stromové struktury. Jsou realizovány tak aby operace vyhledávání, vkládání, editace a mazání byly co nejefektivnější. 

Pro rychlé vyhledávání, které předchází i editaci a mazání je nutné udržovat datovou strukturu setříděnou. To však může zpomalit operaci vkládání (např. zařazením nového záznamu do prostřed tabulky musím posunout milion záznamu).

Výpis příkazu chkdks, ukazuje že disk F: je členěn do bloků o velikosti 4kB. Těchto bloků má na disku 122 milionu => disk má velikost akoro půl Terabajtu (4kB * 122 = 488kB)

Blok (alokační jednotka) - je nejmenší jednotka s kterou SŘBD manipuluje při zápisu a čtení dat z disku (obvykle 4KB nebo 8KB).

Stránka - nejmenší jednotka s kterou pracuje správce paměti. Stranka.velikost = X * Blok.velikost (je-li velikost bloku = 4KB je odpovídá velikost stránky násobkům 4KB)

Datový soubor - fyzický prostor na disku s daty.

Indexy - tabulka setříděna podle daného atributu. Jde o soubor obsahující setříděný indexovaný atribut a ukazatel do datového souboru, kde je daný záznam uložen.

Stránkování

Jak ho chápu já...

Tato struktura pracuje s daty rozdělených do stránek (bloků?). Takže nepracujeme s tabulkou o milionech záznamech jako s celkem, ale načteme s jejíma stránkami, která mají třeba jen 20 záznamů. 

Na obrázku vpravo je ukázka tabulky indexované (řazené) podle atributu název. Je rozdělená na dvě stránky. Díky indexaci bude vyhledávání podle názvu v této tabulce rychlé. Díky stránkování nebude ani problém s vkládáním nových záznamů. Volné místa na konci stránek slouží k rychlé manipulaci s daty. V případě vložení nového záznamu např. Borovice nebudu muset posunovat všechny záznamy, ale stačí posunout jen Dub. V případě že už není v rámci stránky kam posunovat, není problém do struktury vložit novou stránku a třeba půlku dat z první stránky do ní přemístit.

Stromové struktury

Stromové struktury, ukládají data do grafů zvané stromy. Stromy jsou grafy bez cyklů s kořenem. Uzly obsahují hodnotu a hrany na další podstomy. kde jsou vůči danému uzlu hodnoty setříděné. Výběr ve stromových strukturách je velmi rychlý, pokud stromy nedegradují na jednu větev (strom se rozrůstá jedním směrem, místo aby se pěkně košatil). Pak se při vyhledávání zvyšuje počet zanoření a rychlost vyhledávání klesá. Z toho důvodů existují metody které se starají o to aby byl strom vyvážený. V případě že se začne rozrůstat jedním směrem jej přeskládají aby snížily jeho úrovně.

Ukázka binárního a B- stromu

 

Binární strom

Strom jehož uzly nesou hodnotu U a dále mají maximálně dva potomky levého a pravého, které tvoří kořeny podstromů. Levý podstrom obsahuje prvky menší než hodnota U a pravý podstrom hodnoty vetší (a nebo naopak, záleží na implementaci). 

B-strom

Je obecnější varianta binárního stromu. Místo jedné hodnoty obsahují uzly pole hodnot a podle velikosti toho pole pak příslušný počet vazeb na podstomy.

B-strom x-tého řádu má v uzlech pole velikosti x*2 a tedy maximálně x*2+1 dětí (vazeb na podstromy).

Ukázka vkládání do vyváženého B-stromu

R-strom

Slouží pro zachycení vícerozměrných datových struktur. Používá se v případě, kdy potřebujeme dělat vyhledávat na základě více atributů. Data uchovává v jakýsich prostorových shlucích, které jsou pak uspořádané ve stromové struktuře. Jak je znázorněno na obrázku dole.

Pro situaci v příkladu by se normálně k takové tabulce musely být dva evidovat indexy (dva B-stromy) jeden setříděný podle atributu město a druhý podle věku, což zabere hodně místa. A i tak by byl tento dotaz náročný, protože výsledky jednotlivých části podmínky by byly obrovské (první část vyplivne všechny lidi z Ostravy, druhá z Opavy, poslední pak všechny lidi starší 60let) a sloučení tak velkých celků je rovněž velmi náročné.

Pokud však použijeme reprezentaci R-stromem jak je znázorněné na obrázku vpravo, bude stejný dotaz otázkou dvou zanoření do stromu a výsledek je na větě.