Syntax highlighting of Archiv/Organizace a zpracování dat I

{{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 &gt;&gt; 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
     }
 }
</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]