Fájlszervezési módszerek - Heap + Hash

• kupac
  • heap
• hasító index
  • hash
• [rendezett állomány]
• [elsődleges index]
  • ritka index
• [másodlagos index]
  • sűrű index
• [többszintű index]
  • indexek indexei
• [\(B^+\) és \(B^*\) fa]

ezeket fogjuk vizsgálni

Feltételezzük, hogy most elég az első találattal számolni

Módosítási műveletek

• insert
• update
• delete

Egyszerűsített esetben a chache-ről "megfeledkezünk", ok?

Kupac

• A rekordokat a blokk első üres helyére tesszük
  • érkezési sorrendben

Heap - A=a keresési idő

• Tárméret: B
• B legrosszabb eset
• B/2 átlagos eset

Heap - Beszúrás

• Utolsó blokkba tesszük a rekordot
  • 1 olvasás + 1 írás

Heap - Módosítás

• 1 keresés + 1 írás

Heap - Törlés

• 1 keresés + 1 írás
• Üres hely marad , vagy törlési bit

Hasítóindex-szervezés (Hashelés)

• A rekordokat blokkláncokba (bucket - kosár) soroljuk
• A lánc utolsó blokjának első üres helyére teszünk rekodot
  • érkezési sorrend szerint
• Blokklánccok száma
  • statikus hasításkor
    • előre adott: K
  • dinamikus hasításkor
    • a tárolt adatok alapján változhat
• Besorolás az indexmező értékei alapján történik
• Egy \(h(x)\in\{1,\ldots,K\}\) hasító függvény dönti el a rekord helyét
  • ahol \(x\) az indexmező értéke
  • jellemzően modulo-n alapszik
• Ha jó a hasító fügvény, akkor nagyjából egyforma hosszúak lesznek a blokkláncok
  • tehát a besorolás egyenletes
• Jó hasító függvénby esetén a blokklánc B/K blokkból áll

Hash (Statikus) - A=a keresési idő

• Ha az index és keresési mező eltér, akkor kupac szervezés jön
• Ha az index és keresési mező egyezik, akkor elég csak a h(a) sorszámú kosarakat végignézni
  • B/K kupacnak felel meg
    • Tehát B/K legrosszabb eset
    • A keresés K-val gyorsabb az egyszerű heap-nél
• Tárméret: B, ha minden blokk tele

• Módosítások B kupacon végzett módosítás, oszd be...

Hash with 🪣 detour

Példa szerint a vödör mérete 2, a hash függvény \(h\in\{0,1,2,3\}\)

• Látni, hogy új elem beszúrása blokklánc bővítését jelenti
• a törlésénél c feljebb tolható, e-t pedig kihozhatjuk a blokkból
  • A blokk memóriába töltése a leg költségesebb, ha már memóriában van, az átszervezés nem nagy baj
  • üres blokkot nem érdemes tárolni
  • A jelen példában a hasító függvény láthatóan nem olyan jó, az utolsó 3-as vödörbe nem került adat, de az első vödröt (még ha üres is), el kell tárolni

Hash (dinamikus)

Előre nem rögzítjük a vödrök számát, a vödrök száma beszúráskor/törléskor változhat

Kiterjeszhető

• Minden vödör egy blokkból áll
• Keresési költség: 1
• Legyen \(k > \log (f)\)
  • f a rekordok várható számának felső korlátja
  • k hosszú bináris sorozatból több van, mint ahány rekord
• A h hasító függvény értéke egy k hosszú bináris sorozat
• Minden kosárhoz tartozik egy legfeljebb k hosszú bináris sorozat
  • kódszó
• A kosarakhoz rendelt kód prefix kód
  • maximális kód hossza legyen i

Hash (Dinamikus) - Beszúrás

1. Vegyük a k hosszú h(x) kód i hosszú elejét, és az ennek megfelelő vödröt
2. ha van benne hely, win
3. ha nincs benne, akkor csináljunk egy új vödröt és a következő bit szerint osszuk ketté a teli vödör tartalmát
4. ha ez a bit mindegyikre megegyezik, akkor vegyük ezt a szétosztáshoz

A keresés hossza erősen változó lenne, mert ez az implementáció (még) kiegyensúllyozatlan fát képez

• A bináris fa levelei a kosárblokkok kódszavai
• A hasító függvény értékeiből annyi bitet tárolunk, ahányadik szinten járunk a fában
• A gráfot a memóriában tároljuk

Hash (Dinamikus) "Kiegyensúllyozása"

This is mega brain time, you can't proceed if you don't have your papers close

before we start, let's assume our buckets can hold exactly two values, okay?

First, make an array of buckets and give it a nice label:

Put in three values with their h(x) value 0001, 1100 and 1001 using their first bit only:

So, I want another value with their h(x) bein' 1010, but the 1 labeled field is full, I can't magically put in, right?

Oh, yes, we can with a simple trick:

• Ok, but that means instead of puttin' another bucket in, we just dubled the array
• ...yes, and now we identify a bucket with two bits, that's right, don't forget to rearrange the values to match their criteria

Lineáris hasító index

• A vödrök 1 vagy több blokkból is álhattnak
• Új vödröt akkor hozunk létre,ha egy előre megadott értéket elér a vödrökre jutó átlagos rekordszám
• 0-val kezdődik a sorszámozás, binárisan
• Adott \(n\) vödör esetén a hasitó függvény értékének utolsó \(\log(n)\) bitjét nézzük
  • Van benne hely, letsgoo
  • Nincs hely: új vödör és láncolhatjuk utána
• Ha nics megfelelő sorszámú vödör, akkor az első bitjén különböző párjához megyünk

Szabály

• \(h(x)_i\le m:\) a rekordot tegyük a \(h(x)_i\) vödörbe
  • \(h(x)_i\le m\) ugye azt mondja, hogy a keresett indexen vödör (még) nem létezik
• else: \(h(x)_i - 2^{i-1}\) the place it goes

Példa - 1

• Hasító érték: 4 bit
• \(i=2\)
• 1 block = 2 record
• Küszöb: 3

\(m = 01\) (a legnagyobb sorszámú létező) blokk sorszáma

Szúrjunk be az előző példábal egy 0101-es rekordot

\(m = 01\)

Tehát mivel az átlagos rekordszámunk nem lépte át a küszöbszámot, ezért túlcsorduló vödröt hozunk létre, és láncoljuk a heap-hez hasonlóan

Példa - 2

• Hasító érték: 4 bit
• \(i=2\)
• 1 block = 2 record
• Küszöb: 2

\(m = 01\) (a legnagyobb sorszámú létező) blokk sorszáma

Szúrjunk be az előző példábal egy 0101-es rekordot, ha a küszöbszám 2

\(m = 10\)

Tehát mivel az átlagos rekordszámunk átlépte a küszöbszámot, ezért a tömbünk felrobban, létrehozunk egy új vödröt, és az egészet átrendezzük, hogy az invariánsunk ne sérüljön