Hašovanie v Rôzne typy hasiacej techniky v DBMS

Obsah:

Anonim

Úvod do Hashingu v DBMS

Keď hovoríme o obrovskej štruktúre databázy a jej zložitosti, je veľmi neefektívne hľadať všetky indexy a dosahovanie požadovaných údajov sa stáva veľmi neurčitým a komplexnou možnosťou. Použitím hashovacej techniky je možné tieto stavy dosiahnuť a priamemu ukazovateľovi je možné priradiť poznať presné a priame umiestnenie na disku pre konkrétny záznam bez použitia zložitej indexovej štruktúry. Dáta v prípade hashovacej techniky sa ukladajú vo forme dátových blokov, ktorých adresa sa generuje použitím funkcie obvykle známej ako hashovacia funkcia. Miesto v pamäti, kde je uložený a sú uložené záznamy, sa nazýva dátové bloky alebo dátová skupina.

Typy hasenia v DBMS

V DBMS sú zvyčajne dva typy hashovacích techník:

1. Statické hasenie
2. Dynamické hasenie

1) Statické hasenie

V prípade statického hashovania je vytvorená množina údajov a adresa vedra je rovnaká. To znamená, že ak sa pokúsime vygenerovať adresu pre USER_ID = 113 pomocou modulu hashovacej funkcie 5, potom nám vždy poskytne výsledok ako 3 s rovnakou adresou vyzerajúcej vedra. V tomto prípade nedôjde k žiadnej zmene adresy poskytnutej vedra. Preto počet vedier zostáva počas operácie konštantný.

Prevádzka staticky napísaného hasenia

a. Vyhľadávanie záznamu: Ak existuje potreba nájsť záznam, potom sa na získanie adresy a cesty dátového vedra s uloženými údajmi použije rovnaká hashovacia funkcia.

b. Vloženie nového záznamu: Ak je nový a nový záznam vložený do tabuľky, vygeneruje sa adresa pre nový záznam na základe hashovacieho kľúča, čím sa záznam uloží na toto miesto.

  1. Vymazanie záznamu: Aby sa záznam vymazal, musí sa najprv načítať záznam, ktorý sa dá vymazať. Po dokončení tejto úlohy je potrebné záznamy vymazať pre túto adresu v pamäti.
  2. Aktualizácia záznamu: Aby sme mohli aktualizovať záznam, najprv ho prehľadáme pomocou funkcie založenej na hashe a keď sa tak stane, dá sa povedať, že náš údajový záznam je v aktualizovanom stave. Aby sme mohli vložiť nový záznam do súboru a adresa, ktorá sa vygeneruje z funkcie založenej na hašiši a zoskupenia údajov, nie je prázdna, alebo ak sú údaje už na poskytnutej adrese. Táto situácia, ktorá nastane najmä v prípade statického hashovania, sa dá lepšie nazývať pretečenie vedra, a preto existuje niekoľko spôsobov, ako sa tento problém prekonať, napríklad:

(i) Open Hashing: Ak hashovacia funkcia vygeneruje adresu, na ktorú je možné dáta vidieť už v uloženom stave, automaticky sa pridelí ďalšia úroveň vedra. Tento mechanizmus možno označiť ako techniku ​​lineárneho snímania.

Napríklad, ak R3 je nová adresa, ktorú je potrebné vložiť, funkcia hash vygeneruje adresu ako číslo 102 pre adresu R3. Vygenerovaná adresa je v úplnom stave, a preto je systém určený na vyhľadávanie novej dátovej skupiny, ktorá je 113, a priradeniu R3 k tejto skupine údajov.

(ii) Uzavreté hasenie: Keď sú vedrá úplne plné, potom sa pridelí nové vedro pre konkrétny výsledok hash, ktorý je spojený hneď po tom, čo bol predtým dokončený, a preto sa táto metóda nazýva technika preplietania pomocou pretečenia.

Napríklad R3 je čerstvá adresa, ktorá sa musí vložiť do novej tabuľky, hashovacia funkcia sa používa na generovanie adresy ako číslo 110. Táto skupina je zase plná, a preto nemôže prijímať nové údaje, a preto sa po 100.

2) Dynamické hasenie

Tento druh metódy založenej na hashovaní sa môže použiť na vyriešenie základných problémov hashovania založeného na statike, ako sú tie, ako je pretečenie vedra, pretože datové vedrá môžu rásť a zmenšovať sa s veľkosťou, čo je viac optimalizovaná technika priestoru, a preto sa nazýva rozšíriteľná hašovacia metóda. V tomto spôsobe sa hashovanie stáva dynamickým, čo znamená, že vkladacia aktivita alebo delécia je povolená bez toho, aby sa poskytoval zlý výkon.

a. Vyhľadávanie v kľúči: Vypočítajte hašovaciu adresu požadovaného kľúča a skontrolujte počet bitov, ktoré sa používajú v prípade adresára známeho ako i. Potom sú tie, ktoré sú najmenej významné z bitov I, prevzaté z adresára, ktorý dáva predstavu o indexe z adresára. Použitím tejto hodnoty indexu prejdite do adresára a vyhľadajte adresu vedra na vyhľadanie súčasných záznamov.

b. Vloženie nového záznamu: Najprv musíte postupovať podľa presne rovnakého postupu vyhľadávania, ktorý musí byť niekde v vedre. Vyhľadajte miesto v tejto vedre a potom doň vložte záznamy. Ak je vytvorená skupina kompletná a plná, potom sa skupina rozdelí a záznamy sa prerozdelia.

Napríklad posledné dva bity číslic 2 a 4 sú 00. Takže pôjdu do vedra Bo a tak ďalej podľa funkcie modulu. Kľúč 9 má adresu 1 0001, ktorá musí byť prítomná v prvom vedre, ale rozdelí sa a presunie sa do nového vedra B1, a to pokračuje dovtedy, kým všetky vedrá a kľúče nie sú dynamicky hasené. Hašovacia funkcia sa používa spôsobom, pri ktorom sa hašovacia funkcia používa na výber stĺpca a jeho hodnoty na vygenerovanie adresy. Maximálne časy, ako hashova funkcia, využíva primárny kľúč, ktorý sa zase používa na generovanie adries dátového bloku. Je to jednoduchá matematická funkcia, kde primárny kľúč možno tiež považovať za adresu dátového bloku, čo znamená, že každý riadok s rovnakou adresou ako primárny kľúč sa uloží do dátového bloku.

Odporúčané články

Toto je sprievodca Hashingom v DBMS. Tu diskutujeme úvod a rôzne typy hashovania v DBMS, ktoré zahŕňajú statické hashovanie a dynamické hashovanie spolu s príkladmi. Ďalšie informácie nájdete aj v nasledujúcich článkoch -

  1. Dátové modely v DBMS
  2. Výhody DBMS
  3. Nástroj na integráciu údajov
  4. Čo je to RDBMS?