2. rész

blokk (header, rec1, rec2, ..., maradék hely)
rekord (header, mező1, mező2, ..., mező M)
- lehet kötött (mutató mutat rá) vagy szabad
- rekordok blokkhatárt nem léphetnek át
művelet időigénye = hányszor kell a háttértárhoz fordulni egy blokk tartalmáért
jelölések:
- hasznos blokkméret - \(b\)
- r állomány rekordmérete - \(s_r\)
- r állomány rekordjainak száma - \(n_r\)
blocking faktor (\(f_r\)): hány rekord fér egy blokkba
- \(f_r = \left \lfloor{\frac{b}{s_r}} \right \rfloor\)
\(b_r\): r állomány által foglalt blokkok száma
- \(b_r = \left \lceil{\frac{n_r}{f_r}} \right \rceil\)
lineáris keresés: \(\frac{b_r + 1}{2}\)

vödrös hashelés: adatállomány B vödörre osztása (minden rész minimum egy blokk)
- vödörkatalógus: mutatókat tárol a vödrökre
- hash függvény: leképzi a kulcsok értékkészletét a \([0, B-1]\) tartományra (pl: \(h(k) = (c * K) \mod B\) )
keresés: lineáris keresés a vödörben
- (általánosan csak az állomány (½B)-ed részét kell átnézni ha egyforma hosszúak a vödrök)
törlés, beszúrás: lineáris keresés a vödörben + 1
módosítás:
- ha nem módosul a kulcs: keresés + 1
- ha módosul a kulcs: törlés + beszúrás (mivel máshova kerül)
hátrány: intervallumkeresést nem támogat

két rész:
- index állomány: kulcs + pointer párok (kulcs szerint mindig rendezve)
- adatállomány: maga az adat
index állomány blocking factor-ja: \(f_i = \left \lfloor{\frac{b}{k + p}} \right \rfloor\)
sűrű index: index minden adatrekordhoz
ritka index: index az adatrekordok halmazához
támogatja az intervallumkeresést

az indexek adatblokkokat címeznek
blokkok száma: \(b_{ri} = \left \lceil{\frac{n_{ri}}{f_{ri}}} \right \rceil\), ahol ugye \(n_{ri} = b_{ri}\)
keresés: \(\left \lceil{\log_2 (M+1)} \right \rceil + 1\)
beszúrás:
- ha befér adott vödörbe: belerakjuk
- ha nem férbe: új vödör kérés, adott vödör elemeinek elosztása, legkisebb kulcsok meghatározása
törlés:
- ha nem a legkisebb az adott vödörbe: töröljük
- ha a legkisebb az adott vödörben: törlés + index állomány korrigálása
módosítás:
- ha nem módosul a kulcs: keresés + 1
- ha módosul a kulcs: törlés + beszúrás (mivel máshova kerül)

többszintes ritka indexek
előny: háttértár kihasználtsága változó méretű adatállomány esetén is kézben tartható
index állomány blocking factorja: \(f_i = \left \lfloor{\frac{b + k}{k + p}} \right \rfloor\)
fa magassága (Height of Tree): \(HT_i = \left \lceil{\log_{f_i} b_r} \right \rceil\)
keresés: \(HT_i + 1\)
beszúrás, módosítás, törlés: mint sima ritka intexnél (kiegyenlítettségre figyelni kell)

az indexek adatrekordokat címeznek
önmagában nem állományszervezés
\(b_{si} = \left \lceil{\frac{n_{si}}{f_{si}}} \right \rceil\), ahol ugye \(n_{si} = b_{si}\)
előny:
- adatállományt nem kell rendezetten tárolni (helymegtakarítás)
- több kulcsos keresést tudunk biztosítani
rekordok szabadokká tehetők (rájuk csak sűrű index hivatkozik)
hátrány:
- plusz helyigény
- plusz egy blokkművelet
- plusz adminisztráció
keresés: kulcs megkeresése, onnan mutatón keresztül elérjük az adatot
törlés: keresés + 1
beszúr: üres hely keresés, ha nincs akkor a végére
módosítás: módosítás háttértárra írása, ha kulcs akkor indexállomány újrarendezése

invertált állomány: az az indexállomány, amely nem kulcsmezőre tartalmaz indexeket (pl más keresést is támogatni akarunk)
invertált állomány mutatói:
- fizikai címre, a konkrét blokkra mutatnak (kötötté teszi az rekordokat)
- fizikai címre, egy sűrű indexállományra mutatnak (plusz egy iteráció a keresés, de szabadok maradnak a rekordok)
- logikai mutatók, amik az adatállomány valamely kulcsának értékét tartalmazzák (ekkor ezt még fel kell oldani)

oka lehet:
- mező hossza változó -> fix mutató van csak a rekordban, tényleges tartalom külön állományban
- ismétlődő mezőcsoport van a rekordban -> mutatós módszer, vagy fix hely a max ismétlődésnek