Raspršivanje u DBMS-u: statičke i dinamičke tehnike raspršivanja

Što je hashiranje u DBMS-u?

U DBMS-u, raspršivanje je tehnika za izravno pretraživanje lokacije željenih podataka na disku bez korištenja strukture indeksa. Metoda raspršivanja koristi se za indeksiranje i dohvaćanje stavki u bazi podataka jer je brže pretraživati ​​tu određenu stavku korištenjem kraćeg raspršenog ključa umjesto korištenja njegove izvorne vrijednosti. Podaci se pohranjuju u obliku podatkovnih blokova čija se adresa generira primjenom hash funkcije u memorijskoj lokaciji na kojoj su ti zapisi pohranjeni poznatoj kao blok podataka ili spremnik podataka.

Zašto nam je potrebno Hashing?

Evo situacija u DBMS-u u kojima trebate primijeniti metodu Hashing:

  • Za ogromnu strukturu baze podataka, teško je pretraživati ​​sve vrijednosti indeksa kroz cijelu njezinu razinu, a zatim morate doći do odredišnog bloka podataka da biste dobili željene podatke.
  • Metoda raspršivanja koristi se za indeksiranje i dohvaćanje stavki u bazi podataka jer je brže pretraživati ​​tu određenu stavku korištenjem kraćeg raspršenog ključa umjesto korištenja njegove izvorne vrijednosti.
  • Raspršivanje je idealna metoda za izračunavanje izravne lokacije zapisa podataka na disku bez korištenja strukture indeksa.
  • To je također korisna tehnika za implementaciju rječnika.

Važne terminologije u hashiranju

Ovdje su važne terminologije koje se koriste u hashiranju:

  • Kanta s podacima – Spremnici podataka su memorijske lokacije na kojima su pohranjeni zapisi. Također je poznata kao jedinica za pohranu.
  • Ključ: DBMS ključ je atribut ili skup atributa koji vam pomaže da identificirate red (torku) u relaciji (tablici). To vam omogućuje da pronađete odnos između dvije tablice.
  • Hash funkcija: Raspršivačka funkcija je funkcija preslikavanja koja preslikava sav skup ključeva za pretraživanje na adresu na kojoj se nalaze stvarni zapisi.
  • Linearno ispitivanje – Linearno sondiranje je fiksni interval između sondiranja. U ovoj metodi, sljedeći dostupni blok podataka koristi se za unos novog zapisa, umjesto prepisivanja preko starijeg zapisa.
  • Kvadratno ispitivanje– Pomaže vam da odredite novu adresu spremnika. Pomaže vam dodati interval između sondi dodavanjem uzastopnog izlaza kvadratnog polinoma početnoj vrijednosti danoj izvornim izračunom.
  • Hash indeks – To je adresa bloka podataka. Hash funkcija može biti jednostavna matematička funkcija čak i složena matematička funkcija.
  • Double raspršivanje -Double hashiranje je metoda računalnog programiranja koja se koristi u hash tablicama za rješavanje problema kolizije.
  • Preljev kante: Stanje prelijevanja kante naziva se sudar. Ovo je kobna faza za funkcioniranje svake statike.

Vrste tehnika raspršivanja

Uglavnom postoje dvije vrste metoda/tehnika raspršivanja SQL-a:

  1. Statičko raspršivanje
  2. Dinamičko raspršivanje

statičko raspršivanje

U statičkom raspršivanju, rezultirajuća adresa spremnika podataka uvijek će ostati ista.

Stoga, ako generirate adresu za recimo Student_ID = 10 pomoću funkcije raspršivanja mod(3), rezultirajuća adresa spremnika uvijek će biti 1. Dakle, nećete vidjeti nikakve promjene u adresi spremnika.

Stoga, u ovoj metodi statičkog raspršivanja, broj spremnika podataka u memoriji uvijek ostaje konstantan.

Statičke hash funkcije

  • Umetanje zapisa: Kada je novi zapis potrebno umetnuti u tablicu, možete generirati adresu za novi zapis koristeći njegov hash ključ. Kada se adresa generira, zapis se automatski pohranjuje na to mjesto.
  • Pretraživanje: Kada trebate dohvatiti zapis, ista hash funkcija bi trebala biti od pomoći za dohvaćanje adrese spremnika u koji bi podaci trebali biti pohranjeni.
  • Brisanje zapisa: Koristeći hash funkciju, prvo možete dohvatiti zapis koji želite izbrisati. Zatim možete ukloniti zapise za tu adresu u memoriji.

Statičko raspršivanje dalje se dijeli na

  1. Otvoreno raspršivanje
  2. Zatvori raspršivanje.

Otvorite Raspršivanje

U otvorenoj metodi raspršivanja, umjesto prepisivanja starijeg, sljedeći dostupni blok podataka koristi se za unos novog zapisa. Ova metoda je također poznata kao linearno ispitivanje.

Na primjer, A2 je novi zapis koji želite umetnuti. Funkcija raspršivanja generira adresu kao 222. Ali ona je već zauzeta nekom drugom vrijednošću. Zato sustav traži sljedeći spremnik podataka 501 i dodjeljuje mu A2.

Otvorite Raspršivanje
Kako funkcionira Open Hash

Zatvori raspršivanje

U metodi bliskog raspršivanja, kada su spremnici puni, novi se spremnik dodjeljuje za isti hash i rezultati se povezuju nakon prethodnog.

Dinamičko raspršivanje

Dinamičko raspršivanje nudi mehanizam u kojem se spremnici podataka dodaju i uklanjaju dinamički i na zahtjev. U ovom raspršivanju, funkcija raspršivanja pomaže vam da stvorite veliki broj vrijednosti.

Razlika između uređenog indeksiranja i raspršivanja

Ispod su ključne razlike između indeksiranja i raspršivanja

Parametri Indeksiranje naloga raspršivanje
Pohranjivanje adrese Adrese u memoriji sortirane su prema vrijednosti ključa koja se naziva primarni ključ Adrese se uvijek generiraju korištenjem hash funkcije na vrijednosti ključa.
Izvođenje Može se smanjiti kada se podaci povećaju u hash datoteci. Budući da pohranjuje podatke u sortiranom obliku kada se izvrši bilo kakva operacija (umetanje/brisanje/ažuriranje) koja smanjuje njegovu izvedbu. Izvedba hashiranja bit će najbolja kada postoji stalno dodavanje i brisanje podataka. Međutim, kada je baza podataka ogromna, tada će organizacija hash datoteke i njeno održavanje biti skuplji.
Koristiti za Preferira se za dohvaćanje podataka u rasponu - što znači da je ova metoda idealna opcija kad god postoje podaci za dohvaćanje određenog raspona. Ovo je idealna metoda kada želite dohvatiti određeni zapis na temelju ključa za pretraživanje. Međutim, dobro će funkcionirati samo ako je hash funkcija na ključu za pretraživanje.
Upravljanje memorijom Bit će mnogo neiskorištenih blokova podataka zbog operacije brisanja/ažuriranja. Ovi blokovi podataka ne mogu se pustiti za ponovnu upotrebu. Zbog toga je potrebno redovito održavanje memorije. U statičkim i dinamičkim metodama raspršivanja memorijom se uvijek upravlja. Prelijevanje spremnika također se savršeno obrađuje kako bi se proširilo statičko raspršivanje.

Što je sudar?

Hash kolizija je stanje kada rezultirajuća hashiranja iz dva ili više podataka u skupu podataka pogrešno mapiraju isto mjesto u hash tablica.

Kako se nositi sa Hashing Collision?

Postoje dvije tehnike koje možete koristiti za izbjegavanje hash kolizije:

  1. Ponavljanje: Ova metoda poziva sekundarnu hash funkciju, koja se kontinuirano primjenjuje sve dok se ne pronađe prazan utor, gdje treba staviti zapis.
  2. Ulančavanje: Metoda ulančavanja gradi povezani popis stavki čiji ključ ima istu vrijednost. Ova metoda zahtijeva dodatno polje veze za svaku poziciju tablice.

rezime

  • In DBMS, hashiranje je tehnika za izravno pretraživanje lokacije željenih podataka na disku bez korištenja strukture indeksa.
  • Metoda raspršivanja koristi se za indeksiranje i dohvaćanje stavki u bazi podataka jer je brže pretraživati ​​tu određenu stavku korištenjem kraćeg raspršenog ključa umjesto korištenja njegove izvorne vrijednosti.
  • Spremnik podataka, ključ, hash funkcija, linearno ispitivanje, kvadratno ispitivanje, hash indeks, Double Hashing, Bucket Overflow važne su terminologije koje se koriste u hashiranju
  • Dvije vrste metoda raspršivanja su 1) statičko raspršivanje 2) dinamičko raspršivanje
  • U statičkom raspršivanju, rezultirajuća adresa spremnika podataka uvijek će ostati ista.
  • Dinamičko raspršivanje nudi mehanizam u kojem se spremnici podataka dodaju i uklanjaju dinamički i na zahtjev.
  • U redoslijedu indeksiranja adrese u memoriji sortirane su prema kritičnoj vrijednosti dok se u raspršivanju adrese uvijek generiraju korištenjem funkcije raspršivanja na vrijednosti ključa.
  • Hash kolizija je stanje kada rezultirajuća hashiranja iz dva ili više podataka u skupu podataka pogrešno mapiraju isto mjesto u hash tablici.
  • Ponovno raspršivanje i ulančavanje dvije su metode koje vam pomažu da izbjegnete koliziju raspršivanja.