Előadáshoz kapcsolódó elméleti feladatok a "zöldkönyvből"
Indexstruktúrák I.

Feladatok - Molina-Ullman-Widom: Adatbázisrendszerek megvalósítása
                    a "zöld könyv" 4.fejezetének példái és feladatai alapján
>> Tk.4.1. Indexek szekvenciális fájlokon
>> Tk.4.2. Másodlagos indexek
>> Tk.4.3. B+ fák
>> Tk.4.4. Tördelőtáblázatok (Hasítóindex szervezés)

Segédanyagok: Kiss Attila Adatbázisok-2 előadása fizika.ppt  (1-66.o.)
+  Oracle 10g "Concepts" doksiban  Part II. Oracle Database Architecture
     >> 5. Schema Objects és itt >> Overview of Indexes 
      
Tk.4.1. fejezete: Indexek szekvenciális fájlokon
 
4.1.1.feladat, lásd előadás fizika.p26 és fizika.p34
   - Minden blokkba 3 rekord, vagy 10 indexrekord (érték-mutató pár) fér.
     Összesen n rekordunk van. Hány blokkos az adatfájl, a sűrű index és
     a ritka index? 

4.1.2.feladat:
   - Minden blokkba 30 rekord, vagy 200 indexrekord (érték-mutató pár) fér.
     Összesen n rekordunk van. Egyik blokk telítettsége sem lehet több, mint 80%.
     Hány blokkos az adatfájl, a sűrű index és a ritka index?

4.1.3.feladat:
   - Minden blokkba 3 rekord, vagy 10 indexrekord (érték-mutató pár) fér.
     Összesen n rekordunk van. Többszintű indexünk legfelső szintje csak
     1 blokkból áll. Hány blokkos az indexfájl, ha az első szinten sűrű az index,
     és ha az első szinten ritka az index? 
   
Tk.4.2. fejezete: Másodlagos indexek
 
4.2.1.feladat:
   - Az adatfájlba történő beszúrás és törlés esetén a másodlagos indexfájlnak
      változnia kell. Javasoljunk néhány módszert arra, hogy lehet naprakészen
      tartani a másodlagos indexet az adatfájlok változásaival szinkronban.

4.2.4.feladat, lásd előadás fizika.p43 
   - Minden blokkba 3 rekord, vagy 10 indexrekord (kulcs-mutató pár), vagy
     50 mutató fér. Tegyük fel, hogy átlagosan 10-szer szerepel minden indexérték.
     Összesen 3000 rekordunk van. Másodlagos indexet készítünk, úgy, hogy az
     egy indexértékhez tartozó mutatókat kosarak blokkjaiban tároljuk. Mekkora
     az állomány mérete összesen, beleértve az adatokat, indexeket és mutatókat
     tartalmazó blokkokat? 
 
Tk.4.3. fejezete: B+ fák
 
B+ fa felépítésére feladat, lásd előadás fizika.pp49-58 
   - Az alábbi feladatban a tankönyben szereplő algoritmussal építsünk fel egy B-fát!
     Tegyük fel, hogy egy B-fa blokkjaiba 3 kulcs fér el plusz 4 mutató. A kulcsok
     különbözőek. Szúrjuk be a B-fába az alábbi kulcsértékeket a megadott sorrendben:
     39,  15,  50,  70,  79,  83,  72,  43,  45, 54, 75, 64, 68
     Adjuk meg a B-fa minden olyan állapotát, amikor egy csomópont kettéosztására
     volt szükség. Például, az első kettéosztás utáni állapot:
                                50
                   15 | 39         50 | 70

    - [Egy kis segítség:]
      -------------------
      Levél csúcs kettéosztásakor minden kulcsot megőrzünk a régi és az új (szomszédos)
      csúcsban. 1 új kulcs-mutató párt küldünk felfelé a szülő csúcsba, amit ott kell elhelyezni.
       
      Belső csúcs kettéosztásakor (N,M csúcsra) a mutatók első fele az N-be kerül,
      a második az M-be. A kulcsok első fele az N-be kerül a második fele az M-be,
     de középen kimarad egy kulcs, ami az M-en keresztül (első gyermekén keresztül)
     elérhető legkisebb kulcsot tartalmazza. Ez nem kerül sem N-be, sem M-be, hanem
     ez megy fölfelé N és M közös szülőjébe az M-re mutató mutatóval együtt.
 
4.3.1.feladat:
   - Legyen a rekordok száma 1 000 000, és az indexelt oszlopban minden érték
      különböző. Sűrű indexre készítünk B-fát. Egy blokkba 10 rekord vagy
      (99 kulcs és 100 mutató) fér. Legyen a telítettség 70%, azaz legalább
      69 kulcs és 70 mutató szerepel az indexblokkban. Mekkora az adatfájl és
      az index együttes mérete? Mennyi a keresés blokkolvasási költsége?
  
Tk.4.4. fejezete: Tördelőtáblázatok (Hasítóindex szervezés)
 
Lineáris hasító index, lásd előadás  fizika.p9,  fizika.pp11-16 és fizika.pp17-20 
---------------------
Tegyük fel, hogy egy blokkba 2 rekord fér el és a kosarak az alábbi rekordokat tartalmazzák:

0000 0101
1110 
---- ---- 
 00 01

Az előre megadott küszöbszám (rekordok száma/kosarak száma) legyen 2,4.
Jelenleg m = 01 (a legnagyobb használt kosárindex)

Szúrjuk be az alábbi hasító értékkel rendelkező sorokat egymás után, és minden
újabb blokk megnyitás után rajzoljuk újra a kosarakat.

0001, 0110, 1011, 0111, 1100, 1111, 0100


Egy kis segítség:
----------------
Ha n kosarunk van, akkor a K kulcsú rekordot h(K) utolsó i bitje alapján tesszük a
megfelelő kosárba (i=log2n).
Ha nincs benne hely, akkor újabb blokkot láncolunk ehhez a kosárhoz.
Ha nincs ilyen kosár, akkor az első bitben különböző kosárba tesszük.
Ha az előre megadott küszöböt átléptük, akkor új kosarat nyitunk.
Szükség esetén növeljük i-t
 
 Vissza az AB2 gyakorlat oldalára             Vissza a Kezdőlapra