Räsimine DBMS-is: staatilised ja dünaamilised räsitehnikad

Autor: Fiona Brown Fiona Brown
Hours Ajakohastatud

⚡ Nutikas kokkuvõte

Räsimine andmebaasihaldussüsteemides on tehnika, mis arvutab kirje ketta asukoha otse selle võtmest, ilma indeksit läbimata. Räsifunktsioon seob otsinguvõtmed andmeämbritega ja staatiline või dünaamiline räsimine haldab nende ämbrite kasvamist.

  • ⚡ Põhiidee: Räsifunktsioon muudab võtme ämbriaadressiks, seega leitakse kirje ühe sammuga, mitte indeksi läbimise teel.
  • 🪣 Andmete ämber: Mälu asukoht ehk salvestusühik, kuhu paigutatakse sama räsiväärtusega kirjed.
  • 📌 Staatiline räsimine: Ämbrite arv on fikseeritud, seega antud võti vastab alati samale aadressile.
  • 📈 Dünaamiline räsimine: Andmemahu muutudes lisatakse ja eemaldatakse ämbreid nõudmisel.
  • ???? Kokkupõrge: Kahe võtme kaartping samasse ämbrisse, lahendatuna sondeerimise, ümberkirjutamise või aheldamise teel.
  • 🔍 Parim: Täpse vaste otsingud otsinguvõtmel, kus räsimine ületab järjestatud indekseerimise.
  • 📊 Kompromiss: Järjestatud indekseerimise võidud vahemikupäringute puhul; räsimise võidud konstantsete lisamiste ja punktotsingute puhul.
Loe rohkem

Staatiline ja dünaamiline räsimine andmebaasisüsteemides

Mis on räsimine DBMS-is?

Andmebaasihaldussüsteemides on räsimine tehnika, mille abil otsitakse soovitud andmete asukohta otse kettalt ilma indeksstruktuuri kasutamata. Räsimise meetodit kasutatakse andmebaasi üksuste indekseerimiseks ja otsimiseks, kuna konkreetse üksuse otsimine on kiirem lühema räsivõtme abil, mitte selle algse väärtuse abil. Andmed salvestatakse andmeplokkidena, mille aadress genereeritakse räsifunktsiooni rakendamise teel; mälukoht, kuhu need kirjed salvestatakse, on tuntud kui andmeplokk või andmeämber.

Miks me vajame räsimist?

Siin on olukorrad andmebaasihaldussüsteemis, kus on vaja rakendada räsimismeetodit:

  • Tohutu andmebaasistruktuuri puhul on keeruline otsida kõiki indeksiväärtusi kõigilt tasemetelt ja seejärel jõuda sihtandmeplokki, et saada soovitud andmed.
  • Räsimist kasutatakse andmebaasi üksuste indekseerimiseks ja otsimiseks, sest lühema räsivõtme abil on konkreetse üksuse otsimine kiirem kui algse väärtuse abil.
  • Räsimine on ideaalne meetod andmekirje otsese asukoha arvutamiseks kettal ilma indeksstruktuuri kasutamata.
  • See on ka abistav tehnika sõnastike rakendamisel.

Olulised terminoloogiad räsimises

Siin on räsimisel kasutatavad olulised terminid:

  • Andmete ämber: Andmeämbrid on mälupesad, kuhu kirjeid salvestatakse. Seda tuntakse ka salvestusühikuna.
  • Võti: a DBMS-i võti on atribuut või atribuutide kogum, mis aitab teil tuvastada rea ​​(tuple'i) seoses (tabelis).
  • Räsifunktsioon: kaardilping funktsioon, mis seob kõik otsinguvõtmete komplekti aadressiga, kuhu tegelikud kirjed paigutatakse.
  • Lineaarne sondeerimine: fikseeritud intervall sondide vahel. Selle meetodi puhul kasutatakse uue kirje sisestamiseks järgmist saadaolevat andmeplokki, selle asemel et vanem kirje üle kirjutada.
  • Ruutskoorimine: aitab määrata uue ämbri aadressi, lisades ruutpolünoomi järjestikuse väljundi algse arvutuse tulemusel saadud algväärtusele.
  • Räsi indeks: andmeploki aadress. Räsifunktsioon võib olla lihtne matemaatiline funktsioon või keerukas funktsioon.
  • Double Räsimine: räsitabelites kasutatav meetod kokkupõrgete lahendamiseks teise räsifunktsiooni rakendamise abil.
  • Ämbri ületäitumine: Ämbri ületäitumise seisundit nimetatakse kokkupõrkeks. See on iga staatilise räsifunktsiooni jaoks saatuslik staadium.

Räsitehnikate tüübid

Andmebaasihaldussüsteemides on peamiselt kahte tüüpi räsimise tehnikaid:

  1. Staatiline räsimine
  2. Dünaamiline räsimine

Need kaks erinevad peamiselt selle poolest, kas ämbrite arv on fikseeritud, nagu selgitatakse järgmistes kahes osas.

Staatiline räsimine

Staatilises räsimises jääb saadud andmeämbri aadress alati samaks.

Seega, kui genereerite aadressi näiteks Õpilase_ID = 10 räsifunktsiooni kasutamine mod (3), jääb tulemuseks ämbri aadress alati olema 1Seega ei näe te ämbri aadressis mingit muutust.

Seega jääb staatilises räsimeetodis mälus olevate andmeämbrite arv alati konstantseks.

SEOTUD ARTIKLID

Staatilised räsifunktsioonid

  • Kirje sisestamine: Kui tabelisse on vaja lisada uus kirje, genereeritakse sellele räsivõtme abil aadress. Kui aadress on genereeritud, salvestatakse kirje sellesse asukohta.
  • Otsimine: Kui teil on vaja kirjet hankida, kasutatakse sama räsifunktsiooni andmete salvestamise ämbri aadressi hankimiseks.
  • Kirje kustutamine: Räsifunktsiooni abil saate kõigepealt hankida kirje, mida soovite kustutada, ja seejärel eemaldate kirje sellelt aadressilt mälus.

Staatiline räsimine jaguneb omakorda järgmisteks osadeks:

  1. Ava räsimine
  2. Suletud räsimine

Avage räsimine

Avatud räsimeetodi puhul ei kirjutata üle vana kirjet, vaid uue kirje sisestamiseks kasutatakse järgmist saadaolevat andmeplokki. Seda meetodit tuntakse ka lineaarse sondeerimisena.

Näiteks A2 on uus kirje, mille soovite lisada. Räsifunktsioon genereerib aadressi 222, kuid see on juba hõivatud teise väärtusega. Seetõttu otsib süsteem järgmist andmeämbrit, 501, ja määrab sellele A2.

Kuidas avatud räsimine lineaarse proovimisega töötab
Kuidas Open Hash töötab

Suletud räsimine

Suletud räsimeetodi puhul eraldatakse ämbrite täis saamisel sama räsi jaoks uus ämber ja tulemus lingitakse eelmise järel.

Dünaamiline räsimine

Dünaamiline räsimine pakub mehhanismi, kus andmeämbrid lisatakse ja eemaldatakse dünaamiliselt ja nõudmisel. Selle räsimise meetodi puhul aitab räsifunktsioon luua suure hulga väärtusi ning struktuur kasvab või kahaneb koos andmetega. See sobib hästi tabelite jaoks, mille suurust ei saa ette ennustada, kus staatiline räsimine raiskaks ruumi või ajaks süsteemi üle.

Erinevus tellitud indekseerimise ja räsimise vahel

Allpool on toodud peamised erinevused indekseerimise ja räsimise vahel:

parameetrid Järjestatud indekseerimine Räsimine
Aadressi salvestamine Mälus olevad aadressid sorteeritakse võtme väärtuse järgi, mida nimetatakse primaarvõtmeks. Aadressid genereeritakse alati võtmeväärtuse räsifunktsiooni abil.
jõudlus See võib andmete suurenedes väheneda, kuna andmeid salvestatakse sorteeritult ja iga lisamine, kustutamine või värskendamine muudab nende järjekorda. Parim jõudlus saavutatakse pideva andmete lisamise ja kustutamise korral. Suure andmebaasi puhul muutub räsifailide hooldus kulukamaks.
Kasuta Eelistatud vahemiku otsimiseks, kus andmeid otsitakse kindla vahemiku kohta. Ideaalne konkreetse kirje otsimiseks otsinguvõtme põhjal ja toimib hästi ainult siis, kui otsinguvõtmel on räsifunktsioon.
Mälu haldamine Paljud kasutamata andmeplokid tekivad kustutamis- ja värskendamistoimingutest ning neid ei saa taaskasutamiseks vabastada, seega on vaja regulaarset hooldust. Staatilises ja dünaamilises räsimises hallatakse alati mälu ja staatiliste räsimiste laiendamiseks käsitletakse ämbri ületäitumist.

Lühidalt, vali järjestatud Indekseerimine vahemiku päringute ja võtme täpse vaste otsingute räsimise jaoks.

Mis on kokkupõrge?

Räsi kokkupõrge on seisund, kus kahe või enama andmestiku elemendi räsiväärtused vastavad valesti samale kohale andmestikus. räsilaud.

Kuidas toime tulla räsimise kokkupõrkega

Räsi kokkupõrke vältimiseks on kaks tehnikat:

  1. Ümberkirjutamine: See meetod kutsub esile sekundaarse räsifunktsiooni, mida rakendatakse pidevalt, kuni leitakse tühi pesa, kuhu saab kirje paigutada.
  2. Aheldamine: Aheldamismeetod loob lingitud loendi elementidest, mille võtmed on räsitud sama väärtusega. See meetod nõuab iga tabeli positsiooni jaoks täiendavat lingivälja.

KKK

Staatiline räsimine hoiab fikseeritud arvu ämbreid, seega võib see andmete kasvades ületäituda. Dünaamiline räsimine lisab ja eemaldab ämbreid nõudmisel, seega kohandub see muutuva andmete suurusega ilma täielikku ümberehitust tegemata.

Vahemiku päringute puhul. Räsimine hajutab võtmed ämbrite vahel, seega päring „between” või „more-than” ei saa neid järjekorras käia. Järjestatud indeks hoiab võtmed sorteerituna ja sobib sinna paremini.

Ämber saab ületäitumise, kui sellele räsitakse rohkem kirjeid, kui see mahutab. Staatilises räsimises on see andmete kasvades tavaline ning sellega tegeletakse avatud adresseerimise, aheldamise või ületäitumise ämbrite abil.

Tehisintellekti süsteemid kasutavad räsimist kiireks tunnuste otsimiseks ja räsimistrikiks, mis kaardistab suure kardinaalsusega kategooriad fikseeritud vektoriks. Sarnasuse räsimine grupeerib tõhusalt ka peaaegu duplikaatseid kirjeid.

Ümberhakkimine leiab samast tabelist teise vaba pesa teise funktsiooni abil. Aheldamine hoiab ämbriga seotud lingitud loendi kirjete kokkupõrkeid, seega tabel ise ei täida kunagi pesa kaks korda.

Võta see postitus kokku järgmiselt: