Adatbázisok - Fizikai szervezés gyakorlat

Az aktuális tematika és feladatsor elérhető a tárgyhonlapon.

Feladatok

1. Egy 1000 rekordból álló állományt ritka index szervezéssel tárolunk. A rekordhossz 850 byte, egy blokk kapacitása (a fejrészt nem számítva) 4000 byte. A kulcs 50 byte-os, egy mutatóhoz 18 byte kell.

• Hány rekord fér el egy blokkban?
  • Blokkméret osztva rekordméret alsó egész része: $\lfloor 4000/850\rfloor =4$
• Hány blokkot foglal el az index struktúra, és mennyit a teljes állomány?
  • Egy blokkban 4 rekord fér el, ezért $\lceil 1000/4\rceil =250$ blokk kell a rekordoknak. Ritka indexnél mindegyik rekordot tartalmazó blokkhoz kell egy pointer, és a blokk első rekordjának kulcsa, így 68 byte-os egységeket tárolunk, ebből egy blokkban elfér $\lfloor 4000/68\rfloor =58$ darab, tehát mind a 250 blokkhoz tartozó kulcs-pointer párnak $\lceil 250/58\rceil =5$ blokk kell. Így az indexstruktúra 5, a teljes állomány 255 blokkot foglal.
• Melyik szinten, melyik blokkokban és blokkok között követeljük meg a rendezettséget?
  • Azt követeljük meg, hogy az indexállományban kulcs szerint növekvő sorrendben legyenek a kulcs-pointer párok (blokkon belül, és az egész állományban egyaránt). Valamint, mindegyik rekordot tartalmazó blokk csak olyan rekordokat tartalmazzon, amik a blokkra mutató pointerhez az indexben tartozó kulcs, és az indexben azt követő kulcs között van (pl. ha egy egész szám a kulcs, és az index a 10, 33, 57, 91, 145 kulcsokat tartalmazza, akkor az 57-hez tartozó pointer által kijelölt blokkban minden rekord kulcsa 57-nél nagyobb egyenlő, és 91-nél kisebb legyen) Viszont a rekordokat blokkon belül nem fontos rendezetten tárolni, és a rekordok blokkjai sem kell, hogy sorrendben legyenek a háttértáron (elég, ha a rájuk mutató indexbejegyzések rendezve vannak).
• Mennyi ideig tart legfeljebb egy rekord tartalmának kiolvasása, ha feltételezzük, hogy az index struktúra már benne van az operatív tárban? (Egy blokkművelet ideje 5 ms).
  • Az indexstruktúrából azonnal tudjuk, hogy melyik blokkot kell betöltenünk, tehát 5 ms.
• Mennyi ideig tart legfeljebb egy rekord tartalmának kiolvasása, ha az index struktúra nem fér el az operatív tárban?
  • Először meg kell keresni a megfelelő indexbejegyzést. Bináris kereséssel legfeljebb $1+\lfloor \log _{2}k\rfloor$ blokk betöltésével (ahol k az index blokkjainak száma) megvan az indexállomány megfelelő blokkja, ezután már egy lépésben betölthető a rekord. Így összesen $5{\text{ms}}\cdot (1+1+\lfloor \log _{2}5\rfloor )=20{\text{ms}}$ alatt megvan a rekord.

2. Vödrös hash szervezéssel tárolunk egy állományt, melyben a rekordok száma 15000. Egy rekord hossza 120 byte, egy blokkba 4000 byte fér el, egy kulcs hossza 25 byte, a mutatóé 8 byte. A szervezést 10 vödörrel oldjuk meg. (Feltételezhetjük, hogy a hash függvény egyenletesen osztja el a kulcsokat.)

• Mekkora az átlagos vödörméret?
  • $15000/10=1500$.
• Mekkora diszkterület szükséges a teljes struktúra tárolásához (valódi méret, illetve felhasznált tárterület)?
  • Egy blokkban a vödör következő blokkjára mutató pointeren kívül $\lfloor (4000-8)/120\rfloor =33$ rekord fér el. Egy vödörbe 1500 rekord kerül, ehhez $\lceil 1500/33\rceil =46$ blokk kell vödrönként, ez rekordtároláshoz összesen 460 blokk. A vödörben (az indexszel ellentétben) csak pointereket tárolunk, ez 80 byte, ami elfér egy blokkban. Tehát összesen kell 461 blokk, ami 1844000 byte felhasznált tárhely. Ami ebből ténylegesen hasznosítva van, az a 15000 rekord szorozva 120 byte-tal, plusz a 80 byte hash katalógus, ami 1800080 byte.
• Mennyi az átlagos rekordelérési idő, ha a blokkelérési idő 5 ms? (A keresés során a vödörkatalógust a memóriában tároljuk.)
  • Miután kiszámítottuk a hash-t és a katalógusból kikerestül a vödör első blokkjának kezdőcímét, egy 46 blokkból álló vödrön kell lineáris keresést végeznünk, ez (elhanyagolva, hogy az utolsó blokk nincs teljesen tele) átlagosan (46 + 1) / 2 blokk olvasását, 117.5 ms-t igényel.
• Mekkora legyen a vödrök minimális száma, ha a keresés során átlagosan 5 blokkelérési idő alatt akarjuk megtalálni a keresett rekordot?
  • Ekkor a vödörben lévő blokkok n számára $(n+1)/2=5$ teljesül, tehát n = 9 blokk kerülhet legfeljebb egy vödörbe. Ebben a 9 blokkban legfeljebb $9\cdot 33=297$ rekord fér el, és a vödrök k számára így $\lceil 15000/k\rceil \leq 297$ teljesül, így $\lceil 15000/297\rceil \leq k$, vagyis $k\geq 51$

3. Egy 1000 rekordból álló állományt szeretnénk tárolni úgy, hogy két kulcs szerint is kereshető legyen. A rekordhossz 120 byte, egy blokk kapacitása (a fejrészt nem számítva) 1000 byte. A kulcs 50 byte-os, egy mutatóhoz 20 byte kell. Javasoljon tárolási eljárást a fenti problémára! Mekkora diszkterület szükséges a teljes struktúra tárolásához?

• A két kulcs szerinti kereshetőséghez kell két sűrű index, illetve mindkettő tetejére egy-egy ritka index. Az első sűrű index az első kulcs szerint lesz rendezve, a második a második szerint, így ha az első kulcs szerint akarunk keresni, az első ritka indexen és az első sűrű indexen keresztül tehetjük meg, a másiknál hasonlóan.
• Rekordból egy blokkban elfér $\lfloor 1000/120\rfloor =8$, ezért a rekordok tárolásához $\lceil 1000/8\rceil =125$ blokk kell. A sűrű index blokkjaiban egyenként $\lfloor 1000/70\rfloor =14$ kulcs-mutató pár fér el, így egy sűrű indexhez $\lceil 1000/14\rceil =72$ blokk kell. A ritka index a sűrű index mindegyik blokkjához tartalmaz egy kulcs-mutató párt, így 72 bejegyzés van benne, ehhez kell $\lceil 72/14\rceil =6$ blokk. Mivel az állományt egyszer tároljuk, viszont van két sűrű, és két ritka indexünk, ezért összesen kell $125+2\cdot 72+2\cdot 6=281$ blokk, ami, ami 281000 byte tárhely.

-- csacsiga - 2008.12.03.

4. Egy állományt kétféle szervezéssel tudunk tárolni: sűrű index, majd erre épített egyszintes ritkaindex vagy pedig hash algoritmussal. Az állományon néha intervallumkeresést is meg kell valósítani! Melyik szervezési módszert válasszuk? Adjon értelmes alsó becslést a szükséges blokkok számára az alábbi feltételek mellett:

• az állomány 3 000 000 rekordból áll
• egy rekord hossza 300 byte
• egy blokk mérete 4000 byte
• a kulcshossz 45 byte
• egy mutató hossza 5 byte

• Intervallumkeresést hash-sel nem lehet hatékonyan csinálni (mivel egy jó hash szétszórja a vödrökbe bármely intervallum elemeit), ezért ritka index kell.
• Rekordból egy blokkban elfér $\lfloor 4000/300\rfloor =13$, így a rekordoknak $\lceil 3000000/13\rceil =230770$ blokk kell. A sűrű indexben 50 byteos kulcs-mutató párokat tárolunk, ebből elfér egy blokkban $\lfloor 4000/50\rfloor =80$, a sűrű indexnek $\lceil 3000000/80\rceil =37500$ blokk kell. A ritka index mindegyik sűrű indexbeli blokkhoz tartalmaz egy kulcs-mutató párt, ehhez $\lceil 37500/80\rceil =469$ blokk kell. Ez összesen $230770+37500+469=268739$ blokk.

5. Egy 10 000 000 rekordból álló állományt szeretnénk B* fa szervezéssel tárolni. A rekordhossz 850 byte, egy blokk kapacitása (a fejrészt nem számítva) 4000 byte. A kulcs 50 byte-os, egy mutatóhoz 18 byte kell. Legalább hány blokkra van szükség? Mennyi az átlagos rekordelérési idő, ha a memóriában egy blokk fér el?

850 byte / rekord és 4000 byte / blokk, $\lfloor 4000/850\rfloor =4$ rekord / blokk → $\lceil 10000000/4\rceil =2500000$ blokk kell az adatoknak.

Egy indexstruktúra 50 + 18 = 68 byte, $\lfloor 4000/68\rfloor =58$ index / blokk → $\lceil 10000000/58\rceil =172414$ blokk a sűrű indexeknek.

172414 ritka index bejegyzés, ennyi levele van a B*-fának, ennek tárolásához $\lceil 172414/58\rceil =2973$ blokk kell. A fa korábbi szintjeihez $\lceil 2973/58\rceil =52$ és $\lceil 52/58\rceil =1$ blokk kell. Ha a blokkok számára nem lenne szükség, a fa szintjeinek számát logaritmussal is megkaphatjuk: $\lceil \log _{58}2973\rceil +1=3$.

$2500000+172414+2973+52+1=2675440$ blokk szükséges összesen a teljes struktúra tárolásához. Az átlagos blokkelérési idő a B*-fa bejárása a gyökértől egy levélig, a sűrű index olvasása és az adatblokk olvasása: $3+1+1=5$ blokkművelet.

-- csacsiga - 2008.12.02. -- ocsi - 2009.11.11.

A megoldás szerintem rossz. 59 index/blokk van, mival a B*-fában szokás k-1 kulcsot tárolni k mutatóhoz (könyv). 58*68=3944 bájt, így még a 18 bájtos mutatónak ott a hely. Innentől ugyanúgy kell számolni, csak 59-cel. -- Fonok - 2012.01.10.

Illetve mivel nincs szükség a több kulcs szerinti keresésre, így a sűrű index is elhagyható.

6. Gondolkodtató kérdések

• Elképzelhető-e sűrű index felhsználása hash szervezés esetén?
• Mik a hash szervezés előnyei, hátrányai a B* fával szemben?
• Milyen adatszerkezetet tudsz elképzelni egy térkép-szoftver adatbázisának?
• Milyen sorrendben kell beszúrnunk a rekordokat egy B* fába ahhoz, hogy a legtöbb helyet pazaroljuk?
• Legfeljebb hány ritka index építhető közvetlenül egy heap-szervezésű állományra?
• Milyen plusz feladataink vannak beszúráskor, illetve törléskor, ha sűrű indexek segítségével több B* fát építünk az adatbázisunkra?
• Lehet értelme egy kulcs szerint indexelt (B*) adatbázis esetén is használni sűrű indexet? Mit nyerünk vele, és mennyit? Mitől függ, hogy mennyit nyerünk?
• Milyen nehézségeink adódnak, ha a töredékblokkokat is fel szeretnénk használni a merevlemezen?
• Miben különbözik egy kicsi és egy nagy bokkméretű llemezen tárolt adatbázis?
• Miért nem beszéltünk arról, hogy blokkon belül hogyan tároljuk az a adatokat?
• *Helyezd el a következő kifejezéseket a táblázatban: "blokknyi" "egyetlen"

	hány rekordot jelöl egy bejegyzése	hány rekordot jelöl ki egy pointer-érték
Sűrű index
ISAM

• Hogyan változnának meg az adatbázisok, ha a jövőben a fizikai memóriában (véletlen hozzáférésű tár) helyezkedne el az adatbázisunk?

Gyakorló feladatok

1. Milyen módszerekkel támogatható a több kulcs szerinti keresés?

2. Egy 25 000 rekordból álló állományt szetetnénk ritka index (ISAM) szervezéssel tárolni. A rekordhossz 850 byte, egy blokk kapacitása (a fejrészt nem számítva) 4000 byte. A kulcs 50 byte-os, egy mutatóhoz 18 byte kell.

• Legalább hány blokkra van szükséga a teljes struktúra tárolásához?
• Mennyi ideig tart legfeljebb egy rekord tartalmának kilovasása, ha az operatív tárban rendelkelzésünkre álló szabad hely 6000 byte? (egy blokkművelet ideje 5msec)
• Segít-e a rekordhozzáférési idő csökkentésében, ha 10-szer (100-szor) ennyi szabad memóriával gazdálkodunk? Hogyan célszerű a többletmemóriát felhasználni?

3. Egy 15525 rekordból álló állományt szeretnénk ritka index (ISAM) szervezéssel tárolni. A rekordhossz 850 byte, egy blokk kapacitása (a fejrészt nem számítva) 4000 byte. A kulcs 50 byte-os, egy mutatóhoz 18 byte kell.

• Legalább hány blokkra van szükség?
• Mennyi ideig tart legfeljebb egy rekord tartalmának kilovasása, haz az operatív tárban rendelkezésünkre álló szabad hely 5000 byte? Segít-e a legnagyobb rekordhozzáférési idő csokkentésében, ha 10-szer (100-szor) ennyi szabad memóriával gazdálkodhatunk?

4. Egy állományt sűrű index, majd erre épített egyszintes rikta index segítségével szetnénk tárolni. Adjon értelmes alsó becslést a szükséges blokkok számára az alábbi feltételek mellett:

• az állomány 3x10^6 rekordból áll
• egy rekord hossza 300 byte
• egy blokk mérete 1000 byte
• a kulcshossz 45 byte
• egy mutató hossza 5 byte

5. Egy 270 000 rekordból álló állományt akarunk tárolni. Két lehetőség közül választhatunk: vagy sűrű indexre épített 1 szintes rikta indexet használunk, vagy 3 szintes ritka indexet. Melyik megoldást lehet kevesebb lap felhasználásával megvalósítani, ha még azt is el szetnénk érni, hogy sem az indexállományban, sem a főállományban ne legyenek 80%-nál telítettebb lapok? Tudjuk hogy egy lap mérete 1900 byte, egy rekord hossza 300 byte, a kulcs hossza 35 byte, a mutató hossza pedig 15 byte.

6. Egy adatabázisban egymilliárd rekordot akarunk tárolni. Egy rekord mérete 100 byte, a blokkémret 4000 byte. Egy blokkművelet 5msec hosszó. Két kulcs van, mindkettő 10 byte-os. A mutatók 32 bitesek. Az egyszerűség kedvéért feltételezzük, hogy egyszerre csak egy blokk fér el a memóriában.

• Javasljon tárolási módszert, ha mindkét kulcs szerint akarunk majd keresni úgy, hogy a keresés maximum 40ms-t vegbyen igénybe. A módszernek támogatnia kell az intervallumkeresést is. Készítsen magarázó ábrát!
• Egy konkrét keresés a rekordok várhatóan 8%-át adja eredményül. Adjon minél hatákonybb módszert a keresésre!

7. Vödrös hash alkalmazása esetén mit szükséges módosítani az adattároló struktúrán úgy, hogy az adatalérési idő megfeleződön?

8. Egy adatsruktúrában hash alapú tárolást építünk ki egy CD lemezeket tároló adatbázisban. Minden CD-ről eltároljuk, hogy képeket, zenéket, videót vagy adatot tárol. Mindezt egy karakter tipusú mezőben: K,Z,V,A. Milyen hash fv-t célszerű választani, ha ezen mezőre szeretnénk alapozni a hash tárolást? Mi a mező kardinalitása, mi lesz a doménje?

9. Egy adatbázisban szeretnénk 1 000 000 rekordot tárolni vödrös hash szervezéssel. 1 rekord mérete 110 byte, 1 blokk 3000 byte, 1 kulcs 25 byte, 1 mutató pedig 64 bit méretű. A rekordelérési idő max. 20 msec, a blokkelérés 5 msec. A vödörkatalügus befér a memóriába, a hash függvény egyenletesen szór.

• Mennyi az átlagos rekordelérési idő?
• A vödörkatalógus hány byte-ot foglal el a memóriában?
• Mennyi többletmemóriára lenne szükség, hogy a rekordelérési idő a felére csökkenjen?

-- G - 2008.11.08.