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í
Zdroje:
https://is.cuni.cz/webapps/zzp/detail/46740/
