Kihagyás

Többszintű index

  • Az indexfájl (1. indexszint) is rendezett fájl, így az tovább indexelhető elsődleges indexxel
  • A főfájl lehet rendezett, vagy rendezetlen, AZ INDEXFÁJL MINDIG(!) RENDEZETT
  • t-szintű index, az indexek mélysége

Keresési idő

  • a t-adik szinten I\(^{(t)}\) bináris kereséssel kapjuk meg a fedő indexrekordot
  • Követjük a mutatót minden szinten, amíg a főfájlhoz nem jutunk
  • Ha a legfelső szint egy blokkból áll, akkor t+1 blokkolvasás
  • Minden szint blokkolási faktora megegyezik, mert az indexrekordok egyforma hosszúak

Statok

Főfájl 1. szint 2. szint \(\ldots\) t. szint
blokkok száma \(\green{B}\) \(\purple{\dfrac{B}{bf(I)}}\) \(\dfrac{B}{bf(I)^2}\) \(\ldots\) \(\dfrac{B}{bf(I)^{(t)}}\)
rekordok száma \(T\) \(\green{B}\) \(\purple{\dfrac{B}{bf(I)}}\) \(\ldots\) \(\dfrac{B}{bf(I)^{(t-1)}}\)
blokkolási faktor \(bf\) \(\blue{bf(I)}\) \(\blue{bf(I)}\) \(\ldots\) \(\blue{bf(I)}\)

  • t-ik szinten 1 blokk: \(1=\dfrac{B}{bf(I)^t}\)

  • általában \(log_{bf(I)}~<~log_2(B(I))\) is igaz, így az egyszinttű indexelésnél is gyorsabb

Módszerek

B\(^+\), B\(^*\) fák a menő

A szerkezeten kívül a telítettség biztosító/karbantartó algokat is beleértjük

  • B\(^+\): Minden blokk legalább 50%-ban telített
  • B\(^*\): Minden blokk legalább 66%-ban telített