Hashing i DBMS: statiske og dynamiske hashing-teknikker
Fiona Brown
⚡ Smart oppsummering
Hashing i DBMS er en teknikk som beregner diskplasseringen til en post direkte fra nøkkelen, uten å gå en indeks. En hash-funksjon tilordner søkenøkler til databøtter, og statisk eller dynamisk hashing styrer hvordan disse bøttene vokser.
Hva er hashing i DBMS?
I DBMS er hashing en teknikk for å søke direkte etter plasseringen av ønskede data på disken uten å bruke en indeksstruktur. Hashing-metoden brukes til å indeksere og hente elementer i en database, ettersom det er raskere å søke etter et bestemt element ved å bruke den kortere hash-nøkkelen i stedet for den opprinnelige verdien. Data lagres i form av datablokker hvis adresse genereres ved å bruke en hash-funksjon; minneplasseringen der disse postene lagres er kjent som en datablokk eller databøtte.
Hvorfor trenger vi hashing?
Her er situasjonene i et DBMS der du må bruke hashing-metoden:
- For en enorm databasestruktur er det vanskelig å søke i alle indeksverdiene gjennom alle nivåene deres og deretter nå måldatablokken for å få de ønskede dataene.
- Hashing brukes til å indeksere og hente elementer i en database, fordi det er raskere å søke etter et bestemt element ved å bruke den kortere hashnøkkelen enn den opprinnelige verdien.
- Hashing er en ideell metode for å beregne den direkte plasseringen av en datapost på disken uten å bruke en indeksstruktur.
- Det er også en nyttig teknikk for å implementere ordbøker.
Viktige terminologier i hashing
Her er viktige terminologier som brukes i hashing:
- Databøtte: Databøtter er minneplasseringer der postene lagres. Det er også kjent som lagringsenheten.
- Nøkkel: a DBMS nøkkel er et attributt eller et sett med attributter som hjelper deg med å identifisere en rad (tuple) i en relasjon (tabell).
- Hash-funksjon: et kartping funksjon som tilordner alle settet med søkenøkler til adressen der de faktiske postene er plassert.
- Lineær sondering: et fast intervall mellom sonder. I denne metoden brukes den neste tilgjengelige datablokken til å legge inn den nye posten, i stedet for å overskrive den eldre posten.
- Kvadratisk sondering: hjelper med å bestemme den nye bøtteadressen ved å legge til den påfølgende utgangen av et kvadratisk polynom til startverdien gitt av den opprinnelige beregningen.
- Hash-indeks: adressen til datablokken. En hash-funksjon kan være en enkel matematisk funksjon eller en kompleks en.
- Double Hashing: en metode som brukes i hash-tabeller for å løse kollisjoner ved å bruke en andre hash-funksjon.
- Bøtteoverløp: Tilstanden med bøtteoverløp kalles kollisjon. Dette er et fatalt stadium for enhver statisk hash-funksjon.
Typer hashing-teknikker
Det finnes hovedsakelig to typer hashingteknikker i DBMS:
- Statisk hashing
- Dynamisk hasj
De to skiller seg hovedsakelig ut i om antallet bøtter er fast, slik de neste to avsnittene forklarer.
Statisk hashing
Ved statisk hashing vil den resulterende databøtteadressen alltid forbli den samme.
Derfor, hvis du genererer en adresse for, for eksempel, Student_ID = 10 ved hjelp av hashingfunksjonen mod(3), vil den resulterende bøtteadressen alltid være 1Så du vil ikke se noen endring i bøtteadressen.
Derfor, i den statiske hashing-metoden, forblir antallet databøtter i minnet alltid konstant.
Statiske hash-funksjoner
- Sette inn en post: Når en ny post må settes inn i tabellen, genererer du en adresse for den ved hjelp av hash-nøkkelen. Når adressen er generert, lagres posten på den plasseringen.
- Søker: Når du trenger å hente posten, brukes den samme hash-funksjonen til å hente adressen til bøtta der dataene er lagret.
- Slett en oppføring: Ved å bruke hash-funksjonen henter du først posten du vil slette, og fjerner deretter posten fra den adressen i minnet.
Statisk hashing er videre delt inn i:
- Åpne hashing
- Lukket hashing
Åpne Hashing
I den åpne hashing-metoden brukes den neste tilgjengelige datablokken til å legge inn den nye posten i stedet for å overskrive den eldre posten. Denne metoden er også kjent som lineær probing.
For eksempel er A2 en ny post du vil sette inn. Hash-funksjonen genererer adressen 222, men den er allerede opptatt av en annen verdi. Det er derfor systemet ser etter den neste databøtten, 501, og tilordner A2 til den.
Lukket hashing
I den lukkede hashing-metoden, når bøttene er fulle, tildeles en ny bøtte for den samme hasjen, og resultatet lenkes etter den forrige.
Dynamisk hasj
Dynamisk hashing tilbyr en mekanisme der databøtter legges til og fjernes dynamisk og etter behov. I denne hashing-metoden hjelper hash-funksjonen deg med å opprette et stort antall verdier, og strukturen vokser eller krymper med dataene. Dette gjør den til en god løsning for tabeller med en størrelse som ikke kan forutsies på forhånd, der statisk hashing enten vil kaste bort plass eller overfylle.
Forskjellen mellom ordnet indeksering og hashing
Nedenfor er de viktigste forskjellene mellom indeksering og hashing:
| Parametre | Ordnet indeksering | hashing |
|---|---|---|
| Lagring av adresse | Adresser i minnet sorteres etter en nøkkelverdi kalt primærnøkkelen. | Adresser genereres alltid ved hjelp av en hash-funksjon på nøkkelverdien. |
| Ytelse | Den kan avta etter hvert som dataene øker, fordi dataene lagres sortert, og hver innsetting, sletting eller oppdatering endrer rekkefølgen. | Ytelsen er best med konstant tillegg og sletting av data. For en stor database blir vedlikehold av hash-filer dyrere. |
| Bruke til | Foretrukket for henting av område, der data hentes for et bestemt område. | Ideell for å hente en bestemt post basert på søkenøkkelen, og fungerer bare bra når hash-funksjonen er på søkenøkkelen. |
| Minnehåndtering | Mange ubrukte datablokker oppstår fra sletting og oppdatering og kan ikke frigjøres for gjenbruk, så regelmessig vedlikehold er nødvendig. | I statisk og dynamisk hashing administreres alltid minne og bøtteoverløp håndteres for å utvide statisk hashing. |
Kort sagt, velg bestilt indeksering for områdespørringer og hashing for eksakte samsvarsoppslag på nøkkelen.
Hva er kollisjon?
En hash-kollisjon er en tilstand der de resulterende hashene fra to eller flere elementer i datasettet feilaktig tilordnes til samme sted i hasjbord.
Hvordan håndtere en hashingkollisjon
Det finnes to teknikker du kan bruke for å unngå en hash-kollisjon:
- Gjentakelse: Denne metoden påkaller en sekundær hash-funksjon, som brukes kontinuerlig inntil et tomt spor finnes der en post kan plasseres.
- Kjetting: Kjedemetoden bygger en lenket liste over elementer der nøklene hashes til samme verdi. Denne metoden krever et ekstra lenkefelt på hver tabellposisjon.
