Hashing DBMS:ssä: Staattiset ja dynaamiset hajautustekniikat
Fiona Brown
Mitä hajautus on DBMS:ssä?
DBMS:ssä hajautus on tekniikka, jolla etsitään suoraan halutun tiedon sijaintia levyltä ilman hakemistorakennetta. Hajautusmenetelmää käytetään tietokannan kohteiden indeksointiin ja hakemiseen, koska tiettyä kohdetta on nopeampi etsiä käyttämällä lyhyempää hajautusavainta sen alkuperäisen arvon sijaan. Tiedot tallennetaan tietolohkojen muodossa, joiden osoite luodaan käyttämällä hash-funktiota muistipaikassa, johon nämä tietueet on tallennettu. tietolohko tai tietoämpäri.
Miksi tarvitsemme tiivistystä?
Tässä ovat DBMS:n tilanteet, joissa sinun on käytettävä hajautusmenetelmää:
- Valtavalle tietokantarakenteelle on vaikeaa etsiä kaikkia indeksiarvoja kaikilta sen tasoilta, ja sitten sinun on päästävä kohdetietolohkoon saadaksesi halutut tiedot.
- Hajautusmenetelmää käytetään tietokannan kohteiden indeksointiin ja hakemiseen, koska tiettyä kohdetta on nopeampi etsiä käyttämällä lyhyempää hajautusavainta sen alkuperäisen arvon sijaan.
- Hashing on ihanteellinen tapa laskea tietueen suora sijainti levyllä ilman indeksirakennetta.
- Se on myös hyödyllinen tekniikka sanakirjojen toteuttamisessa.
Tärkeitä termejä hajautusohjelmassa
Tässä on tärkeitä terminologioita, joita käytetään Hashingissa:
- Tietoämpäri – Tietoämpärit ovat muistipaikkoja, joihin tietueet tallennetaan. Se tunnetaan myös nimellä Unit Of Storage.
- avain: DBMS-avain on attribuutti tai attribuuttijoukko, joka auttaa sinua tunnistamaan rivin (tuple) relaatiossa (taulukossa). Tämän avulla voit löytää kahden taulukon välisen suhteen.
- Hash-toiminto: Hajautustoiminto on kartoitustoiminto, joka kartoittaa kaikki hakuavaimet osoitteeseen, johon varsinaiset tietueet on sijoitettu.
- Lineaarinen koetus – Lineaarinen mittaus on kiinteä väli koettimien välillä. Tässä menetelmässä seuraavaa käytettävissä olevaa tietolohkoa käytetään uuden tietueen syöttämiseen sen sijaan, että se korvattaisiin vanhemmalla tietueella.
- Toissijainen koetus– Se auttaa sinua määrittämään uuden kauhan osoitteen. Se auttaa lisäämään mittausvälin lisäämällä toisen asteen polynomin peräkkäisen lähtöarvon alkuperäisen laskennan antamaan aloitusarvoon.
- Hash-indeksi – Se on tietolohkon osoite. Hajautusfunktio voi olla yksinkertainen matemaattinen funktio, jopa monimutkainen matemaattinen funktio.
- Double hajautusta -Double hajautus on tietokoneohjelmointimenetelmä, jota käytetään hash-taulukoissa törmäysongelmien ratkaisemiseen.
- Kauhan ylivuoto: Kauhan ylivuototilaa kutsutaan törmäykseksi. Tämä on kohtalokas vaihe minkä tahansa staattisen toiminnan kannalta.
Hashing-tekniikoiden tyypit
SQL-hajautusmenetelmiä/-tekniikoita on pääasiassa kahdenlaisia:
- Staattinen hajautus
- Dynaaminen hajautus
staattinen hajautus
Staattisessa hajautustyössä tuloksena oleva tietosäilon osoite pysyy aina samana.
Siksi, jos luot osoitteen sanoa Opiskelijatunnus = 10 käyttämällä hajautustoimintoa mod(3), tuloksena oleva ryhmäosoite on aina 1. Et siis näe muutosta ämpäriosoitteessa.
Tästä syystä tässä staattisessa hajautusmenetelmässä muistissa olevien tietoryhmien määrä pysyy aina vakiona.
Staattiset hajautusfunktiot
- Lisätään tietue: Kun uusi tietue on lisättävä taulukkoon, voit luoda uudelle tietueelle osoitteen sen hash-avaimella. Kun osoite luodaan, tietue tallennetaan automaattisesti kyseiseen sijaintiin.
- Etsiä: Kun sinun on noudettava tietue, saman hajautustoiminnon pitäisi olla hyödyllinen haettaessa sen ryhmän osoite, johon tiedot pitäisi tallentaa.
- Poista tietue: Hajautustoimintoa käyttämällä voit ensin hakea tietueen, jonka haluat poistaa. Sitten voit poistaa kyseisen osoitteen tietueet muistista.
Staattinen hajautus jaetaan edelleen
- Avaa hajautus
- Sulje hajautus.
Avaa hajautus
Avoimessa hajautusmenetelmässä vanhan korvaamisen sijaan käytetään seuraavaa saatavilla olevaa tietolohkoa uuden tietueen syöttämiseen. Tätä menetelmää kutsutaan myös lineaariseksi luotaukseksi.
Esimerkiksi A2 on uusi tietue, jonka haluat lisätä. Hash-funktio luo osoitteen muodossa 222. Mutta se on jo jonkin muun arvon varaama. Tästä syystä järjestelmä etsii seuraavan datasäiön 501 ja määrittää sille A2:n.
Sulje hajautus
Suljetussa hajautusmenetelmässä, kun ämpärit ovat täynnä, samalle tiivisteelle varataan uusi säilö ja tulos linkitetään edellisen jälkeen.
Dynaaminen hajautus
Dynaaminen hajautus tarjoaa mekanismin, jossa tietoryhmiä lisätään ja poistetaan dynaamisesti ja pyynnöstä. Tässä hajautustoiminnossa hash-funktio auttaa sinua luomaan suuren määrän arvoja.
Ero järjestetyn indeksoinnin ja tiivistyksen välillä
Alla on tärkeimmät erot indeksoinnin ja tiivistyksen välillä
| parametrit | Tilausten indeksointi | hajautusta |
|---|---|---|
| Osoitteen tallennus | Muistissa olevat osoitteet lajitellaan ensisijaiseksi avaimeksi kutsutun avainarvon mukaan | Osoitteet luodaan aina käyttämällä avainarvon hash-funktiota. |
| Suorituskyky | Se voi pienentyä, kun hajautustiedoston data lisääntyy. Koska se tallentaa tiedot lajiteltuna, kun suoritetaan jokin (lisää/poista/päivitä) toiminto, joka heikentää sen suorituskykyä. | Hajautus toimii parhaiten, kun tietoja lisätään ja poistetaan jatkuvasti. Kuitenkin, kun tietokanta on valtava, hash-tiedostojen organisointi ja ylläpito ovat kalliimpia. |
| Käyttää | Suositeltu tietojen etäisyyshakuun – mikä tarkoittaa, että aina kun tietystä alueesta on hakudataa, tämä menetelmä on ihanteellinen vaihtoehto. | Tämä on ihanteellinen tapa, kun haluat hakea tietyn tietueen hakuavaimen perusteella. Se toimii kuitenkin hyvin vain, kun hajautustoiminto on hakunäppäimessä. |
| Muistinhallinta | Poisto-/päivitystoiminnon vuoksi on paljon käyttämättömiä tietolohkoja. Näitä tietolohkoja ei voi luovuttaa uudelleen käytettäväksi. Tästä syystä muistin säännöllinen huolto on tarpeen. | Staattisissa ja dynaamisissa hajautusmenetelmissä muistia hallitaan aina. Kauhan ylivuoto on myös käsitelty täydellisesti staattisen hajautusarvon pidentämiseksi. |
Mikä on törmäys?
Hash-törmäys on tila, jossa tuloksena olevat tiivisteet kahdesta tai useammasta tietojoukon tiedosta kartoittavat virheellisesti saman paikan hash-pöytä.
Miten käsitellä Hashing-törmäystä?
Voit käyttää kahta tekniikkaa välttääksesi hash-törmäyksen:
- Rehashing: Tämä menetelmä käynnistää toissijaisen hajautusfunktion, jota käytetään jatkuvasti, kunnes löydetään tyhjä paikka, johon tietue tulisi sijoittaa.
- ketjutus: Ketjutusmenetelmä rakentaa linkitetyn luettelon kohteista, joiden avain tiivistää samaan arvoon. Tämä menetelmä vaatii ylimääräisen linkkikentän jokaiseen taulukon sijaintiin.
Yhteenveto
- In DBMS, hajautus on tekniikka, jolla etsitään suoraan haluttujen tietojen sijainti levyltä ilman hakemistorakennetta.
- Hajautusmenetelmää käytetään tietokannan kohteiden indeksointiin ja hakemiseen, koska tiettyä kohdetta on nopeampi etsiä käyttämällä lyhyempää hajautusavainta sen alkuperäisen arvon sijaan.
- Tietosäilö, avain , hajautustoiminto, lineaarinen koetus, neliöllinen mittaus, hajaindeksi, Double Hashing, Bucket Overflow ovat tärkeitä termejä, joita käytetään hajautustyössä
- Kahden tyyppisiä hajautusmenetelmiä ovat 1) staattinen hajautus 2) dynaaminen hajautus
- Staattisessa hajautustyössä tuloksena oleva tietosäilon osoite pysyy aina samana.
- Dynaaminen hajautus tarjoaa mekanismin, jossa tietoryhmiä lisätään ja poistetaan dynaamisesti ja pyynnöstä.
- Järjestyksessä Indeksointiosoitteet muistissa lajitellaan kriittisen arvon mukaan, kun taas hajautuksessa osoitteet luodaan aina käyttämällä avainarvon hash-funktiota.
- Hash-törmäys on tila, jossa tuloksena olevat tiivisteet kahdesta tai useammasta tietojoukon tiedosta kartoittavat virheellisesti saman paikan hajautustaulukossa.
- Uudelleenhajotus ja ketjuttaminen ovat kaksi tapaa, jotka auttavat sinua välttämään hajautustörmäyksen.