Přehled látky probrané na přednášce Organizace a zpracování dat I.

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í hešovaní (Cormack)

Cormakovo hašování je založeno na existenci primární hašovací funkce $h(k)$, a celé třídy sekundárních hašovacích funkcí $h_i(k,r)$. funkce $h(k)$ musí mít obor hodnot roven velikosti adresáře.

Položky jsou ukládány do primárního souboru (pevné velikosti), způsobem, který bude popsán za pomoci adresáře (pevné velikosti). Protože je i primární soubor i adresář pevné velikosti, řadí se Cormacovo hašování do tzv <statické%20metody%20hasšování>.

Primární soubor si jde představit jako pole pevné velikosti. Adresář vypadá následujícím způsobem:

Význam položek

Příklad 1.

Jak funguje vkládání

Příklad 2.

Jak funguje vyhledávání

Pseudokód

Vyhledávání

Vkládání

Perfektné hashovanie - Larson & Kalja (beta)

Vkladanie

Vyhľadávanie

Stromy