Kivonatolás a DBMS-ben: statikus és dinamikus kivonatolási technikák
Fiona Brown
⚡ Okos összefoglaló
A DBMS-ben a hashelés egy olyan technika, amely közvetlenül a kulcsából számítja ki egy rekord lemezhelyét, indexbejárás nélkül. A hash függvény a keresési kulcsokat adattárolókhoz rendeli, és a statikus vagy dinamikus hashelés kezeli ezeknek a tárolóknak a növekedését.
Mi az a kivonatolás a DBMS-ben?
Az adatbázis-kezelő rendszerekben a hashelés egy olyan technika, amely lehetővé teszi a kívánt adatok helyének közvetlen keresését a lemezen indexstruktúra használata nélkül. A hashelési módszert az adatbázisban lévő elemek indexelésére és lekérésére használják, mivel gyorsabb egy adott elemet a rövidebb hashelt kulcs használatával keresni az eredeti érték helyett. Az adatokat adatblokkok formájában tárolják, amelyek címét hash függvény alkalmazásával generálják; a memóriahely, ahol ezeket a rekordokat tárolják, az úgynevezett adatblokk vagy adatgyűjtő.
Miért van szükségünk hashelésre?
Íme néhány helyzet egy adatbázis-kezelő rendszerben, amikor alkalmazni kell a hashelési módszert:
- Egy hatalmas adatbázis-struktúra esetén nehéz az összes indexértéket az összes szinten átkeresni, majd elérni a céladatblokkot a kívánt adatok megszerzéséhez.
- A hashelést az adatbázis elemeinek indexelésére és lekérésére használják, mivel egy adott elem keresése gyorsabb a rövidebb hashelt kulcs használatával, mint az eredeti értékkel.
- A hashelés ideális módszer az adatrekord lemezen való közvetlen helyének kiszámítására indexstruktúra használata nélkül.
- Hasznos technika a szótárak megvalósításához is.
Fontos terminológiák a hashingban
Íme a hashelés során használt fontos terminológiák:
- Adattároló: Az adattárolók olyan memóriahelyek, ahol a rekordokat tárolják. Tárolási egységnek is nevezik.
- Kulcs: a DBMS kulcs egy attribútum vagy attribútumok halmaza, amely segít azonosítani egy sort (tuple-t) egy relációban (táblában).
- Hash függvény: egy térképping függvény, amely a keresési kulcsok összes halmazát ahhoz a címhez rendeli, ahol a tényleges rekordok találhatók.
- Lineáris mérés: fix intervallum a próbák között. Ebben a módszerben a következő elérhető adatblokkot használják az új rekord bevitelére a régebbi rekord felülírása helyett.
- Másodfokú próba: segít meghatározni az új vödörcímet egy kvadratikus polinom egymást követő kimenetének hozzáadásával az eredeti számítás által adott kezdőértékhez.
- Hash index: az adatblokk címe. Egy hash függvény lehet egyszerű matematikai függvény vagy összetett függvény.
- Double Kivonatolás: egy hash táblákban használt módszer az ütközések feloldására egy második hash függvény alkalmazásával.
- Vödör túlcsordulás: A vödör túlcsordulás állapotát ütközésnek nevezzük. Ez végzetes állapot bármely statikus hash függvény számára.
A kivonatolási technikák típusai
A DBMS-ben főként kétféle hashelési technika létezik:
- Statikus kivonatolás
- Dinamikus hashelés
A kettő főként abban különbözik, hogy a vödrök száma rögzített-e, amint azt a következő két szakasz kifejti.
Statikus kivonatolás
Statikus hashelés esetén az eredményül kapott adattároló címe mindig ugyanaz marad.
Tehát, ha generálsz egy címet, mondjuk, Diák_azonosító = 10 a hash függvény használata mod(3), az eredményül kapott csoportcím mindig ez lesz 1Tehát nem fogsz semmilyen változást látni a vödör címében.
Ezért a statikus hashelési módszerben a memóriában lévő adatvödrök száma mindig állandó marad.
Statikus hash-függvények
- Rekord beszúrása: Amikor egy új rekordot kell beszúrni a táblázatba, a hash kulcs segítségével generálunk hozzá egy címet. A cím generálása után a rekord ezen a helyen tárolódik.
- Keresés: Amikor le kell kérni a rekordot, ugyanazt a hash függvényt kell használni az adatok tárolására szolgáló vödör címének lekéréséhez.
- Rekord törlése: A hash függvény használatával először beolvassuk a törölni kívánt rekordot, majd eltávolítjuk a rekordot a memóriában található címről.
A statikus hashelést tovább osztják:
- Nyissa meg a kivonatolást
- Zárt hasheléssel
Nyissa meg a kivonatolást
A nyílt hashelési módszerben a régebbi rekord felülírása helyett a következő elérhető adatblokkot használják az új rekord beviteléhez. Ez a módszer lineáris próbaként is ismert.
Például az A2 egy új rekord, amelyet be szeretne szúrni. A hash függvény a 222-es címet generálja, de ezt már egy másik érték foglalja el. Ezért a rendszer a következő adattárolót, az 501-et keresi, és hozzárendeli az A2-t.
Zárt hasheléssel
A zárt hashelési módszerben, amikor a vödrök megtelnek, egy új vödröt foglalnak le ugyanahhoz a hashhez, és az eredményt az előző után linkelik.
Dinamikus hashelés
A dinamikus hashelési módszer egy olyan mechanizmust kínál, amelyben az adattárolók dinamikusan és igény szerint adhatók hozzá és távolíthatók el. Ebben a hashelési módszerben a hash függvény segít nagyszámú érték létrehozásában, és a struktúra az adatokkal együtt növekszik vagy zsugorodik. Ezáltal jól illeszkedik azokhoz a táblázatokhoz, amelyek mérete előre nem jelezhető előre, ahol a statikus hashelési módszer vagy helyet pazarolna, vagy túlcsordulna.
Különbség a rendezett indexelés és a hashelés között
Az alábbiakban a hashelési és indexelési műveletek közötti főbb különbségeket ismertetjük:
| paraméterek | Rendezett indexelés | hashelés |
|---|---|---|
| Cím tárolása | A memóriában lévő címek egy kulcsérték, az úgynevezett elsődleges kulcs szerint vannak rendezve. | A címek mindig a kulcsérték hash függvényével jönnek létre. |
| Teljesítmény | Az adatmennyiség növekedésével csökkenhet, mivel az adatok rendezve tárolódnak, és minden beszúrás, törlés vagy frissítés átrendezi azokat. | A teljesítmény folyamatos adatbevitellel és -törléssel érhető el. Egy hatalmas adatbázis esetében a hash fájlok karbantartása költségesebbé válik. |
| Használ | Tartománylekéréshez előnyös, ahol egy adott tartományra vonatkozóan kérik le az adatokat. | Ideális egy adott rekord lekérésére a keresési kulcs alapján, és csak akkor teljesít jól, ha a hash függvény a keresési kulcson van. |
| Memóriakezelés | Sok fel nem használt adatblokk törlési és frissítési műveletekből származik, és nem adhatók fel újrafelhasználásra, ezért rendszeres karbantartásra van szükség. | Statikus és dinamikus hashelés esetén a memóriát mindig kezelik, és a vödör túlcsordulást kezelik a statikus hashelés kiterjesztése érdekében. |
Röviden, válasszon rendezett Indexelés tartománylekérdezésekhez és hasheléshez a kulcs pontos egyezésű kereséseihez.
Mi az ütközés?
A hash ütközés olyan állapot, amelyben az adathalmaz két vagy több eleméből származó hashek helytelenül ugyanarra a helyre kerülnek leképezésre az adathalmazban. hash asztal.
Hogyan kezeljünk egy hashelési ütközést
Kétféle technikát alkalmazhatsz a hash ütközések elkerülésére:
- Újragondolva: Ez a metódus egy másodlagos hash függvényt hív meg, amelyet folyamatosan alkalmaznak, amíg nem találnak egy üres helyet, ahová egy rekordot el lehet helyezni.
- Láncolás: A láncolási metódus egy láncolt listát hoz létre azokból az elemekből, amelyek kulcsai ugyanarra az értékre hash-elődnek. Ez a metódus minden táblapozícióban egy extra link mezőt igényel.
