Hašování v DBMS: Statické a dynamické hašovací techniky

Od: Fiona Brownová Fiona Brownová
Hours aktualizováno

Co je hashování v DBMS?

V DBMS je hašování technika přímého vyhledávání umístění požadovaných dat na disku bez použití struktury indexu. Metoda hašování se používá k indexování a načítání položek v databázi, protože je rychlejší prohledávat konkrétní položku pomocí kratšího hashovaného klíče namísto použití její původní hodnoty. Data jsou uložena ve formě datových bloků, jejichž adresa je generována aplikací hashovací funkce v místě paměti, kde jsou tyto záznamy uloženy, známé jako datový blok nebo datový bucket.

Proč potřebujeme hashování?

Zde jsou situace v DBMS, kdy musíte použít metodu hash:

  • Pro rozsáhlou strukturu databáze je těžké prohledat všechny hodnoty indexu na celé její úrovni a pak se musíte dostat k cílovému datovému bloku, abyste získali požadovaná data.
  • Metoda hašování se používá k indexování a načítání položek v databázi, protože je rychlejší prohledávat konkrétní položku pomocí kratšího hashovaného klíče namísto použití její 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 jsou důležité terminologie, které se používají v hašování:

  • Datový kbelík – Datové segmenty jsou paměťová místa, kde jsou uloženy záznamy. Je také známá jako jednotka úložiště.
  • Klíč: klíč DBMS je atribut nebo sada atributu, která vám pomáhá identifikovat řádek (n-tice) ve vztahu (tabulce). To vám umožní najít vztah mezi dvěma tabulkami.
  • Hašovací funkce: Hašovací funkce je mapovací funkce, která mapuje všechny sady vyhledávacích klíčů na adresu, kde jsou umístěny skutečné záznamy.
  • Lineární sondování – Lineární snímání je pevný interval mezi sondami. Při této metodě se k zadání nového záznamu použije další dostupný datový blok, místo aby se přepisoval na starší záznam.
  • Kvadratické sondování– Pomůže vám určit novou adresu kbelíku. Pomůže vám přidat Interval mezi sondami přidáním po sobě jdoucího výstupu kvadratického polynomu k počáteční hodnotě dané původním výpočtem.
  • Hash index – Je to adresa datového bloku. Hašovací funkce může být jednoduchá matematická funkce až po komplexní matematickou funkci.
  • Double Hashing -Double hashování je metoda počítačového programování používaná v hašovacích tabulkách k vyřešení problémů s kolizí.
  • Přetečení kbelíku: Stav přetečení kbelíku se nazývá kolize. Toto je fatální fáze pro fungování jakékoli statické elektřiny.

Typy hashovacích technik

Existují hlavně dva typy hašovacích metod/technik SQL:

  1. Statické hašování
  2. Dynamické hašování

statické hashování

Ve statickém hashování zůstane výsledná adresa datového segmentu vždy stejná.

Pokud tedy vygenerujete adresu pro řekněme Student_ID = 10 pomocí hashovací funkce mod(3), bude výsledná adresa segmentu vždy 1. Takže neuvidíte žádnou změnu adresy bucketu.

Proto v této statické metodě hash 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, můžete pro nový záznam vygenerovat adresu pomocí jeho hash klíče. Po vygenerování adresy se záznam automaticky uloží na toto místo.
  • Vyhledávání: Když potřebujete získat záznam, stejná hashovací funkce by měla být užitečná pro získání adresy segmentu, kde by měla být data uložena.
  • Smazat záznam: Pomocí hašovací funkce můžete nejprve načíst záznam, který chcete smazat. Potom můžete odstranit záznamy pro tuto adresu v paměti.

Statické hašování se dále dělí na

  1. Otevřete hashování
  2. Zavřít hašování.

Otevřete hashování

V otevřené metodě hašování se místo přepsání staršího záznamu použije k zadání 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 generuje adresu 222. Ta je však již obsazena jinou hodnotou. Proto systém vyhledá další datový segment 501 a přiřadí mu A2.

Otevřete hashování
Jak funguje Open Hash

Zavřete hashování

V metodě close hash, když jsou segmenty plné, je pro stejný hash přidělen nový segment a výsledek je propojen za předchozí.

Dynamické hašování

Dynamické hašování nabízí mechanismus, ve kterém jsou datové segmenty přidávány a odebírány dynamicky a na vyžádání. V tomto hašování vám hašovací funkce pomáhá vytvořit velké množství hodnot.

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 Indexování objednávek Hashing
Uložení adresy Adresy v paměti jsou seřazeny podle hodnoty klíče zvané primární klíč Adresy jsou vždy generovány pomocí hashovací funkce na hodnotě klíče.
Výkon Může se snížit, když se data v souboru hash zvýší. Protože ukládá data v setříděné podobě, když je provedena jakákoli operace (vložení/smazání/aktualizace), která snižuje její výkon. Výkon hashování bude nejlepší, když dochází k neustálému přidávání a odstraňování dat. Pokud je však databáze obrovská, organizace hash souboru a jeho údržba bude nákladnější.
Použij pro Upřednostňuje se pro získávání dat z rozsahu – což znamená, že kdykoli jsou k dispozici data pro určitý rozsah, je tato metoda ideální volbou. Toto je ideální metoda, když chcete získat konkrétní záznam na základě vyhledávacího klíče. Bude však fungovat dobře pouze tehdy, když je hashovací funkce na vyhledávací klávese.
Správa paměti Kvůli operaci odstranění/aktualizace bude mnoho nevyužitých bloků dat. Tyto datové bloky nelze uvolnit pro opětovné použití. Proto je nutná pravidelná údržba paměti. U statických a dynamických hashovacích metod je paměť vždy spravována. Přetečení kbelíku je také dokonale vyřešeno pro rozšíření statického hashování.

Co je kolize?

Hašovací kolize je stav, kdy výsledný hash ze dvou nebo více dat v datové sadě nesprávně mapuje stejné místo v hash tabulka.

Jak se vypořádat s hashovací kolizí?

Existují dvě techniky, které můžete použít, abyste se vyhnuli kolizi hash:

  1. Rehashing: Tato metoda vyvolá sekundární hashovací funkci, která je aplikována nepřetržitě, dokud není nalezen prázdný slot, kam by měl být umístěn záznam.
  2. Řetězení: Metoda řetězení vytvoří propojený seznam položek, jejichž klíč hash na stejnou hodnotu. Tato metoda vyžaduje zvláštní pole odkazu na každou pozici tabulky.

Shrnutí

  • In DBMS, hašování je technika pro přímé vyhledávání umístění požadovaných dat na disku bez použití struktury indexu.
  • Metoda hašování se používá k indexování a načítání položek v databázi, protože je rychlejší prohledávat konkrétní položku pomocí kratšího hashovaného klíče namísto použití její původní hodnoty.
  • Datový segment, klíč, hashovací funkce, lineární sondování, kvadratické sondování, hash index, Double Hašování, přetečení bucketu jsou důležité terminologie používané při hašování
  • Dva typy hašovacích metod jsou 1) statické hašování 2) dynamické hašování
  • Ve statickém hashování zůstane výsledná adresa datového segmentu vždy stejná.
  • Dynamické hašování nabízí mechanismus, ve kterém jsou datové segmenty přidávány a odebírány dynamicky a na vyžádání.
  • V pořadí Indexační adresy v paměti jsou seřazeny podle kritické hodnoty, zatímco v hashování jsou adresy vždy generovány pomocí hashovací funkce na hodnotě klíče.
  • Hašovací kolize je stav, kdy výsledné haše ze dvou nebo více dat v datové sadě nesprávně mapují stejné místo v hašovací tabulce.
  • Rehashing a řetězení jsou dvě metody, které vám pomohou vyhnout se kolizi hašování.