Please enable JavaScript.
Coggle requires JavaScript to display documents.
A fizikai adatbázis, Keresés
a tárolásban nincs egyéb szabályosság
ha…
A fizikai adatbázis
Heap szervezés
- def: segéd struktúra nélküli állományszervezés
- legegyszerűbb
- az adatokat legalább annyi blokkban tároljuk, ameynnit a rekordok száma és mérete igényel
- nincs semmilyen kiegészítő struktúra hozzárendelve
Törlés
- megkeressük
- a rekord fejlécében jelezzük, hogy a rekord felszabadult
- tehát ha a rekord nem kötött, akkor a terület felülírható
- ezután a megváltozott blokkot visszaírjuk a diszkre
- időnként szükség lehet a gyakori törlések következtében szétszóródott lemezterületek összegyűjtésére és egyesítésére
- az un szemétgyűjtő programmodul a törölt jelzés alapján tudja, hogy ezt a területet felül lehet írni
- keresés+1
Beszúrás
- ügyelni kell, hogy az egyediségek megmaradjanak
- ha nincs ötlet végignézni mindet
- N blokkműv +1
- először a törlés által felszabadított helyen próbálkozunk
- ha itt nincs akkor az állomány végén
- ha itt sincs hely, akkor az OS rendszer ill a db adminisztráort kell megkérni, hogybővítse az állományt
- ez bonyolult: célszerű egy fizikaliag egybefüggő diszkterülettel bővíteni az adatbázist
Módosítás
- egyszerű ha az egyediséget biztosító mezők értéke nem változik
- keresés, felülírás, visszaírás
- egyéb: gondoskodni hogy megkülönböztetlen rekord ne kerüljön az adatbáziba
Indexelt állományok
- háttértár struktúra: indexFÁJL
- kulcs érték szerint rendezett MINDIG
- log2N
- könyvtári példa: lineárisnál hatékonyabb algoritmus
- alapgondolat: a keresés kulcsát egy ún indexállományban megismételjük, és a kulcshoz egy mutatót rendelünk, amely a tárolt adatrekord helyére mutat
- a kulcsot és a mutatót is rögzített hosszúsággal ábrázoljuk
- az indexállomány blocking factora fi=b/(k+ip), ahol i az indexáll neve
- az indexállományt mindig rendezve tároljuk
- ha a kulcs numm: a tervezés triv
- összetett kulcs esetén( a kulcs több mezőből áll), definiálnunk kell a rendezés módját, azt, hogy a kulcsmezők mely sorrendje alapján történjen a rendezés
- ennek a sorrendnek az alkalmas megválasztása jelentősen bef az index használatának hatékonyságát
- ált nincs akadálya, hogy több indexállományt is létrehozzunk ugyanazon az adatállományon
- nem biztos, hogy ez a mező egy rekordot egyértelműen azonosítanak
- kereséséi kulcs lesz minde, ami szerint egy indexet felépítjük, ill a keresését végezzük
- az indexállomány rekordjai szabadok, így könnyen mozgathatók, jól karbantartható
- az adatállomány rekordjai valamilyen értelemben kötöttekké válnak
- indexrekordok megfeleltetése az indexelt állomány rekordjainak:
- indexrekordot rendelünk minden egyes adatrekordhoz
- indexrekordot rendelünk adatrekordok egy csoportjához, tipikusan az egy blokkban levőkhöz
Ritka indexek
- def: amikor az indexáll található indexrekordokszáma lényegesen kisebb, mint az adatállományban található adatrekordok száma
- szótárak felső sarkába írott index
- az indexrekordok azt határozzák meg, hogy az adatállomány rekordjai melyik blokkban találhatók
- egy blokkon belül az adatrekordok szabad rekordoknak tekinthetők
- az adatállományt rendezetten kell tárolni
- egy blokkban kell, hogy legyen minden olyan adatrekord, amelyeknek a kulcsa egy meghatározott intervallumba esik
- az adatt blokkra mutató indexrekord a blokk címét, valamint a legkisebb értékű kulcsot fogja tartalmazni
- az ri indexállomány blokkjainak száma bri=nri/fri, nri=br, ha az r állományhoz épített ritka indexekről beszélünk
Keresés
- k1 kulcsú rekordra van szükség
- megkeressük azt a rekordot, amelyiknek k2 kulcsa a legnagyobb azok közül, amelyek még kisebbek k1-nél
- keresés lehet bináris
- a k2 kulcsú indexrekord mutatója megcímzi azt a blokkot, amely végig kell keresni a k1 kulcsú adatrekord után
- blokkon belül: lin keresés
- ha blokkon belül rendezetten tároljuk itt islehet bináris
- log2N+1
Beszúrás
- k1 kulcsú rekordot akarjuk tárolni
- megkeressük azt a blokkot, amelyben a rekordnak linnie kellene, ha az adatállományban lenne
- legyen ez a Bi blokk
- ha van elegendő hely a Bi blokkban a k1 kulcsú rekord számára beírjuk a Bi blokkba
- ha nincs akkor helyet kell csinálni
- egy lehetőség, hogy kérünk egy új üres blokkot Bn, majd a Bi rekordjainak számát megfelezzük Bi és Bn között
- meghatározzuk mindkét blokkban a legkisebb kulcsúr rekordot
- a Bi hez tartozó indexrekordban szükség esetén korrigáljuk a kulcsmező értékét
- A Bn hez tartozó lekisebb kulccsal és Bn címével új indexrekordot képzünk, amelyet a megfelelő pozícióban elhelyezünk az indexállományban
- ehhez esetleg az indexállományt is újra kell rendezni
Törlés
- k1 kulcsú rekordot akarjuk törölni
- megkeressük a blokkot, amelyik a rekordot tartalmazza, legyen ez Bi
- ha a k1 kulcs a blokkban nem a legkisebb, akkor a rekordot egyszerűen töröljük
- a keletkező lyukat akár rögtön meg is szüntethetjük a rekordok blokkon belüli mozgatásával
- ha k1 volt a legkisebb kulcs a blokkban, akkor az indexállományt is korrigálni kell Bi új, legkisebb kulcsának megfelelően
- ha a Bi blokkban a k1 kulcső volt az egyetlen rekord, akkor a Bi-re mutató indexrekordot is törölni kell, az üres adatblokkot pedig fel kell szabadítani
Módosítás
- egyszerű, ha nem érinti a kulcsot
- meg kell keresni a szóban forgó rekordot, elvégezni a módosítást, majd az érintett adatblokkot visszaírni a háttértárra
- ha a módosítás kulcsmezőt is érint, akkor egy törlést követő beszúrás sal valósítjukmeg
B*-fák mint többszintes ritka indexek
- az indexelt szervezésnél log2 bi-vel arányos átlagos keresési idő érhető el, ami kesebb, mint a heap, de elmarad a hash mellett
- a háttértár kihasználtásga változó méretű adatállomány esetén is kézben tartható
- a szervezés bonyolítása árán lehetőség van a blokkelérések számát csökkenteni úgy, hogy logk bi vel arányos kereséséi időt érjünk el
- nagy méretű adatállományok esetén, ill, ha k elég nagy, akkor jelentős az elérhető nyereség
- ára: az indexeket egy k ágú fában kell tárolnunk és az adatállomány változása során az indexfát is gondosan karban kell tartanunk
- az ezzel járó többletadminisztráció és az indexállomány valamelyest megnövekedett mérete áll szemben a gyorsabb blokkeléréssel
- az alapgondolat az, hogy az indexállományban való keresést meggyorsíthatjuk, ha az indexállományhoz is (ritka) indexet készítünk hasonló szabályok szerint
- addig folytatható,amíg az utolsó index egyetlen blokkba be nem fér
- az i-1. index tehát egyidejűleg ritka indexe az i. indexnek az adatállománya az i-2. indexnek
- a legalsó szint mutatói az adatállomány egy-egy blokkjára mutatnak, a fölötte levő szintek mutatói pedig az indexállomány egy-egy részfáját azonosítják
- minden levele és csomópontja pontosan blokkméretű és a gyökértől a levelekig vezető út mindig ugyanolyan hosszú, tehát a fa kiegyenylítettv
- szokásos még, hogy az egy csomópontban ábrázolt l mutatóhoz csak l-1 kulcsot tárolnak, mert a legkisebb kulcs jelentése a kijelölt részfában tárolt legkisebb kulcsérték
- az indexblokkok első kulcsérték bejegyzése nem hordozna információt
- az ilyen indexelést nevezik B*-fa indexnek
- blocking gactor, a fa elágazási tényezője : fi=(b+k)/(k+p)
-k a kulcs hossza
- az r állományhoz tartozó B*fa szintjeinek számát HTi vel jelöljük: HTi= logfi br
- gyakorlati megvalósításokban a leveleket gyakran egyik vagy mindkét irányban összeláncolják, amivel az intervallumkereséseket lehet gyorsítani
Keresés
- v1 rekordra van szükségünk
- az indexáll csúcsán álló blokkban megkeressük azt a rekordot, amelyiknek v2 kulcsa a legnagyobb azok közül, amelyek még kisebbek v1-nél
- ennek a rekordnak a mutatója az eggyel alacsonyabb szintű indexben rámutat arra a blokkra amelyben a keresést tovább kell folytatni egy olyan indexrekord után, amelyiknek v3 kulcsa a legnagyobb, azok közül, amelyek még kisebbek v1-nél
- addig folytatjuk, amíg az utolsó mutató már az adatállomány egy blokkját azonosítja, amelyben v1 kulcsú rekordnak lennie kell
Beszúrás
- az indexállomány karbantartásban van, ügyelni kell arra, hogy az eredeti fastruktúrát és annak kiegyenlítettségét fenntartsuk
- bizonyos esetekben az indexhierarchia minden szintjén igényelheti néhány blokk megváltoztatását
Törlés
- megkeressük és töröljük
- az adatblokkokat lehetőség szerint összevonjuk
- összevonáskor, vagy ha egy adatblokk utolsó rekordját is töröltük, a megszűnt blokkhoz tartozó kulcsot ki kell venni az indexállomány érintett részfájából
- ehhez akár minden szinten szükséges lehet néhány blokk módosítása
Módosítás
- azonos a ritkával, a bonyibb indexstruktúrából adódó köv értelemszerűen alkalmazva
Sűrű indexek
- def: amikor az indexáll található indexrekordokszáma megegyezik az adatállományban található adatrekordok számával
- a ritka index szervezésnél kihasználtuk, hogy egy rekord eléréséhez mindig egy teljes blokkot kell a memóriába beolvasnunk
- a blokkon belüli keresés már igen gyors, így elegendő az indexállományban a blokkcímet tárolni a bennük található legkisebb kulcsértékkel együtt
- az volt az ára, hogy az adatállományt is rendezetten kell tárolni
- nincs mód arra, hogy 1-1 új rekordot tetszőleges szabad helyre szúrjunk be
- mindkét problémára megoldást kínál, ha minden egyes adatrekordhoz tartozik indexrekord
- az indexrekord mutatója általában továbbra is csak a rekordot tartalmazó blokkot azonosítja
- az utóbbival a blokkelérések számát természetesen nem lehet csökkenteni
- önmagában nem állományszervezési módszer
- a sűrű indexre mindig ráépül egy másik elérési mechanizmus: tirka v hash
- az si sűrű indexállomány blokkjainak a száma bsi=nsi/fsi
- hátrányok
- plusz helyigény
- eggyel több indirekció kell egy rekord kiolvasásához
- plusz adminisztrációval jár a sűrű index karbantartása
- előnyök
- nem kell rendezetten tárolni
- meggyorsíthatja a rekordkeresést
- támogatja a több kulcs szerinti keresését
- az adatállomány rekordjai szabadokká tehetők, ha minden további rekordhivatkozás a sűrű indexen keresztül történik
Keresés
- megkeressük a kulcsot, a hozzá tartozó mutatóval elérhetjük a tárolt rekordot
Törlés
- megkeressük
- a hozzá tartozó törölt bitet szabadra állítjuk
- a kulcsot kivesszük az indexállományból és az indexállományt időnként tömörítjük
Beszúrás
- keresünk egy üres helyet a tárolandó rekordnak
- ha nem találunk, akkor az állomány végére vesszük fel
- beállítjuk a foglaltsági jelzést és beírjuk az adatot
- a kulcsot és a tárolás helyére hivatkozó mutatót a kulcs szerint berendezzük az indexállományba
Módosítás
- megkeressük a módosítandó rekordot tartalmazó adatblokkot
- a módosított tartalommal visszaírjuk a háttértárra
- ha a módosítás kulcsmezőt is érintett, akkor az indexállományt újrarendezzük
Tároló eszközök
- soros hozzáférésű
- közvetlen/direkt hozzáférésű
- mágnesdob
- mágneslemez: HDD/merevlemez
- SSD
- HDD+SSD} DRDB: disk resident database
- ,,memóriában": in memory database: IMDB
- tárolóeszköz=háttértár
- adatok tárolásához az fontos, hogy a háttértáron ezt, hogy valósítjuk meg
Bevezetés
- rendszer legalsó szintje: fizikai réteg
- adatrekordok célszerű tárolás a háttrétáron -> keresett rekord/ rekordok halmazának gyors elérése
- mágneslemezes háttértáron való hatékony tárolás
- HDD esete
- rekordszerű struktúrákat kezelünk
- Strukturálás: file(állomány): blokk: rekord: mező
- blokk: ezekben az egységekben mozgatjuk az adatokat az operatív tár és a háttértár között
- négy műveletet tervezünk támogatni: kersés, beszúrás, törlés, módosítás
- a számítógépen futó OS az adatbázis adatait is állományokba(fájlokban) tárolja
- állományok: azonos méretű blokkokból épülnek fel
- blokkméret: 0,5...32kb
- OS tartja nyilvánmely állományhoz mely blokk tartozik
- minden blokknak abszolút címe van
- egyetlen fejmozgatással és be/kimeneti művelettel a blokk elérhető, az adatai az operatív tárba(memory) juttathatók
- a szükséges adatokat minden esetben a mágneslemezről kell beolvasni
- nincs lehetőség egyidőben több blokkot egy időben a számítógép memóriájában tárolni
Általános
- a lemezműveletek időigénye több nagyságrenddel nagyobb ahhoz képest, mintha az adatokat a memóriában kellene megkeresni ugyanilyen szervezés mellett
- időigényt alapvetően az fogja meghatározni, hogy egy blokk tartalmáért hányszor kell a háttértárhoz fordulni
- úgy kell az adatainkat a mégneslemezen tárolni, hogy a kért adat a lehető legkevesebb blokkművelettel legyen elérhető
- blokk művelet: írás/olvasás
- mindig tartozik hozzá egy header/ fejrész
- a blokkok tartalmazzák az adatrekordokat
- a rekordok blokkhatárt nem lépnek át, így ált nincsenek teljesen kihasználva
- szabad rekord: nem mutat rá pointer (segítik a háttértár hatékonyabb kihasználását)
- köttött rekord: mutat rá és a helyéről nem lehet mozgatni anélkül, hogy a rá mutató pointert meg ne változtatnánk
- rekord címzése: legegyszerűbb egy abszolút fizikai cím, gyakoribb megadni annak a blokknak a fizikai címét, amely a rekordott tartalmazza + ofszet, ami a blokkon belülu kezdőcímét adja meg
- logikailag is megcímezhető, ha pl megadjuk a kulcsának az értékét
- a rekordok lehetnek változó vagy rögzített hosszúságúak/formátúmúak ( változó hosszúságú mezőt vagy ismétlődő csoportot tartalmaznak (ismétlődő mezőcsoport))(hálósnál pl)
- fix részt leválasztjuk, úgy kezeljük, mint eddig
- a változó részt egy mutatón keresztül érjük el, máshol más módszerekkel kezeljük
- tárolni kell a különböző típusú rekordblokkal kapcsolatban azt az információt is, hogy milyen a felépítésük, az egyes mezőket hogyan kell értelmezni
- meg kell különböztetni élő rekordokat a még soha nem használt üres helyektől
- a blokk a headerben egy számláló jelzi a blokkon belüli élő rekordok mindenkori számát
- b hasznos blokkméret (fejrészt nem tart) polc hossza
- sr: r állomány rekordmérete kosár hossza
- nr: rekordok száma kosarak száma
- fr: r állományban egy blokkban elhelyezhető rekordok száma (blocking factor) b/sr kosarak száma a polcon
- br: állomány által elfoglalt blokkok száma nr/fr
Hash-állományok
- Hash-címzés/csonkolásos címzés onnan kapta a nevét, hogy elvileg a keresés kulcsának bitmintájából csonkolással is nyerhető egy cím, amely alapján a keresett rekord megtalálható.
- legegysezerűbb változatában minden rekordhoz egy egyértelmű címet rendelünk az ún. hash-függvény segítségével
- a hashF egy rekord K(kersési) kulcsát egyértelműen képezi le egy intervallumra
- az intervallum => szóba jöhető rekordok max száma
- a kulcs ismeretével egy egyszerű számítással megkaphatjuk a tároláso helyét
- egyetlen blokkművelettel elérhetjük a rekordot
- gyakorlatban ilyen formában alig használható, mert rosszul használja ki a háttértárat
- egy gyakorlati megoldás az ún. vödrös hashelés
vödrös hashelés
- Osszuk fel az adatállományt B(vödör, bucket) részre úgy, hogy minden rész legalább egy blokkból álljon
- hozzunk létre egy B számú mutatóból álló ún vödörkatalógust(hash tábla), amelyben minden mutató az állomány 1-1 blokkcsoportjának(vödörnek) a címét tartalmazza
- definiáljunk egy h hash függvényt , amely a kulcsok szóbajöhető értékkészletét leképzi a [0,B-1] tartományra lehetőleg egyenletesen
- lényege, hogy azt a rekordot, amyleiknek a kulcsa K értékű, mindig a h(K) adaik vödörbe kell tárolni
- a tárolás hatékonysága a hashfg megalkotásától függ, másrészt, hogy az adatállomány nagysága jól becsülhető, ill közel állandó-e
- gyakran használt hashF_ h(K)= (c*K)mod B, ahol c egy alkalmasan megválasztott konstans
- az egyszerűség kedvéért felt, hogy a hashtábla az operatív tárban van
Kersés
- meghatározzuk a rekord kulcsát:K
- kiszámítjuk h(K)-t
- kiolvassuk a vödör katalógus h(K)-adik bejegyzését, ezen a címen kezdődő vödörben kell a rekordnak lennie, ha egyáltalán benne van
- végigolvassuk a vödör első blokkjának mindegyik nem törölt és nem üres rekordhelyét
- ha valamelyik kiolvasott rekordnak K a kulcsa, akkor megtaláltuk a rekordot
- ha nem, akkor a vödör ún túlcsordulási blokkjait vizsgáljuk végig hasonlóan
- Ha a vödör egyik blokkjában sem találtuk, akkor nincs benne az adatbázisban
- vödrön belül: lin keresés
- keresés az állomány1/(2B)-ed része, amennyiben a vödrök egyforma hosszúak
Törlés
- megekeressuk
- a törölt bitet beibillentjük
- a módosított blokkot visszírjuk a diszkre
Beszúrás
- K kulcsú rekordot
- ügyelni kell az egyediségre
- kiszámítjuk h(K) értékét és kiolvassuk a vödör katalógus h(K) adik bejegyzését
- először végigkeressük a az így meghatározott vödröt a K kulcsú rekord után
- ha megtaláljuk: hibaüzenet
- ha nem akkor az első szabad vagy törölt helyre beírjuk a rekordot, miközben mgefelelően beállítjuk a törölt bitet
- ha minden hely foglalt, akkor a vödörhöz egy új blokkot kell hozzáfűzni. és itt elhelyezni
Módosítás
- ha a módosítás nem érnit kulcsmezőt: megkeressük a rekordot tart blokkot, a művelet után pedig visszaírjuk, ha nem találtunk rekordot: hibaüzenet
- ha érint: törlés, beszúrás egymás utáni végrehajtása, mivel feltehetőleg másik vödörbe fog kerülni
Egyéb
- gyorsak lehetnek a hash alapú műveletek, ha a vödrök hossza kicsi
- 1 vödör/blokk: rossz a határ kihasználtság
- kevesebb vödör és hosszabbak: a blokkelérések száma nő
- a diszkterület az egyik legolcsóbb erőforrás: nem ezzel érdemes takarékoskodni, ha keresését gyorsítani akarjuk
- nem támogatja az intervallum kereséséeket : indexelt áll mo
Invertálás
- korlátozott használhatósága van annak az adatbázisnak, amelyben egy személy adatait pl csak akkor lehet megkapni, ha pontosan tudjuk a személyi számát
- van arra igény, hogy csak név alapján lehessen keresni
- vagy listát csináljuk azokból, akik egy városban laknak
- a név és a lkóhely sem kulcsmezők
- ált több mező szerint is támogatni kell az adatrekordok megtalálását
- gyakran ilyenkor is kulcsról beszélnek azzal a mezővel kapcsolatban, amely szerint a keresésé történik
- az indexszervezés módosításával-kibővítésével támogatjuk a több kulcs szerinti keresést
- kézenfekfő mo: több indexállományt is létrehozunk
- invertált állomány
- az invertált állomány mutatói:
- lehetnek fizikai mutatók, amelyek mutathatnak pl:
- közvetlenül az adatálllomány megfelelő blokkjára
- az adatállomány elsődleges kulcsa szerinti sűrű indexállomány megfelelő rekordjára
- lehetnek logikai mutatók, amelyek az adatállomány valamely kulcsának értékét tartalmazzák
- az a) esteben az adatállomány rekordjai kötöttek és ráadásul csak egyetlen invertált állomány esetén használható
- b) esetben eggyel több indirekción keresztül érjük el a keresett rekordot, de az adatrekordok változtatásakor csak az érintett mezőt tartalmazó invertált állományokat és az indexállományt kell módosítani
- a . mo választjuk, akkor az adatállomány rekodrjai szabadok lehetnek, viszont nem ismerjük még a keresett rekord címét
- ennek megtalálását pl hasheléssel/indexeléses módszerrel támogathatjuk
Változó hosszúságú rekordok kezelése
- ok:
- egy mező hossza változó
- ismétlődő mező van a rekodban
- a változókat a mezőlista végén helyezzük el
- 2 eset kezelése:
- lefoglalt hely módszer: ilyenkor a maximális számú ismétlődéshez elegendő nagyságú helyet foglalunk a rekordnak
- mutatós módszer
- kombinált módszer: valamennyi helyet lefoglalunk, ha még több az ismétlődés, akkor a mutatós módszert alkalmazzuk
Részleges információ alapján történő keresés
- gyakori, amikor egy rekord több mezőjének értékét ismerjük és keressük azokat a rekordokat, amelyek ugyanezeket az értékeket tartalmazzák ugyanezen mezőikben
- feltételezzük, hogy a mezők egyikse sem kulcs
- egyik lehetőség: több mezőre építünk indexeket
- minden specifikált mező-érték alapján előállítjuk a találati rekord-halmazt, majd ezeknek a metszetét képezzük
- ez nem igazán praktikus
- másik lehetőség: particionált hash- függvények alkalmazása
Keresés
- a tárolásban nincs egyéb szabályosság
- ha a keresési kulcs alapján egyetlen rekordot tudunk azonosítani
- akkor egymás után beolvassuk a háttértárról a memóriába a kérdéses rekordokat tartalmazó állomány blokkjait, majd végigolvassuk a blokkokat mindaddig, amíg rá nem találunk a keresettre
- hol kezdődik az első rekord: fej+ofszet: honnan tudjuk mekkora a fej: metaadat tár, minden ilyen cuccli
- metaadat táróből kiolvassuk, hogy mi a rekord struktúrája
- lucky:1 unlucky: n
- egyedi kulcsérték által meghatározott egyetlen rekord megtalálása átlagos: (blokkok száma+1)/2 számú blokkművelet elvégzését igényli
- keresés lineárisan arányos a blokkok számával
-
-
-