Hashing în DBMS: tehnici de hashing statice și dinamice
Ce este hashing în DBMS?
În DBMS, hashingul este o tehnică de căutare directă a locației datelor dorite pe disc, fără a utiliza structura indexului. Metoda hashing este utilizată pentru indexarea și preluarea elementelor dintr-o bază de date, deoarece este mai rapid să căutați acel element specific folosind cheia hashing mai scurtă în loc să folosiți valoarea sa originală. Datele sunt stocate sub formă de blocuri de date a căror adresă este generată prin aplicarea unei funcții hash în locația de memorie în care sunt stocate aceste înregistrări cunoscută sub numele de bloc de date sau compartiment de date.
De ce avem nevoie de Hashing?
Iată situațiile din DBMS în care trebuie să aplicați metoda Hashing:
- Pentru o structură uriașă a bazei de date, este greu să căutați toate valorile indexului prin toate nivelurile sale și apoi trebuie să ajungeți la blocul de date de destinație pentru a obține datele dorite.
- Metoda hashing este utilizată pentru indexarea și preluarea elementelor dintr-o bază de date, deoarece este mai rapid să căutați acel element specific folosind cheia hashing mai scurtă în loc să folosiți valoarea sa originală.
- Hashing este o metodă ideală pentru a calcula locația directă a unei înregistrări de date pe disc fără a utiliza structura indexului.
- Este, de asemenea, o tehnică utilă pentru implementarea dicționarelor.
Terminologii importante în hashing
Iată terminologii importante care sunt folosite în Hashing:
- Grup de date – Bucket-urile de date sunt locații de memorie în care sunt stocate înregistrările. Este cunoscută și sub numele de Unitate de stocare.
- Cheie: O cheie DBMS este un atribut sau un set al unui atribut care vă ajută să identificați un rând (tuplu) într-o relație (tabel). Acest lucru vă permite să găsiți relația dintre două tabele.
- Funcția Hash: O funcție hash, este o funcție de mapare care mapează tot setul de chei de căutare la adresa unde sunt plasate înregistrările reale.
- Sondare liniară – Sondarea liniară este un interval fix între sonde. În această metodă, următorul bloc de date disponibil este folosit pentru a introduce noua înregistrare, în loc să se suprascrie pe înregistrarea mai veche.
- Sondarea cuadratică– Vă ajută să determinați noua adresă a grupului. Vă ajută să adăugați Interval între probe prin adăugarea ieșirii consecutive a polinomului pătratic la valoarea de pornire dată de calculul original.
- Indicele hash – Este o adresă a blocului de date. O funcție hash ar putea fi o funcție matematică simplă chiar și o funcție matematică complexă.
- Double hashing -Double hashing este o metodă de programare computerizată utilizată în tabelele hash pentru a rezolva problemele legate de o coliziune.
- Debordare găleată: Condiția de preaplin al găleții se numește coliziune. Aceasta este o etapă fatală pentru orice static trebuie să funcționeze.
Tipuri de tehnici de hashing
Există în principal două tipuri de metode/tehnici de hashing SQL:
- Hashing static
- Hashing dinamic
Hashing static
În hashingul static, adresa de date rezultată va rămâne întotdeauna aceeași.
Prin urmare, dacă generați o adresă pentru a spune Student_ID = 10 folosind funcția de hashing mod (3), adresa compartimentului rezultată va fi întotdeauna 1. Deci, nu veți vedea nicio modificare în adresa găleții.
Prin urmare, în această metodă de hashing statică, numărul de compartimente de date din memorie rămâne întotdeauna constant.
Funcții hash statice
- Inserarea unei înregistrări: Când o înregistrare nouă trebuie să fie inserată în tabel, puteți genera o adresă pentru noua înregistrare folosind cheia hash. Când adresa este generată, înregistrarea este stocată automat în acea locație.
- Căutare: Când trebuie să preluați înregistrarea, aceeași funcție hash ar trebui să fie utilă pentru a prelua adresa compartimentului în care ar trebui să fie stocate datele.
- Ștergeți o înregistrare: Folosind funcția hash, puteți prelua mai întâi înregistrarea pe care doriți să o ștergeți. Apoi puteți elimina înregistrările pentru adresa respectivă din memorie.
Hashingul static este împărțit în continuare în
- Deschide hashing
- Închide hashing.
Deschide Hashing
În metoda hashing deschisă, în loc să se suprascrie pe unul mai vechi, următorul bloc de date disponibil este folosit pentru a introduce noua înregistrare. Această metodă este cunoscută și sub numele de sondare liniară.
De exemplu, A2 este o înregistrare nouă pe care doriți să o introduceți. Funcția hash generează adresa ca 222. Dar este deja ocupată de o altă valoare. De aceea sistemul caută următorul compartiment de date 501 și îi atribuie A2.
Închide Hashing
În metoda close hashing, când gălețile sunt pline, o găleată nouă este alocată pentru același hash și rezultatul este legat după cel precedent.
Hashing dinamic
Hashingul dinamic oferă un mecanism prin care gălețile de date sunt adăugate și eliminate dinamic și la cerere. În acest hashing, funcția hash vă ajută să creați un număr mare de valori.
Diferența dintre indexarea ordonată și hashing
Mai jos sunt diferențele cheie dintre indexare și hashing
parametrii | Indexarea comenzilor | hashing |
---|---|---|
Stocarea adresei | Adresele din memorie sunt sortate în funcție de valoarea cheii numită cheie primară | Adresele sunt întotdeauna generate folosind o funcție hash pe valoarea cheii. |
Performanţă | Poate scădea atunci când datele cresc în fișierul hash. Deoarece stochează datele într-o formă sortată atunci când se efectuează orice operație (inserare/ștergere/actualizare) care îi scade performanța. | Performanța hashing-ului va fi cea mai bună atunci când există o adăugare și o ștergere constantă a datelor. Cu toate acestea, atunci când baza de date este uriașă, organizarea fișierelor hash și întreținerea acesteia vor fi mai costisitoare. |
Utilizați pentru | Preferată pentru extragerea datelor în interval - ceea ce înseamnă că ori de câte ori există date de regăsire pentru un anumit interval, această metodă este o opțiune ideală. | Aceasta este o metodă ideală atunci când doriți să preluați o anumită înregistrare bazată pe cheia de căutare. Cu toate acestea, va funcționa bine numai atunci când funcția hash este pe tasta de căutare. |
Managementul memoriei | Vor fi multe blocuri de date neutilizate din cauza operațiunii de ștergere/actualizare. Aceste blocuri de date nu pot fi eliberate pentru reutilizare. De aceea este necesară întreținerea regulată a memoriei. | În metodele de hashing statice și dinamice, memoria este întotdeauna gestionată. Debordarea găleții este, de asemenea, gestionată perfect pentru a extinde hashingul static. |
Ce este coliziunea?
Ciocnirea hash este o stare în care hashe-urile rezultate din două sau mai multe date din setul de date mapează greșit același loc în masa de hash.
Cum să faci față coliziunii Hashing?
Există două tehnici pe care le puteți folosi pentru a evita o coliziune hash:
- Reluare: Această metodă invocă o funcție hash secundară, care este aplicată continuu până când este găsit un slot gol, unde ar trebui să fie plasată o înregistrare.
- Înlănțuirea: Metoda de înlănțuire construiește o listă Linked de elemente a căror cheie are aceeași valoare. Această metodă necesită un câmp de legătură suplimentar la fiecare poziție de tabel.
Rezumat
- In Baze de date, hashingul este o tehnică de căutare directă a locației datelor dorite pe disc fără a utiliza structura indexului.
- Metoda hashing este utilizată pentru indexarea și preluarea elementelor dintr-o bază de date, deoarece este mai rapid să căutați acel element specific folosind cheia hashing mai scurtă în loc să folosiți valoarea sa originală.
- Buchetă de date, cheie, funcție hash, sondare liniară, sondare patratică, indice hash, Double Hashing, Bucket Overflow sunt terminologii importante folosite în hashing
- Două tipuri de metode de hashing sunt 1) hashing static 2) hashing dinamic
- În hashingul static, adresa de date rezultată va rămâne întotdeauna aceeași.
- Hashingul dinamic oferă un mecanism prin care gălețile de date sunt adăugate și eliminate dinamic și la cerere.
- În ordine, adresele de indexare din memorie sunt sortate în funcție de o valoare critică, în timp ce în hashing adresele sunt întotdeauna generate folosind o funcție hash pe valoarea cheii.
- Coliziunea hash este o stare în care hashe-urile rezultate din două sau mai multe date din setul de date mapează greșit același loc în tabelul hash.
- Rehashing și înlănțuire sunt două metode care vă ajută să evitați coliziunea hashing.