4. gyakorlat

Indexelés

• Elsődleges index: feltehetjük, hogy a fájl rendezett
• Sűrű index: minden rekordhoz tartozik egy mutató az index fájlban
• Az index kulcs-mutató párjai kevesebbet helyet foglalnak, mint a rekordok
  • Gyorsabban lehet benne keresni (logaritmikus keresés)
• Ritka index: minden blokkhoz egy mutató tartozik az index fájlban
  • A kulcs az adatblokk első rekordjának kulcsa
• Több szintű index: ha az indexre indexet készítünk, akkor a rekordok

elérését még hatékonyabbá tehetjük.

• A második szintű indextől kezdve az indexek kötelezően ritkák

B-fák

• A ma használt adatbázisokban az alapértelmezett index egy B-fa
• Általában három szintesek
• Fontos a csúcsokban lévő kulcsoks száma
• A levélcsúcsban a rowid-k vannak
• Egy csúcsban
  • N kulcsű
  • N + 1 mutató

Feladatok

Jelölések

• T(R) – az R reláció sorainak a száma
• bf(R) – blokkolási faktor, azaz R reláció hány sora fér el egy blokkban
• B(R) – az R reláció sorainak tárolásához szükséges blokkok száma

1. feladat

• R: tábla
  • T(R) = 10 000
  • bf(R) = 20
• I1: sűrű index
  • bf(I1) = 100
• I2: ritka index
  • bf(I2) = 100

Számoljuk ki a következőket: B(R), B(I1), B(I2)

B(R) = T(R) / bf(R) = 10000 / 20 = 500

B(I1) = T(R) / bf(I1) = 10000 / 100 = 100

B(I2) = B(R) / bf(I2) = 500 / 100 = 5

B(I3) = ? / ? = 100 / 100 = 1

(TODO: I3 specifikáció a videó alapján)

2. feladat

Végezzük el az előző feladatot úgy, hogy a blokkok csak 80%-ban lehetnek tele!

• R: tábla
  • T(R) = 10 000
  • bf(R) = 20 * 0,8 = 16
• I1: sűrű index
  • bf(I1) = 100 * 0,8 = 80
• I2: ritka index
  • bf(I2) = 100 * 0,8 = 80 Számoljuk ki a következőket: B(R), B(I1), B(I2)

B(R) = T(R) / bf(R) = 10000 / 16 = 625

B(I1) = T(R) / bf(I1) = 10000 / 80 = 125

B(I2) = B(R) / bf(I2) = 625 / 80 = 7,81 ~ 8 (kerekítünk)

3. feladat

• T(R) = 1 000 000
• bf(R) = 20
• Egy "A" oszlopra készítünk B+ fa indexet, amelyre bf(I) = 50 Számoljuk ki a B(I)-et

• Alsó szint: T(R) / bf(I) = 1 000 000 / 50 = 20 000
• 1. szint: 20 000 / 50 = 400
• 2. szint: 400 / 50 = 8
• Felső szint: 8 / 50 = 0,16 ~ 1

(Addig megyünk fel, amíg 1 nem lesz.)

Összesen: B(I) = 20 000 + 400 + 8 + 1 = 20 409

Hány blokkot kell beolvasnunk egy konkrét sor megtalálásához a legrosszabb esetben, ha:

• a tábla sorai rendezetlenül vannak tárolva és nem használunk indexet
  • 50 000
• a tábla sorai rendezetten vannak tárolva és nem használunk indexet
  • 10
• a fenti B+ fa indexet használjuk
  • 5

Bitvektor

DNEV FOGLALKOZAS BELEPES OAZON SMITH CLERK 1980 20 ALLEN SALESMAN 1981 30 WARD CLERK 1981 30 JONES MANAGER 1983 20 MARTIN SALESMAN 1981 30 BLAKE MANAGER 1983 30 CLARK MANAGER 1981 10 SCOTT ANALYST 1982 20 KING PRESIDENT 1981 10 TURNER CLERK 1983 30

1981-ben léptek be és a foglalkozásuk hivatalnok (CLERK)

20-as osztályon dolgoznak és a foglalkozásuk MANAGER