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é hashování==
* 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
'''AINDlgoritnus najdenia stranky:'''
* 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|Schema stepenia pri linearnom hashovani]]
=== Litwin (lineární bezadresářové hashování) ===
Metoda nevyuziva adresar ale potrebuje oblast pretecenia. Nieje zaruceny pristup ku vsetkym datam na jeden pristup na disk.
Stranky su stepene nezavisle na tom, kde doslo ku kolizii, kruhovym schematom. Po kazdych L(par) vlozeni je roztepena jedna stranka. Pri stepeni pridame jednu stranku na konci stranok. Zaznamy so stepenej stranky ( + oblast pretecenia ) su potom rozdelene medzi novu a staru stranku.
'''FIND:''' ''h''(''k'') = ''k`'' ( pseodokluc)
Růst primárního souboru je lineární => lineární hashování
