Másodlagos index

• Főfájl a másodlagos index szempontjából rendezetlen
  • Az indexfájl mindig(!) rendezett
• A főfáj minden rekordjához kell indexrekord
  • Ugye mivel rendezetlen, így a fedőérték nem működik
• Indexrekordok száma: T(I)=T
  • Sűrű index
• Az indexrekordból még mindig sokkal több fér egy blokkba, mint a főfájl blokkjaiba
  • \(B(I) = \dfrac{B}{bf(I)} \ll \dfrac{T}{bf} = B\) továbbra is igaz

Keresési idő

• Az index rendezettsége miatt bináris idő
  • \(log_2\)(B(I))
    • • a talált blokkban lévő rekord beolvasása
• Összesen \(1+\log_2\)(B(I))\(\ll~\log_2\)(B)
  • rendezett eset

Módosítás

• A főfájl kupac elrendezésű szervezésű
• Rendezett fájlba kell szúrni
• Ha az első rekord változik a blokkban, akkor az indexfába is be kell szúrni (rendezett)
• Üres hely esetén ugyanazt kapjuk, mint elsődleges indexnél

Kezelési eltérések az elsődlegestől

• Ha nem rendezett az állomány, mind a keresés és a tárolás költséges lesz
• Az index értéke ismétlődhet (és gyakran fog is)
• A blokkon belül más indexű elemek is lehetnek

Lehetséges megoldások

• Indexrekord szerkezete változik
  • Változó hosszú indexrekordok (pl.: a 10-es indexhez nem egy mutató, hanem mutatók listája tartozik)
• Indexenfájlban indexenként egy rekord van, és az azonos indexű elemek láncban mutatnak egymásra
  • Bejárás hosszadalmas
• Mutatók Vödre (Kosarai, idc)
  • Az indexfájlban egy rekord van indexenként megint
  • Van egy köztes réteg
  • Egy index a kezdő helyére mutat a vödörnek
  • A másik index pozíciójáig minden mutató a jelen indexhez mutat

A vödör megoldás halmazműveleteknél előnyös nagyon

pl.: metszet képzése a két index legkissebb pozíciójának maximuma, és legnagyobb pozíciójának minimuma (blazingly fast)