{{predmet|Organizace a zpracování dat I|Michal Žemlička|DBI007}}
= Přednáška – stručný přehled =
== Schémata organizace souborů ==
* '''hromada''' – nehomogenní soubor (nemá pevný typ záznamu s primitivními typy)
** pravěk
* '''sekvenční soubor''' – homogenní soubor uspořádaný dle nějakého klíče
** + sekvenčí přístup; - ''(minus)'' přístup k záznamům
* '''index-sekvenční soubor''' – sekvenční soubor + (víceúrovňový) index na blocích, příp. oblast přetečení
** + přístup k záznamům i sekvenční přístup
* '''indexovaný soubor''' ''(také invertovaný soubor)'' – primární soubor + více indexů na záznamech (klasický index, bitmapy, ..)
** + přístup k záznamům, k množině záznamů; - sekvenční přístup
* '''soubor s přímým přístupem''' – typicky ''hašování''
** + přístup k záznamům; - přístup k množině i sekvenční přístup
** perfektní (prosté) hašování
*** Cormack – 2-stupňové hašování přes pomocný adresář
*** Larson & Kalja – 2-stupňové hašování + signatury a separátory stránek
** dynamické hašování
*** s pomocným adresářem (Fagin)
*** bez adresáře – skupinové štěpení
** výcerozměrná mřížka (pro OLAP?)
== Popis jednotlivých algoritmov ==
=== Perfektné hashovanie - Cormack (beta) ===
Počet položiek (=veľkosť súboru): N
k: kľúč
s: veľkosť adresára
Hashovanie je realizované pomocou adresára (pomocou nejakej hashovacej funkcie), okrem toho sú potrebné aj ďalšie hashovacie funkcie
h<sub>i</sub>(k,r)=(k mod (2i + 100r +1)) mod r
Predpokladá sa, že k >> 2i+ + 100r +1. Okrem primárneho súboru používa hashovanie ešte jednu pomocnú "tabuľku" - adresár, ktorý vyzerá nasledovne:
{| border="1" cellpadding="0"
|+Adresár
|-
! pozícia !! p !! i !! r
|-
! 1
| || ||
|-
! 2
| || ||
|-
! ...
|-
! j
| adresa_v_primárnom_súbore || i<sub>j</sub> || veľkosť_bloku
|-
! ...
|}
Zadefinujeme si ešte nejaké dátové položky:
<code>
typedef head_1 {int p; int i; int r;}
typedef body_1 {int k; int v;}
head_1 *head=new head_1[s];
body_1 *body=new body_1[];
</code>
Primárny súbor obsahuje jednotlivé dátové štruktúry (body) v blokoch (ich veľkosť je daná položkou r v adresári)...
==== Vyhľadávanie ====
<code>
int h(int k, int s) {}
int hi(int i, int k, int r) {}
bool find(int k, int *v) {
j=h(k, s);
if (head[j].r==0) return false;
else {
body *p=body[head[j].p+hi(head[j].i, k, head[j].r)];
if (p->k!=k) return false;
else {*v=p->v; return true;}
}
}
</code>
==== Vkladanie ====
...je trošku zložitejšie, c-like algoritmus nech rozšíri niekto iný :-)
<code>
int free(int size) {/*nájde voľné miesto v primárnom súbore s veľkosťou size*/}
bool insert(body_1 d) {
j=h(d.k, s);
if (head[j].r==0) { //pre daný kľúč ešte nemáme alokovaný blok
int p=free(1);
body[p].k=d;
head[j].p=&body[p]; head[j].i=0; head[j].r=1;
} else {
Ak už je hodnota d.k v množine head[j].p - head[j].p+head[j].r, vráť false
Nájdi voľné miesto pre (head[j].r+1) prvkov
Nájdi i také, aby hashovacia funkcia hi vrátila pre každý z prvkov (pôvodný blok+d) rôznu adresu
Premiestni prvky zo starého umiestnenia na nové, zapíš nový prvok
Oprav adresár
}
}
</code>
=== Perfektné hashovanie - Larson & Kalja (beta) ===
* otvorené adresovanie s dvojitým hašhovaním a jedným prístupom
* používa tabuľku pomocných informácií, nazvime ju sep (povolenie), ktorá je podstatne menšia ako u Cormacka. Vyžaduje M*d bitov, kde M je počet stránok adresového priestoru, a d je veľkost pomocnej dátovej štruktúry (reťazec 0 a 1) - separátor/povolenie. Ďalej sa používa M hashovacích funkcií h<sub>i</sub>, ktoré pre každý kľúč vracajú postupne postupnosť adries tých stránok, kde je možné hľadať (vložiť) daný záznam; dalších M hashovacích funkcií s<sub>i</sub> generuje signatúry kľúča k .
Predstava:
Stránka:
+------+
| sep |
+------+-----+
| data sig | (PS: sig-signatúry záznamov si ukladať nemusíme, pomocou s<sub>i</sub> si ich dopočítame...)
| ... |
+------------+
Na začiatku sú všetky stránky prázdne...
1 2 3 M
+------+ +------+ +------+ +------+
| 1111 | | 1111 | | 1111 | | 1111 |
+------+-----+ +------+-----+ +------+-----+ +------+-----+
| | | | | | ... | |
| | | | | | | |
+------------+ +------------+ +------------+ +------------+
==== Vkladanie ====
0) i=1
1) Keď chceme pridať záznam (k), pomocou h<sub>i</sub>(k) zistíme umiestnenie stránky. Potom záznam zahashujeme pomocou s<sub>i</sub>, čím získame jeho signatúru.
2) Porovnáme povolenie/separátor stránky so signatúrou záznamu - ak je sep<=sig, i=i+1 a opakujeme od bodu 1.
3) Inak sme našli správnu stránku - pokúsime sa pridať do nej náš záznam. Záznamy v stránke usporiadame podľa signatúry (od zostupne - od najvačšej).
4) V prípade, že je záznamov v stránke priveľa (viac ako je veľkosť stránky): vyberieme (vymažeme zo stránky) záznamy s najvačšou signatúrou (teda všetky s rovnakou signatúrou z "vrchu" stránky), túto signatúru nastavíme ako separátor stránky, a vybrané záznamy znovu zahashujeme...
Pridanie jedného prvku (33, h<sub>1</sub>=4, s<sub>1</sub>=(001)b)...
4
+------+
| 111 |
+------+-----+
| data sig |
| 33 001 |
| |
+------------+
Pridanie ďalších dvoch (11, h<sub>1</sub>=4, s<sub>1</sub>=(101)b; 15, h<sub>1</sub>=4, s<sub>1</sub>=(001)b)...
4
+------+
| 111 |
+------+-----+
| data sig |
| 11 101 | <= stránka je plná, toto budeme musieť "vyhodiť"
| 33 001 |
| 15 001 |
+------------+
|
V
4
+------+
| 101 |
+------+-----+
| data sig |
| 33 001 |
| 15 001 |
+------------+
Hodnotu 11 budeme musieť zahashovat znovu, ale tentokrát už nie "pomocou" h<sub>1</sub>/s<sub>1</sub>, ale niektorých ďalších funkcií...
==== Vyhľadávanie ====
Viď bod 0-2 z pridávania :-)
== Stromy ==
* [[wikipedia:B-Tree|B-stromy]]
= Cvičení =
Triedenie veľkých objemov dát - [http://en.wikipedia.org/wiki/Heapsort heapsort] (vytváranie v lineárnom čase), ďalej optimalizácia jeho práce s pamäťou, a nakoniec [http://en.wikipedia.org/wiki/Mergesort zlievanie] (=mergesort)
= Odkazy =
* [http://kocour.ms.mff.cuni.cz/~zemlicka/vyuka/DBI007/ Žemličkove stránky k predmetu]
* [http://kocour.ms.mff.cuni.cz/~zemlicka/cz.html Žemličkove stránky]
