hashovací struktura se nevejde do hlavní paměti (RAM), efektivnost se počítá podle počtu přístupů k blokům v externí paměti (HDD)
=== Statické hashovací metody ===
* hashovací fce mapuje klíče do fixního počtu adres/stránek
* umožňují přidávat klíče ale neumožňují rozšiřovat adresní prostor bez přehashování celého indexu
* vhodné pro statické databáze
==== Cormack (perfektní hashování) ====
[[Soubor:Cornack.PNG|thumb|Pre pristup najprv vypocitame riadok s adresata funkciou ''h''(''k'') = ''j'' . Adresa v hlavnom subore bude potom ''j.p'' + ''h''ⱼᵢ (''k'', ''j.r'')|344x344px]]
V vyzdvyhnutiu lubovolneho zaznamu su potrebne najviac dva pristupy na disk. Ak je adresar ulozeny v pamati tak potom jeden.
'''Potrebujeme''':
* '''Hlavnu hashovaciu funkciu ''h''(''k'')''' ktora vracia [0...''n''] Pre pristup k riadku adresara
* '''Pomocnu hashovaciu funkcia ''h''ᵢ(''k'', ''r'')''' vracia hodnotu s ⟨0, ''r'' - 1⟩ napr ''h''ᵢ(''k'', ''r'') = (''k'' mod (2''i'' + 100''r'' + 1)) mod ''r''
* '''Adresar '''( Velkost '''O(''n'')''' kde ''n'' je velkost suboru ) ktory obsahuje parametre druhej hashovacej funkcie ( ''p'' : index do primarneho adresara, ''i'' index hashovacej funcie , ''r'' pocet miest na kolko hashovacia funcia ''h''ᵢ prvky hashuje)
* '''Primarny subor''' obsahuje data a je ulozeny na disku.
'''FIND''': Pre pristup najprv vypocitame riadok s adresata funkciou ''h''(''k'') = ''j'' . Adresa v hlavnom subore bude potom j.p + ''h''ⱼᵢ ( ''k'', ''j.r'' )
'''INSERT''': Vsetky hodnoty adresara su na zaciatku 0.
* Zistime riadok adresara
** Ak je prvy najdeme pre neho volne miesto , ulozime ho a zauktualizujeme adresar
** Ak nieje prvy zobereme kolidujuce zaznamy a pozrieme ci nemame koliziu. Ak nie najdeme novu funciu ktora bude mat obor hodnot tak aby sme zaheshovali ''n'' + 1 prvkov , najdeme volne miesto a zaktualizujeme adresar.
[[Soubor:Fagin.PNG|thumb|Faginovo hashovanie pre hlbku adresara 2|224x224px]]
=== Dynamické hashovací metody ===
* umožňuje dynamický nárůst adresního prostoru pomocí dynamické hashovací fce
* vhodné pro db s měnící se velikostí
==== Fagin (rozšiřitelné adresářové hashování, Koubkovo "externí hashování") ====
'''Potrebujeme'''
* '''Adresar '''( Obsahuje ukazovatele / nie nutne unikatne / na stranky dat v na disku ; hlavicku v ktorej je ulozena hlbka adresara 0 < ''d ''< ''r'') / aky pocet bitov sa bere s pseudokluca)
* '''Hashovaciu funkciu pre pseodukluc ''h''(''k'')'''. Pseodukluce maju vsetky rovnaku dlzku r
* '''Stranky na disku''' , stranka obsahuje lokalnu hlbku ''d`''. Ak ''d` ''< ''d'' tak na jednu stranku vedie viac ukazovatelov
'''FIND:'''
* Spocitame pseodukluc ''k` ''= ''h''(''k'')
* Vezmeme hlbku adresata (''d'') a precitame prvych ''d'' bitov s pseodokluca ( nazveme to ''p'')
* Zobereme ukazovatel, ktory je umieneny v ''p.v'' ( ''v'' je velkost kazdeho pointra v bytoch ) ⇒ vedie na hladanu stranku
'''INSERT: '''Když se stránka naplní, rozštěpím ji na 2 podle dalšího bitu hash-funkce. Pokud už stránka používá stejně bitů jako adresář, musím zvětšit o 1 bit i adresář.[[Soubor:Litwin.PNG|thumb|Schéma štěpení při lineárním hašování]]
==== Litwin (lineární bezadresářové hashování) ====
Nevyužívá adresář, ale '''potřebuje oblast přetečení''' a tedy není zaručeno, že se ke všem datům dostaneme v 1 přístupu na disk. Data uložena ve stránkách.
Stránky jsou štěpeny nezávisle na tom, kde došlo ke kolizi, kruhovým schématem (viz obrázek). Po každých L (L je parametr metody) vloženích je rozštěpena 1 stránka. Když dochází ke štěpení stránky, přidáme 1 stránku na konec '''úložiště stránek''' . Záznamy ze štěpené stránky (a případné z oblasti přetečení, které by patřily do štěpené stránky) jsou potom rozděleny mezi novou a štěpenou stránku.
'''FIND:''' ''h''(''k'') = ''k`'' (pseudoklíč má na rozdíl Fagina podle posledních bitů a jeho délku spočítá podle počtu všech stránek, pokud tam není hledáme v obl.přetečení)
'''INSERT:''' najdi místo pomocí FIND a pak vložíme, pokud se nevejde tak nacpeme do oblasti přetečení, po L INSERTech štěpíme a podle posledních bitů rozdělíme záznamy
Růst primárního souboru je lineární ⇒ lineární hashování
{{collapse|Příklad|
<pre>
Hasovaci fce - v nasem pripade pouze prevod z desitkove do dvojkove soustavy
Vysvetlivky:
b = 3 ...velikost bloku
l = 2 ...po kolika insertech se ma stepit stranka
Vkladane hodnoty:
12, 5, 4, 1, 3, 2, 7, 14
i(12):
┌────┐ Kdyz mame jedinou stranku (do 1. stepeni), vkladame do ni
│ 12 │ vsechny hodnoty (nezalezi na poslednim bitu).
│ │
│ │
└────┘
i(5):
┌────┐
│ 12 │
│ 5 │
│ │
└────┘ "oznaceni stranky" - posledni bit(y) cisel ve strance maji
├──────┐ / tuto hodnotu
│ 0 │ 1
┌────┐ ┌────┐ Protoze l=2 a vlozili jsme druhy prvek, dojde ke stepeni.
│ 12 │ │ 5 │ Podle posledniho bitu cisel se rozhodne, do
│ │ │ │ ktere pujdou stranky.
│ │ │ │
└────┘ └────┘
i(4):
0 1
┌────┐ ┌────┐
│ 12 │ │ 5 │
│ 4 │ │ │
│ │ │ │
└────┘ └────┘
i(1):
0 1
┌────┐ ┌────┐
│ 12 │ │ 5 │
│ 4 │ │ 1 │
│ │ │ │
└────┘ └────┘
├──────────────┐
│ 00 1 │10
┌────┐ ┌────┐ ┌────┐ Vlozili jsme 4. prvek - dochazi ke stepeni.
│ 12 │ │ 5 │ │ │ Hodnoty rozdelujeme podle poslednich dvou
│ 4 │ │ 1 │ │ │ bitu.
│ │ │ │ │ │
└────┘ └────┘ └────┘
i(3):
00 1 10
┌────┐ ┌────┐ ┌────┐
│ 12 │ │ 5 │ │ │
│ 4 │ │ 1 │ │ │
│ │ │ 3 │ │ │
└────┘ └────┘ └────┘
i(2):
00 1 10
┌────┐ ┌────┐ ┌────┐
│ 12 │ │ 5 │ │ 2 │
│ 4 │ │ 1 │ │ │
│ │ │ 3 │ │ │
└────┘ └────┘ └────┘
├──────────────┐
00 │ 01 10 │11
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ 12 │ │ 5 │ │ 2 │ │ 3 │
│ 4 │ │ 1 │ │ │ │ │
│ │ │ │ │ │ │ │
└────┘ └────┘ └────┘ └────┘
i(7):
00 01 10 11
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ 12 │ │ 5 │ │ 2 │ │ 3 │
│ 4 │ │ 1 │ │ │ │ 7 │
│ │ │ │ │ │ │ │
└────┘ └────┘ └────┘ └────┘
i(14):
00 01 10 11
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ 12 │ │ 5 │ │ 2 │ │ 3 │
│ 4 │ │ 1 │ │ 14 │ │ 7 │
│ │ │ │ │ │ │ │
└────┘ └────┘ └────┘ └────┘
├───────────────────────────┐
│000 01 10 11 │100
┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐
│ │ │ 5 │ │ 2 │ │ 3 │ │ 12 │
│ │ │ 1 │ │ 14 │ │ 7 │ │ 4 │
│ │ │ │ │ │ │ │ │ │
└────┘ └────┘ └────┘ └────┘ └────┘
</pre>
}}
{{zdroje|
https://is.cuni.cz/webapps/zzp/detail/46740/
}}