online kép - Fájl  tube fájl feltöltés file feltöltés - adja hozzá a fájlokat online fedezze fel a legújabb online dokumentumok Kapcsolat
   
 

Letöltheto dokumentumok, programok, törvények, tervezetek, javaslatok, egyéb hasznos információk, receptek - Fájl kiterjesztések - fajltube.com

 

Online dokumentumok - kep
   

kategória
 

Biológia állatok Fizikai Földrajz Kémia Matematika Növénytan Számítógépes
Filozófia
Gazdaság
Gyógyszer
Irodalom
Menedzsment
Receptek
Vegyes

 
 
 
 
 




































 
 

 

 

Hashelés és ritka indexes szervezési módszerek

számítógépes

Fájl küldése e-mail Esszé Projekt


egyéb tételek

 
SSADM Strukturalt rendszerelemzési és -tervezési módszer
A videokonferencia mint prezentació
Windows XP (magyar) új kapcsolat létrehozasa
A programozasi technikak és jellemzőik
Hattértarak és jellemzöik
MS Project
Tömörítés, hibadetektalas és javítas
Logikai algebra, logikai műveletek
Processzus ütemezése
Szamítógép halózatok
 
 
 


Hashelés és ritka indexes szervezési módszerek

1. Adatbázisok alapvető fizikai szervezési elvei

Ezek a következők:

1. Kupac (heap) (erről az előző rételben már volt szó)

2. Hash

3. Indexelt szervezés.

2. Hash-szervezés

Elsősorban a vödrös (bucket) hash-elés és változatai használatosak. Az alapmódszerben adott:

ˇ  B db vödör (egy vödör egy kis - kevés lapból álló - lap-láncot jelent);

ˇ  egy vödörkatalógus (0-tól (B-1)-ig indexelt tömb)

ˇ  és a h: -> [0,B-1] hash-függvény, mely legyen gyorsan számítható és ne okozzon túl sok ütközést (ütközés: két kulcshoz h ugyanazt a tömb-cellát rendeli)

Ábrázolva:


A hash-függvény a K kulcsú rekordh 929j91j oz az i. vödröt sorsolja: h(K) = i.

A keresés a sorsoláshoz egész hasonlóan zajlik: a K' rekordot keresve ki kell számítani a h(K') értékét és a megfelelő vödörhöz kell fordulni. Ez a módszer átlagos értelemben igen jó (a vödrök nem lesznek túl kicsik / túl nagyok); átlagban konstans lapelérés elég.

Tipikusan B-t prímnek választják, és a hash-függvényt így határozzák meg:

h(K) := K (mod p).

Az alapmódszer hibája, hogy statikus: rögzítve a vödörkatalógus méretét előfordulhat, hogy túl hosszú lap-láncok alakulnak ki a vödrökben, vagyis a szervezés nem követi dinamikusan az állomány méretváltozásait.

Javaslatok a statikusság kiküszöbölésére:

1. Dinamikus hash-elés

Ötlete: a szófa és a vödrös hash-elés ötvözete segít. h(k)-t fogjuk fel úgy, mint egy bitsorozatot.

A szerkezet így épül fel:


A vödrök itt is lap-láncok, de méretük fix (bár rendszerenként más és más lehet).

Keresés: h(K) bitjeit olvasva lehet megtalálni a kívánt vödröt és benne a megfelelő lapot.

Kezdőállapot:


Ha egy vödör megtelik, akkor szét kell vágni. Például a 01... kezdetű, 2-es számú vödör telt meg. Ebből csinálunk két vödröt a 010... és 011... -gyel kezdődő lapok számára.


Van értelme a testvér-vödrök összevonásának is. Ha törlünk egy vödörből, akkor megnézzük a testvérét: ha együtt jobban ki vannak töltve, akkor érdemes összevonni őket.

Természetesen a dinamikus hash-elés az alapmódszernél nehézkesebb és költségesebb. Ez részint attól is függ, hogy mi kerülhet be a belső memóriába (esetleg az egész szerkezet vagy csak a gyökérhez közeli csúcsok, stb.). A költséget ezért nehéz pontosan megbecsülni.


2. Növelhető (extendable) szervezés

A módszer paramétere: d pozitív egész szám, ez a katalógus globális mélysége. A katalógusnak ekkor 2d számú bejegyzése lesz. h(K) továbbra is egy bitsorozatnak tekinthető.

A szerkezet így épül fel d=3 esetén:

d' a lokális mélység. Pl. d'=3=d => a katalógus elemeit címző háromjegyű cím mindhárom bitjére szükség van a vödörben; benne minden rekord 000-val kezdődik. Ha d'=2, akkor az azt jelenti, hogy itt elég 2 bit a rekord eléréséhez, elhelyezéséhez.

A szervezés során mindvégig igaz, hogy d<= d'.

Tehát a globális mélység a használható, a lokális mélység pedig a használt bitek számát jelenti.

Túlcsordulás esetén a vödör lapjait két vödörben próbáljuk elhelyezni.

ˇ d (azaz új, nagyobb táblát készítünk), ha a d' lokális mélységű vödör túlcsordult;

ˇ d csökken (azaz új, kisebb táblát készítünk), ha minden d' < d.

3. Indexelt szervezés

A módszer kihasználja a kulcsok rendezettségét és alapvető műveletek megvalósítására szolgál.


Adott a tényleges, tárolni kívánt "fő" állomány ("nagy" rekordokkal). Felette helyezkedik el az index állomány, mely (kis) index rekordokból áll. A kettő közötti összefüggések segítik a lapok elérését.




Az index rekordokból - kis méretük miatt - sok férhet el egy lapon.


Az index rekord felépítése:


Az indexelés fajtái:

a.) Egyszintes ritka indexelés (ISAM)

ˇ  az index rekordok kulcs szerint rendezve vannak az index állományban elhelyezve;

ˇ  mutatójuk a fő állományba mutat.

Kapcsolat a mutató és a mutatott rekord között:


K az első (legkisebb) kulcsérték a mutatott lapon.

Keresés: a K kulcsú rekordot keresve az index állományban megkeressük a legnagyobb K' kulcsú index rekordot, amelyre K <= K' teljesül. Ekkor biztosak lehetünk abban, hogy K' mutatóját, m-et követve megkapjuk az "esélyes lapot", ahol K rekordja talán megtalálható - feltéve, hogy egyáltalán része a szerkezetnek.

A ritka indexrekordok között - kihasználva a rendezettséget - kereshetünk (feltéve, hogy N db index lap van):

ˇ  lineáris kereséssel: az index állományt az elejétől kezdve szekvenciálisan járjuk be. A keresés időigénye az index lapok számával arányos, ~ N lapelérés (N<<főállomány lapjainak száma).

ˇ  bináris kereséssel: felezéses módszerrel járjuk be az index állományt. Az időigény ~ logN lapelérés.

ˇ  interpolációs kereséssel: (pl. a telefonkönyvben így keresünk) szükség van valamilyen tárolt tudásra, statisztikára az index állomány bejárásában. A keresés jósága ennek a tudásnak a minőségéhez mérhető, ~ loglogN lapelérés.

A további műveletekben lényeges, hogy mennyire mozgathatók a fő állomány rekordjai: szabadok avagy kötöttek.

Tegyük fel hogy a fő állomány rekordjai szabadok, vagyis lógó mutatóktól nem kell tartani (a fő állomány rekordjaira csak az index rekordok mutatói mutatnak).


ˇ  beszúrás: a rekordok helyét kereséssel határozzuk meg. Túlcsordulás esetén lapvágást kell végezni (ez a B-fáknál megismert módszert jelenti) és ennek megfelelően új index rekordot létrehozni - ami esetleg az index állományban is lapvágást okozhat.



ˇ  törlés: a lapvágás inverzét, a lapösszevonást kell alkalmazni szükség esetén.

ˇ  tólig: a szervezés támogatja ezt a műveletet, ami adott kulcs-értékek közötti rekordok kilistáztatására szolgál.

A stratégia következménye, hogy a lapok legalább félig telítve lesznek a főállományban.

Ha a fő állomány tömör, akkor a fenti műveletek nehézségekbe ütköznek. Ezért találták ki a módszer statikus változatát (kötött rekordokra).


b.) Egyszintes ritka indexelés - statikus változat

Itt az index állomány előre elkészül; az index rekord pedig nem a főállomány egy lapjára, hanem egy "lap-oszlopára", listájára mutat.


A ritka index szabad és kötött változata között a költség szempontjából drámai különbség van.

További módszerek: (a köv. tétel anyaga)

c.) Többszintes indexelés

d.) Sűrű indexelés

Találat: 1357