Hašování v DBMS: Statické a dynamické hašovací techniky
Fiona Brownová
⚡ Chytré shrnutí
Hašování v systémech pro správu databází (DBMS) je technika, která vypočítává umístění záznamu na disku přímo z jeho klíče, bez nutnosti procházení indexu. Hašovací funkce mapuje vyhledávací klíče na datové segmenty (buckety) a statické nebo dynamické hašování řídí, jak tyto segmenty rostou.
Co je hashování v DBMS?
V systémech pro správu databází (DBMS) je hašování technika pro přímé vyhledávání umístění požadovaných dat na disku bez použití indexové struktury. Metoda hašování se používá k indexování a načítání položek v databázi, protože je rychlejší vyhledat konkrétní položku pomocí kratšího hašovaného klíče namísto její původní hodnoty. Data jsou uložena ve formě datových bloků, jejichž adresa je generována použitím hašovací funkce; umístění v paměti, kde jsou tyto záznamy uloženy, se nazývá datový blok nebo datový bucket.
Proč potřebujeme hashování?
Zde jsou situace v systému DBMS, kde je třeba použít metodu hashování:
- U rozsáhlé databázové struktury je obtížné prohledat všechny hodnoty indexu na všech jejich úrovních a poté dosáhnout cílového datového bloku pro získání požadovaných dat.
- Hašování se používá k indexování a načítání položek v databázi, protože je rychlejší vyhledat konkrétní položku pomocí kratšího hašovaného klíče než původní hodnoty.
- Hašování je ideální metoda pro výpočet přímého umístění datového záznamu na disku bez použití indexové struktury.
- Je to také užitečná technika pro implementaci slovníků.
Důležité terminologie v hašování
Zde je důležitá terminologie používaná při hašování:
- Datový segment: Datové úložiště (data buckets) jsou paměťová místa, kde jsou uloženy záznamy. Jsou také známá jako úložná jednotka.
- Klíč: a klíč DBMS je atribut nebo sada atributů, která vám pomáhá identifikovat řádek (n-tici) v relaci (tabulce).
- Hašovací funkce: mapaping funkce, která mapuje veškerou sadu vyhledávacích klíčů na adresu, kde jsou umístěny skutečné záznamy.
- Lineární snímání: pevný interval mezi sondami. V této metodě se pro zadání nového záznamu použije další dostupný datový blok, místo aby se přepsal starší záznam.
- Kvadratické snímání: pomáhá určit novou adresu kontejneru přičtením po sobě jdoucího výstupu kvadratického polynomu k počáteční hodnotě dané původním výpočtem.
- Hašovací index: adresa datového bloku. Hašovací funkce může být jednoduchá matematická funkce nebo složitá funkce.
- Double Hašování: metoda používaná v hašovacích tabulkách k řešení kolizí aplikací druhé hašovací funkce.
- Přetečení kbelíku: Stav přetečení kbelíku se nazývá kolize. Toto je fatální stav pro jakoukoli statickou hašovací funkci.
Typy hashovacích technik
V systémech pro správu databází existují hlavně dva typy hašovacích technik:
- Statické hašování
- Dynamické hašování
Tyto dva se liší hlavně v tom, zda je počet košů pevný, jak vysvětlují následující dvě části.
Statické hašování
Při statickém hašování zůstane výsledná adresa datového úložiště vždy stejná.
Pokud tedy vygenerujete adresu například pro Student_ID = 10 pomocí hašovací funkce mod(3), bude výsledná adresa segmentu vždy 1Takže v adrese kontejneru neuvidíte žádnou změnu.
Proto u metody statického hašování zůstává počet datových segmentů v paměti vždy konstantní.
Statické hashovací funkce
- Vložení záznamu: Když je třeba do tabulky vložit nový záznam, vygenerujete pro něj adresu pomocí jeho hash klíče. Jakmile je adresa vygenerována, záznam se uloží na toto místo.
- Vyhledávání: Když potřebujete načíst záznam, použije se stejná hašovací funkce k načtení adresy úložiště, kde jsou data uložena.
- Smazat záznam: Pomocí hašovací funkce nejprve načtete záznam, který chcete smazat, a poté jej z této adresy v paměti odstraníte.
Statické hashování se dále dělí na:
- Otevřete hashování
- Uzavřené hašování
Otevřete hashování
V metodě otevřeného hašování se místo přepisování staršího záznamu používá k zápisu nového záznamu další dostupný datový blok. Tato metoda je také známá jako lineární sondování.
Například A2 je nový záznam, který chcete vložit. Hašovací funkce vygeneruje adresu 222, ale ta je již obsazena jinou hodnotou. Proto systém hledá další datový sektor, 501, a přiřadí mu A2.
Uzavřené hašování
V metodě uzavřeného hashování, když jsou koše plné, je pro stejný hash alokován nový koš a výsledek je propojen za předchozím.
Dynamické hašování
Dynamické hashování nabízí mechanismus, ve kterém jsou datové segmenty dynamicky přidávány a odebírány na vyžádání. V této metodě hashování vám hašovací funkce pomáhá vytvářet velké množství hodnot a struktura roste nebo se zmenšuje s daty. Díky tomu je vhodná pro tabulky, jejichž velikost nelze předem předpovědět, kde by statické hashování buď plýtvalo místem, nebo by způsobilo přetečení.
Rozdíl mezi uspořádaným indexováním a hašováním
Níže jsou uvedeny klíčové rozdíly mezi indexováním a hašováním:
| parametry | Seřazené indexování | Hashing |
|---|---|---|
| Uložení adresy | Adresy v paměti jsou seřazeny podle hodnoty klíče nazývané primární klíč. | Adresy jsou vždy generovány pomocí hashovací funkce na hodnotě klíče. |
| Výkon | Může se snižovat s rostoucím množstvím dat, protože data jsou uložena seřazená a každé vložení, odstranění nebo aktualizace je mění. | Výkon je nejlepší při neustálém přidávání a mazání dat. U rozsáhlé databáze se údržba hash souboru stává nákladnější. |
| Použij pro | Preferováno pro načítání rozsahu, kde se data načítají pro konkrétní rozsah. | Ideální pro načtení konkrétního záznamu na základě vyhledávacího klíče a funguje dobře pouze tehdy, když je hašovací funkce na vyhledávacím klíči. |
| Správa paměti | Mnoho nepoužívaných datových bloků vzniká operacemi mazání a aktualizace a nelze je uvolnit pro opětovné použití, proto je nutná pravidelná údržba. | Při statickém a dynamickém hašování je paměť vždy spravována a přetečení bucketu je ošetřeno pro rozšíření statického hašování. |
Zkrátka, vyberte si objednané indexování pro dotazy rozsahu a hašování pro vyhledávání přesné shody v klíči.
Co je kolize?
Kolize hašů je stav, kdy výsledné haše ze dvou nebo více položek v datové sadě chybně mapují na stejné místo v hash tabulka.
Jak se vypořádat s kolizí hašování
Existují dvě techniky, jak se vyhnout kolizi hashů:
- Opakování: Tato metoda vyvolá sekundární hašovací funkci, která se aplikuje nepřetržitě, dokud se nenajde prázdný slot, kam lze umístit záznam.
- řetězení: Metoda řetězení vytváří propojený seznam položek, jejichž hash klíčů má stejnou hodnotu. Tato metoda vyžaduje na každé pozici v tabulce další pole propojení.
