Hashing DBMS:ssä: Staattiset ja dynaamiset hajautustekniikat
Fiona Brown
⚡ Älykäs yhteenveto
Tietokannan hallintajärjestelmissä (DBMS) hajauttaminen on tekniikka, joka laskee tietueen levyn sijainnin suoraan sen avaimesta ilman indeksin läpikäymistä. Hajautusfunktio yhdistää hakuavaimet datasäilöihin, ja staattinen tai dynaaminen hajauttaminen hallitsee näiden säilöjen kasvua.
Mitä hajautus on DBMS:ssä?
Tietokannan hallintajärjestelmissä hajautus on tekniikka, jolla halutun datan sijaintia voidaan hakea suoraan levyltä ilman indeksirakennetta. Hajautusmenetelmää käytetään tietokannan kohteiden indeksointiin ja hakemiseen, koska tietyn kohteen etsiminen lyhyemmän hajautusavaimen avulla on nopeampaa kuin sen alkuperäisen arvon avulla. Data tallennetaan datalohkoina, joiden osoite luodaan hajautusfunktion avulla; muistipaikka, johon nämä tietueet tallennetaan, tunnetaan nimellä tietolohko tai tietoämpäri.
Miksi tarvitsemme hajautusta?
Tässä ovat tilanteet tietokannan hallintajärjestelmässä, joissa sinun on käytettävä hajautusmenetelmää:
- Valtavan tietokantarakenteen osalta on vaikeaa etsiä kaikkia indeksiarvoja kaikkien tasojen läpi ja sitten päästä kohdedatalohkoon haluttujen tietojen saamiseksi.
- Tiivistystä käytetään tietokannan kohteiden indeksointiin ja hakemiseen, koska tietyn kohteen etsiminen on nopeampaa käyttämällä lyhyempää tiivistettyä avainta kuin alkuperäistä arvoa.
- Hajautus on ihanteellinen menetelmä datatietueen suoran sijainnin laskemiseen levyllä ilman indeksirakennetta.
- Se on myös hyödyllinen tekniikka sanakirjojen toteuttamisessa.
Tärkeitä termejä hajautusohjelmassa
Tässä on tärkeitä hajautuksessa käytettyjä terminologioita:
- Datasäilö: datasäilö on muistipaikka, johon tietueet tallennetaan. Sitä kutsutaan myös tallennusyksiköksi.
- Key: a DBMS-avain on attribuutti tai joukko attribuutteja, jotka auttavat tunnistamaan rivin (tuplen) relaatiossa (taulukossa).
- Hajautusfunktio: karttaping funktio, joka yhdistää kaikki hakuavaimet osoitteeseen, johon varsinaiset tietueet sijaitsevat.
- Lineaarinen mittaus: kiinteä aikaväli luotainten välillä. Tässä menetelmässä seuraavaa käytettävissä olevaa datalohkoa käytetään uuden tietueen syöttämiseen sen sijaan, että vanhempi tietue korvattaisiin.
- Toisen asteen mittaus: auttaa määrittämään uuden ämpäriosoitteen lisäämällä toisen asteen polynomin peräkkäisen tulosteen alkuperäisen laskennan antamaan aloitusarvoon.
- Hajautusindeksi: datalohkon osoite. Hajautusfunktio voi olla yksinkertainen matemaattinen funktio tai monimutkainen funktio.
- Double Hashing: hajautustaulukoissa käytetty menetelmä törmäysten ratkaisemiseksi käyttämällä toista hajautusfunktiota.
- Kauhan ylivuoto: Kauhan ylivuodon tilaa kutsutaan törmäykseksi. Tämä on kohtalokas vaihe mille tahansa staattiselle tiivistefunktiolle.
Hashing-tekniikoiden tyypit
Tietokannan hallintajärjestelmissä on pääasiassa kahdenlaisia hajautustekniikoita:
- Staattinen hajautus
- Dynaaminen hajautus
Nämä kaksi eroavat pääasiassa siinä, onko kauhojen lukumäärä kiinteä, kuten seuraavissa kahdessa osiossa selitetään.
Staattinen hajautus
Staattisessa hajautuksessa tuloksena oleva datasäiliön osoite pysyy aina samana.
Jos siis luot osoitteen esimerkiksi Opiskelijatunnus = 10 hajautusfunktion käyttäminen mod(3), tuloksena oleva ryhmäosoite on aina 1Joten et näe mitään muutosta säiliön osoitteessa.
Siksi staattisessa hajautusmenetelmässä muistissa olevien datasäilöjen määrä pysyy aina vakiona.
Staattiset hajautusfunktiot
- Tietueen lisääminen: Kun taulukkoon on lisättävä uusi tietue, sille luodaan osoite sen hajautusavaimen avulla. Kun osoite on luotu, tietue tallennetaan kyseiseen sijaintiin.
- Haetaan: Kun sinun on haettava tietue, samaa hajautusfunktiota käytetään hakemaan sen säilön osoite, johon tiedot on tallennettu.
- Poista tietue: Hajautusfunktiota käytettäessä ensin haetaan poistettava tietue ja sitten poistetaan tietue kyseisestä osoitteesta muistissa.
Staattinen hajauttaminen jaetaan edelleen seuraaviin osiin:
- Avaa hajautus
- Suljettu hajautus
Avaa hajautus
Avoimessa hajautusmenetelmässä vanhan tietueen korvaamisen sijaan käytetään seuraavaa käytettävissä olevaa datalohkoa uuden tietueen syöttämiseen. Tätä menetelmää kutsutaan myös lineaariseksi luotaimeksi.
Esimerkiksi A2 on uusi tietue, jonka haluat lisätä. Hajautusfunktio luo osoitteen 222, mutta se on jo varattu toiselle arvolle. Siksi järjestelmä etsii seuraavaa datasäilöä, 501, ja määrittää sille osoitteen A2.
Suljettu hajauttaminen
Suljetussa hajautusmenetelmässä, kun ämpärit ovat täynnä, samalle hajautukselle varataan uusi ämpäri ja tulos linkitetään edellisen jälkeen.
Dynaaminen hajautus
Dynaaminen hajautus tarjoaa mekanismin, jossa datasäilöjä lisätään ja poistetaan dynaamisesti ja tarvittaessa. Tässä hajautusmenetelmässä hajautusfunktio auttaa luomaan suuren määrän arvoja, ja rakenne kasvaa tai kutistuu datan mukana. Tämä tekee siitä erinomaisen sopivan taulukoille, joiden kokoa ei voida ennustaa etukäteen, missä staattinen hajautus joko tuhlaisi tilaa tai ylittäisi sen.
Ero järjestetyn indeksoinnin ja hajautuksen välillä
Alla on indeksoinnin ja hajautuksen tärkeimmät erot:
| parametrit | Järjestetty indeksointi | hajautusta |
|---|---|---|
| Osoitteen tallennus | Muistissa olevat osoitteet lajitellaan avaimen arvon, jota kutsutaan ensisijaiseksi avaimeksi, mukaan. | Osoitteet luodaan aina käyttämällä avainarvon hash-funktiota. |
| Suorituskyky | Se voi pienentyä datan kasvaessa, koska data tallennetaan lajiteltuna ja jokainen lisäys, poisto tai päivitys järjestää sen uudelleen. | Suorituskyky on paras, kun tietoja lisätään ja poistetaan jatkuvasti. Suuren tietokannan hajautustiedostojen ylläpito tulee kalliimmaksi. |
| Käyttää | Suositellaan aluehakuun, jossa tiedot haetaan tietyltä alueelta. | Ihanteellinen tietyn tietueen hakemiseen hakuavaimen perusteella ja toimii hyvin vain, kun hakuavaimessa on tiivistefunktio. |
| Muistinhallinta | Monet käyttämättömät datalohkot syntyvät poisto- ja päivitysoperaatioista, eikä niitä voida vapauttaa uudelleenkäyttöön, joten säännöllinen ylläpito on tarpeen. | Staattisessa ja dynaamisessa hajautuksessa muistia hallitaan aina ja kauhan ylivuotoa käsitellään staattisen hajautuksen laajentamiseksi. |
Lyhyesti sanottuna, valitse tilattu indeksointi välikyselyihin ja hajautukseen avaimen tarkkojen vastineiden hauissa.
Mikä on törmäys?
Tiivistystörmäys on tila, jossa kahden tai useamman tietojoukon alkion tiivisteet kohdistuvat virheellisesti samaan paikkaan aineistossa. hash-pöytä.
Kuinka käsitellä hajautustörmäystä
Voit välttää hajautusvirheet kahdella tavalla:
- Uudelleenkerronta: Tämä metodi kutsuu toissijaista hajautusfunktiota, jota käytetään jatkuvasti, kunnes löytyy tyhjä paikka, johon tietue voidaan sijoittaa.
- Ketjutus: Ketjutusmetodi muodostaa linkitetyn listan alkioista, joiden avaimet ovat hajautettuina samaan arvoon. Tämä metodi vaatii ylimääräisen linkkikentän jokaiseen taulukon sijaintiin.
