{{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 ===
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)...
Postup vyhľadávania v hashovaní:
<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
}
ak
}
</code>
== 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]