Indexek

• Kiegészítő adatszerkezet
  • Tárolni kell
  • Keresést gyorsít
  • Több mezőre is deffiniálható
• Ha akeresési mező egyik indexmezővel sem egyezik, akkor kupacrendezésre van szükség

Indexrekord szerkezete

• (a,p), ahol
  • a egy érték az indexelt oszlopban
  • p egy blokkmutató
    • Értéke az A=a értékű rekordra mutat
• Az index mindig(!) rendezett értéke szerint

🍊le specific way

Egyszerű index

CREATE INDEX supplier_idx
    ON supplier(supplier_name);

Összetett index

CREATE INDEX supplier_idx
    ON supplier(suplier_name, city)
    COMPUTE STATISTICS;

Elkészíti az optimalizáláshoz szükséges statisztikákat is

Elsődleges index

• Főfájl is rendezett
• Csak egy elsődleges index adható meg
  • (mert csak ennyi mező szerint ehet rendezni a főfájlt)
• Elég a főfájl minden blokkjának legkissebb rekordjához elkészíteni az indexrekordot
• Indexrekordok szám: T(I)=B
  • "Ritka Index"

Indexrekordból jellemzően sokkal több fér el egy blokkba, mint a főfájl rekordjaiból (I'm lookin' at you 6NF 🔫)

bf (I) \(\ll\) bf

avagy:

\(B(I) = \dfrac{B}{bf(I)} \ll \dfrac{T}{bf} = B\)

Keresési idő - Fedő keresés

• Az indexfájlban nincs minden érték, Fedő keresésre van szükség
  • Visszaadja a Legnagyobb olyan indexértéke, aminél a keresett érték kissebb vagy egyenlő
• Az index rendezettsége miatt a keresés bináris
  • \(\log_2\)(B(I))
• Plusz még a kiolvasás művelete
• Összesen \(1+\log_2\)(B(I))\(\ll~\log_2\)(B)
  • rendezett eset

Módosítás

• Rendezett fájlba kell beszúrni
• Ha a blokk első rekordja változik, akkor az indexfájlba is be kell szúrni
  • még egy rendeztett fájl beszúrás
• Megoldás: üres hely a fő,- és indexfájl blokkjaiban
  • rossz esetben ez tár duplázódást okozhat, de így egy-egy visszaírás kell legfeljebb

Ritka index - Példa

Indexfájl

Főfájl

Beszúrás

Akkor az előzőbe szúrjuk be a 74-et, ok?

Nyilván, a 70-es fedőértékhez be is fér, ahhoz nem csinálok táblázatot...

Szúrjuk be a 15-öst

Első elgondolás - Újrarendezés

Módosítsuk az indexfájlt, és toljuk át a 30-at a blokk aljába

Indexfájl

Főfájl

Második elgondolás - Túlcsordulási blokk

Azt hittet, az átrendezéssel megúszod, XD

• Mint eddig, behozunk egy küszöböt, ami után mindenképp átrendezünk

Törlés

• Ha marad hely a blokkban, akkor szuper
• Ha túlcsordulási blokkot használunk, és kiürülne, el is távolíthatjuk
• Ha a fedőérték rekordját törölnénk ki (ami ugye az első a blokkban), akkor az indexet módosítani kell
  • Ha maradt a blokkban rekord, az index új fedőértéket kap
  • Ha nem maradt a blokkban rekord, akkor:
    • A blokkot eltávolítjuk
    • A hozzá tartozó indexet is kivesszük
    • Az index blokkjában karbantartást kell végezni (felcsúsztatni, mutatókat mozgatni)