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.1, 4.2, 4.3, 4.4 fejezetei alapján
A fogalmak: Oracle dokumentációkból - a "Concepts"  itt:
                    Part II. Oracle Database Architecture - 5. Schema Objects
                    és itt Overview of Indexes részben
Segédanyagok: EA: Indexstruktúrák  (1-66.o.)
 

Molina-Ullman 4.1. fejezete: Indexek szekvenciális fájlokon
 
4.1.1.feladat:
   - 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? 

4.1.4.feladat:
   - Minden blokkba 3 rekord, vagy 10 indexrekord (érték-mutató pár) fér.
      Hány adatblokkot kell átlagosan beolvasni az összes adott értékű rekord
      eléréséhez, ha rendezett állományunk van, egy érték 1,2 vagy 3-szor
      szerepelhet 1/3, 1/3, 1/3 valószínűségekkel, és olyan sűrű indexünk van,
      amelyben csak az első előforduláshoz tartozik indexrekord?
    - Feltesszük, hogy tudjuk előre, hogy mennyi előfordulásunk van
      az adott értékből.

4.1.5.feladat:
   - Minden blokkba 3 rekord, vagy 10 indexrekord (érték-mutató pár) fér.
      Hány blokkot kell átlagosan beolvasni az összes adott értékű rekord
      eléréséhez, ha egy érték 1,2 vagy 3-szor szerepelhet 1/3, 1/3, 1/3
      valószínűségekkel, és olyan sűrű indexünk van, amelyben minden
      előforduláshoz tartozik indexrekord?
    - Feltesszük, hogy már kiszámoltuk, hogy melyik indexblokkban van
      az első keresett indexérték, és tudjuk, hogy hány van belőle.
 
 
Molina-Ullman 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:
   - 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? 
 
 
Molina-Ullman 4.3. fejezete: B-fák
 
B-fa.feladat:
   - 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,  75,  45
     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?
 
 
Molina-Ullman 4.4. fejezete: Tördelőtáblázatok
 
HF: 4.4.1 - 4.4.6 feladatok
 

Vissza az AB2 gyakorlat oldalára

Vissza a Kezdőlapra