6 15:51 page 27 #23

i

i “adatszerkezetek” — 2007/7/6 — 15:51 — page 27 — #23

i

i

9. FEJEZET

Állományok

9.1. Alapfogalmak 9.1. definíció. Másodlagos tárolónak vagy külső tárolónak, háttértárnak, periféria tárolónak nevezzük azokat a tárolóeszközöket, amelyeken adatokat és programokat tárolunk, s amelyek adatcsatornán keresztül kapcsolódnak a központi feldolgozóegységhez. A másodlagos tárolóeszközön tárolt adatok közvetlenül nem használhatók fel, csak a belső tárba való bejuttatásuk után. Másodlagos tárolóeszközök használatára azért van szükség, mert a belső tárak kapacitása viszonylag kicsi, és csak időleges adat-, illetve programtárolásra szolgál. A modellezés során először az állomány absztrakt szerkezetét, a logikai állományt alakítjuk ki, majd ezt képezzük le a háttértárra, s így kapjuk a fizikai állományt.

9.1.1. Logikai állományokkal kapcsolatos fogalmak 9.2. definíció. Adattételnek vagy adatelemnek nevezzük azt a legkisebb, önálló névvel rendelkező adatot, amelynek a felhasználó szempontjából még önálló jelentése van. A logikai állomány legkisebb önállóan értelmezhető, atomi része. Jellemzői: név, típus és hossz. Van fix és változó hosszúságú adattétel. 9.3. példa. Fix hosszúságú adattétel a születési évszám (négy decimális számjegy), változó hosszúságú a születési hely. 9.4. definíció. Adatcsoportnak nevezzük az adattételeknek egy olyan együttesét, amelyben a tételek logikailag kapcsolódnak egymáshoz, és önálló névvel vannak ellátva. Típusai: • vektor típusú: azonos darabszámú adatelemből áll; • ismétlődő adatcsoport : olyan adatcsoport, amely halmazértékű (nem atomi), azaz tetszőleges számú (akár 0 darab) adatelemből áll;

i

i i

i

i


i

28

9.

i

Állományok

• összetett adatcsoport : a vektor típusú és az ismétlődő adatcsoport kombinációja, ahol a vektor típusú adatcsoport legalább egy eleme ismétlődő adatcsoportot alkot. 9.5. megjegyzés. Az adatcsoport megkülönböztetésnek csak akkor van értelme, ha az ily módon összekapcsolódó adattételek együttesen valamilyen logikai tartalom hordozói. 9.6. definíció. Logikai rekordnak nevezzük adattételek és adatcsoportok rögzített sorrendű, logikailag összetartozó együttesét. Nincs önálló neve. 9.7. definíció. Logikai rekordazonosítónak vagy elsődleges kulcsnak nevezzük azt az adatelemet vagy adatcsoportot, amely minden egyes logikai rekordban különböző értéket vesz fel. Célja, hogy segítségével megkülönböztessük egymástól a logikai rekordokat. Lehet egyszerű, ha egyetlen adatelemből áll, és összetett, ha nem. 9.8. definíció. Másodlagos kulcsnak nevezünk minden olyan adatelemet vagy adatcsoportot, amelynek értékei nem feltétlenül egyediek az egyes rekordokban, de felmerülhet az igény a rekordok ezek alapján történő feldolgozására is. A logikai rekord felépítése (rekordformátuma) a következők valamelyike lehet: • fix : a logikai rekordok azonos szerkezetűek és hosszúságúak (ez kizárja a változó hosszúságú adatelemeket, valamint az ismétlődő és az összetett adatcsoportokat); • változó: a logikai rekordok felépítése azonos, hosszuk azonban eltérhet (ha a logikai rekord változó hosszúságú adatelemet vagy ismétlődő csoportot tartalmaz, csak ez jöhet szóba); • határozatlan: a logikai rekordok szerkezete is különbözhet (bizonyos adatelemek hiányozhatnak egyes rekordokból). 9.9. definíció. Logikai fájlnak vagy logikai (adat)állománynak nevezzük valamilyen feldolgozási cél, tartalom vagy forma szerint összetartozó logikai rekordok névvel ellátott együttesét. A logikai állományok szerkezete lehet: • struktúra nélküli: a logikai rekordok sorrendje tetszőleges; • asszociatív : a logikai rekordok valamilyen egyértelmű, diszjunkt csoportosítását el lehet végezni (logikai rekordazonosító alapján például egyelemű csoportok alakíthatók ki); • szekvenciális: a logikai rekordok között valamilyen szempont szerint sorrendiséget (rendezettséget) értelmezünk, azaz minden rekord esetén meg tudjuk mondani a megelőző és a rákövetkező rekordot; • hierarchikus: a logikai rekordok hierarchiát (fát) alkotnak, azaz minden rekordnak legfeljebb egy megelőzője és tetszőleges számú rákövetkezője lehet.

i

i i

i

i


i

9.1.

Alapfogalmak

i

29

9.1.2. Fizikai állományokkal kapcsolatos fogalmak Adatainkat tárolnunk kell. A tárolás egy leképezés eredményeként valósítható meg. Például a belső tár, a mágnesszalag vagy a mágneslemez eltérő hardver sajátosságokkal, eltérő címzési lehetőségekkel és ennek megfelelően eltérő tárolószerkezettel rendelkezik. Ezért különböző módon lehet adatokat tárolni rajtuk. Következésképpen a különböző tárolóeszközök igénybevételekor más-más leképezést kell alkalmaznunk. A leképezés kapcsolatot teremt a logikai adatszerkezet és a tárolószerkezet elemei között. Eredményeként létrejön a tárolóeszközön a fizikai adatszerkezet. Alapvetően fontos, hogy a leképezés során a logikai adatstruktúra ne torzuljon el. Ez a feltétel nem mindig teljesíthető, azaz egyes logikai adatszerkezetek nem képezhetők le torzulás nélkül bizonyos tárolóeszközökre. A továbbiakban a logikai adatszerkezeteknek csak a külső tárolóeszközökre való leképezésével foglalkozunk. 9.10. definíció. A fizikai állomány legkisebb alkotórésze a mező, amely önálló névvel van ellátva. Ez a logikai adattételnek (adatelemnek) tartalmilag megfelelő fizikai tárolási egység. A fizikai mezőnek azonban vannak csak rá jellemző fizikai tulajdonságai is (például az ábrázolási formája). Hossza bájtokban értendő. 9.11. definíció. A mezőcsoport a logikai adatcsoport fizikai megfelelője. 9.12. definíció. Fizikai rekordnak vagy blokknak nevezzük a tárolt adatoknak egy olyan egységét, amelyet a számítógép egyetlen író-olvasó utasítással képes beírni egy tárolóterületre vagy kiolvasni egy tárolóterületről. 9.13. megjegyzés. A számítógépes író-olvasó utasítások szempontjából ez a legkisebb egység. Mi a viszony a logikai és fizikai rekord között? Bizonyos esetekben a két fogalom egybeeshet, amikor is egy fizikai rekord egy logikai rekordot tartalmaz. Előfordulhat, hogy nem teljes az egybeesés amiatt, hogy a fizikai rekordhoz még további technikai adatok is tartoznak. Gyakoribb eset, hogy egy fizikai rekord több logikai rekordot is magában foglal, ezt nevezzük blokkolásnak. Ritkábban, de megeshet, hogy egy logikai rekord csak több fizikai rekordban helyezhető el, részekre darabolva. Ezt nevezzük szegmentálásnak. Olyankor kerülhet erre sor, ha a blokk maximális mérete valamilyen hardveres vagy szoftveres megkötés miatt rögzített, és ezt meghaladó rekordmérettel van dolgunk. A logikai rekordformátumok megvalósítása fizikai szinten a következőképpen történik: • Fix rekordformátum: Az összes rekord hossza azonos, rögzített, állományra jellemző információ. – nincs sem blokkolás, sem szegmentálás: Nincs szükség további információra.

i

i i

i

i


i

30

9.

i

Állományok

– blokkolás: Szükséges egy plusz információ arról, hogy hány rekord kerül egy blokkba (blokkolási tényező), ami ugyancsak az állományra jellemző tulajdonság. – szegmentálás: Szükséges egy plusz információ arról, hogy hány blokkra tördeljük az egyes logikai rekordokat, ami szintén az állományra jellemző tulajdonság. • Változó rekordformátum: A rekordok mérete különbözhet, szerkezetük megegyezik. – nincs sem blokkolás, sem szegmentálás: Egy lehetséges megoldás a fix blokkméret alkalmazása, amelyet akkorának kell választani, hogy a leghosszabb rekord is beleférjen. Ebben az esetben a blokk ki nem használt része lehet „szemét”, vagy feltölthetjük egy speciális értékkel. Egy másik megoldás, ha a blokkméretet nem rögzítjük. Ebben az esetben a blokk mérete megegyezik a logikai rekord méretével, s ezt az információt minden blokk elején tárolni kell. Mindkét megoldás esetén minden blokkban vagy (1) tárolni kell egy plusz információt: változó hosszúságú adatelem esetén a hosszt, ismétlődő adatcsoport esetén az adatelemek számát, vagy (2) a rekordok elején egy fejlécet alakítunk ki, amelyben az egyes adatelemekre és adatcsoportokra jellemző összes segédinformációt (hossz, darabszám, kezdőcím) tároljuk. – blokkolás: Minden logikai rekord előtt tárolni kell a rekord méretét. Amennyiben ezek a rekordok méreteik szerint szabályosan követik egymást, akkor használhatunk rögzített blokkméretet és -szerkezetet. Ha a rekordok mérete véletlenszerű, akkor is dolgozhatunk azonos blokkmérettel, de ebben az esetben a blokkok szerkezete eltérő lesz. Az érkező rekordokat sorban pakoljuk a blokkba, és ha már nem fér több, akkor a következő blokkban folytatjuk, az előző blokk ki nem használt része pedig „szemét” marad, vagy feltöltjük egy speciális értékkel. Az is egy lehetőség, hogy nem fix blokkmérettel dolgozunk. Ekkor rögzítünk egy maximális blokkméretet, és ha az érkező rekord nem fér el az aktuális blokkban, akkor új blokkot kezdünk. Ilyenkor nincs feleslegesen lefoglalt terület, viszont tárolni kell a blokkok elején azok hosszát. – szegmentálás: A blokkoláshoz hasonlóan sok plusz információ tárolásával kell dolgozni. • Határozatlan rekordformátum:

i

i i

i

i


i

9.2.

Állománykezelési műveletek

i

31

Minden egyes rekordban meg kell adni, hogy mely adatelemeket és adatcsoportokat tároljuk, vagy azt, hogy melyeket nem. Általában nincs sem blokkolás, sem szegmentálás, mert körülményes azok megvalósítása. Amennyiben azt adjuk meg, hogy mely adatelemeket (adatcsoportokat) tároljuk az adott rekordban, akkor meg kell adnunk az adatelem (adatcsoport) nevét, típusát, hosszát és értékét is. 9.14. definíció. Fizikai állománynak nevezzük egy (vagy több) logikai állomány logikai rekordjait tartalmazó fizikai rekordok (blokkok) önálló névvel ellátott sorozatát. A leggyakoribb, hogy egy fizikai állomány egy logikai állományt tartalmaz. Néha egy logikai állományt szét kell bontanunk két (vagy több) fizikai állományra. Előfordulhat az is, hogy több logikai állományt vonunk össze egy fizikai állományba.

9.2. Állománykezelési műveletek A műveletek alapja a logikai rekord.

9.2.1. Létrehozása Az állományszerkezet (szervezési mód) kiválasztását jelenti.

9.2.2. Bővítés Az állomány rekordjainak darabszáma nő.

9.2.3. Törlés Törléskor egy adott azonosítójú rekordot meg kell szüntetni, törölni kell az állományból. A törlés kétféle lehet: • logikai vagy • fizikai. Logikai törlésnek azt nevezzük, amikor egy rekord fizikailag a helyén marad, de valamilyen módon inaktívvá tesszük (törlőbájt használatával vagy valamelyik mező értékének cseréjével), tehát nem kereshető vissza, nem dolgozható fel. Fizikai törlésnek azt nevezzük, ha az adott rekordot fizikailag töröljük az állományból. Az adott állományszerkezet sajátossága, hogy az így felszabaduló tárolóterület újra felhasználható-e más rekord tárolására. A törlés művelete két fázisból tevődik össze: • a kérdéses rekord visszakereséséből és • a törlés logikai vagy fizikai végrehajtásából.

i

i i

i

i


i

32

9.

i

Állományok

9.2.4. Csere A rekord valamelyik mezője értékének felülírását jelenti. Ahol van elsődleges kulcs, ott az nem cserélhető.

9.2.5. Elérés Egy állomány rekordjainak elérése lehet: • soros, ahol az elérés sorrendje megegyezik a rekordok állományba illesztésének fizikai sorrendjével, • szekvenciális, ahol az elérés sorrendje követi az elsődleges kulcsértékek logikai sorrendjét, • közvetlen, ahol egy adott elsődleges vagy másodlagos kulcsértékkel rendelkező rekord elérése közvetlenül, a környezetében lévő rekordoktól függetlenül történik.

9.2.6. Keresés Soros elérés esetén teljes, szekvenciális elérés esetén lineáris. Közvetlen elérés esetén nem beszélünk keresésről.

9.2.7. Rendezés Bizonyos állományszerkezeteknél lehetséges.

9.2.8. Feldolgozás Egy állomány feldolgozása a benne lévő rekordok feldolgozását jelenti. A feldolgozás az elérésen (keresésen) alapul.

9.2.9. Újraszervezés Egy állomány újraszervezésén értjük azt az eljárást, amelynek során az állományt változatlan szervezési móddal újra létrehozzuk egy másik tárolóeszközön vagy ugyanazon tárolóeszköz egy másik területén. Mindeközben természetesen megváltozhat az állomány fizikai szerkezete és tartalma.

9.3. Állományszerkezetek (szervezési módok) A továbbiakban az állományszerkezeteket az alábbi csoportosításban tárgyaljuk: • egyszerű állományszerkezetek, • összetett állományszerkezetek.

i

i i

i

i


i

9.3.

i

33

Állományszerkezetek (szervezési módok)

9.15. definíció. Egyszerűnek nevezünk egy állományszerkezetet, ha a fizikai állomány csak a logikai állomány adatelemeit tartalmazza. 9.16. megjegyzés. Ez azt jelenti, hogy a fizikai állomány magából az állomány adataiból kialakítható, nem szükséges hozzá technikai szerkezethordozó (strukturáló) adatokat is tárolni, illetve meglétük nem meghatározó a szerkezet szempontjából. 9.17. definíció. Összetett állományszerkezet esetén a fizikai állomány a logikai adatelemeken kívül szerkezethordozó adatokat is tartalmaz. Egy egyszerű állomány fizikai szerkezetét azok a szabályok határozzák meg, amelyek szerint a logikai rekordok elhelyezkednek a fizikai állományban. A szabályok alapvetően két dologra vonatkoznak: • a logikai adatszerkezet elemei közötti kapcsolatokra, • a logikai rekordazonosító (a logikai rekord egyedi azonosítója) és a logikai rekord által elfoglalt fizikai tárolóterület címe közötti kapcsolatra. Ezek alapján az egyszerű állományszerkezeteknek négy alapvető változata különböztethető meg: • szeriális, • szekvenciális, • direkt, • random. a logikai rekordazonosítók között

a rekordazonosítók és tárolási címeik között

nincs

nincs

szekvenciális

van

nincs

direkt

van

van

nincs

van

kapcsolat állományszerkezet szeriális

random

9.1. ábra. Az egyszerű állományszerkezetek összefoglaló táblázata

i

i i

i

i


i

34

9.

i

Állományok

9.4. Szeriális állomány Szeriális egy adatállomány szerkezete akkor, ha az állomány struktúrájának a kialakítására semmilyen szabály sem vonatkozik. Egy szeriális állományban sem a rekordazonosítók, sem pedig a rekordazonosítók és tárolási címeik között nincs összefüggés (kapcsolat). A szeriális állomány mindenféle rekordformátumot tud kezelni, a rekordok tetszőlegesen blokkolhatók vagy szegmentálhatók. A szeriális szerkezetű adatállományokat soros vagy szerkezet nélküli állományoknak is szokás nevezni.

9.4.1. Szeriális állományokkal végezhető műveletek • Létrehozása lényegében véve egy üres tevékenység, mivel nincs szerkezete, amit létre kellene hozni. • A bővítés igen egyszerű művelet, mivel a rekordok logikai sorrendjét nem kell figyelembe venni. A hozzáadandó rekordot egyszerűen az utolsó felírt rekord után helyezzük el. • A törlés alapvetően logikai törléssel realizálható. Fizikai törlést csak közvetlen elérésű háttértároló és fix rekordformátum esetén lehet végrehajtani, a törlendő rekordot az utolsó rekorddal felülírva. Minden más esetben a fizikai törlés – a törlendő rekordot kihagyva – csak az állomány újraszervezésével oldható meg. • A csere közvetlen elérésű háttértároló és fix rekordformátum esetén realizálható, minden más esetben csak az állomány újraszervezésével oldható meg. • A rekordok elérése soros. • A keresést teljes kereséssel lehel megvalósítani. • Rendezés nincs. • Az állomány feldolgozásakor annak rekordjait azok fizikai sorrendje szerint olvassuk végig. • Az újraszervezés művelete csak cserénél merül fel, illetve akkor, ha a logikailag törölt rekordokat fizikailag is törölni akarjuk (lásd fent). A szeriális feldolgozási mód akkor jó megoldás, ha a helyigény minimális, nagyon rövid a karbantartási idő, és elfogadható a viszonylag hosszú visszakeresési idő. Ezért a szeriális állománynak minden olyan esetben hatékony az alkalmazása, ha csak létre kell hozni egy adatállományt, amit időnként bővíteni akarunk. Akkor is célszerűen alkalmazható, ha a feldolgozandó rekordok sorrendje teljesen közömbös, és a teljes állományt vagy az állományt alkotó rekordok többségét fel kell dolgoznunk.

i

i i

i

i


i

9.5.

Szekvenciális állomány

i

35

9.5. Szekvenciális állomány Ha egy adatállományban a logikai rekordok kívánt sorrendjét úgy érjük el, hogy a rekordokat a tárolón a kíván sorrendet meghatározó elsődleges kulcs növekvő vagy csökkenő sorrendjében, folyamatosan helyezzük el egymás után, akkor a szekvenciális állományban a rekordok közötti logikai kapcsolatot a fizikai sorrend teremti meg azáltal, hogy a rekordok logikai és fizikai sorrendje azonos. A szekvenciális állomány mindenféle rekordformátumot tud kezelni, rekordjai tetszőlegesen blokkolhatók vagy szegmentálhatók.

9.5.1. Szekvenciális állományokkal végezhető műveletek • Létrehozása egy vagy két lépésben történhet. Ha egy lépésben hozzuk létre, akkor biztosítani kell a rekordok elvárt érkezési sorrendjét. Ha a rekordok érkezési sorrendje véletlenszerű, akkor először egy szeriális állományt alakítunk ki, majd ezt rendezve kapjuk a szekvenciális állományt. • A bővítés csak újraszervezéssel hajtható végre. • Törölni logikailag lehetséges. A fizikai törlés újraszervezéssel valósítható meg. • A csere közvetlen elérésű háttértároló és fix rekordformátum esetén realizálható, minden más esetben csak az állomány újraszervezésével oldható meg. • A soros és szekvenciális elérés ezúttal ugyanazt jelenti, mivel a rekordok logikai és fizikai sorrendje megegyezik. • A lineáris keresés minden esetben végrehajtható, de bináris keresést is tudunk alkalmazni fix rekordformátum és közvetlen elérésű háttértároló esetén. • Rendezés nincs, értelmetlen, a rekordok elsődleges kulcsuk alapján eleve rendezettek. • A feldolgozás alapja a keresés. Lineáris keresést használva egyszerre több rekordot is feldolgozhatunk. Ilyenkor elegendő egyszer végigolvasni az állományt, ha a keresés előtt rendezzük a keresendő rekordokat elsődleges kulcsuk szerint. • Az újraszervezés igénye bővítéskor, fizikai törléskor, illetve bizonyos esetekben cserénél merül fel (lásd fent). A szekvenciális állományszerkezet előnye, hogy • soros és közvetlen elérésű háttértárolón egyaránt létrehozható, • jó kapacitáskihasználást tesz lehetővé, • szekvenciális módon való feldolgozása egyszerű.

i

i i

i

i


i

36

9.

i

Állományok

Hátránya, hogy • nem támogatja a közvetlen elérést, • aktualizálása újraszervezéssel oldható meg (kivételt képez a közvetlen elérésű háttértárolón elhelyezkedő szekvenciális állományok rekordjainak törlése vagy módosítása), • létrehozását rendezés vagy összeválogatás előzi meg.

9.6. Direkt állomány A direkt és a random állományok asszociatív szerkezetű állományok. Felépítésük és kezelésük a korábban megismert kulcstranszformációs táblázatokéhoz hasonló. A rekordok háttértárolón elfoglalt helye egy hash függvény segítségével határozható meg, amely a logikai rekordazonosítóhoz (az elsődleges kulcshoz) rendel egy lemezcímet. Amennyiben a hash függvény kölcsönösen egyértelmű, akkor direkt állományról, ha csak egyértelmű, random állományról beszélünk. Ha egy logikai adatállományban az elméletileg számba vehető rekordok és ezen keresztül a rekordazonosítók száma közelít az állományban ténylegesen előforduló rekordazonosítók számához, azaz ha az állományt alkotó rekordazonosítók halmazának az eloszlása egyenletes vagy közel egyenletes, akkor célszerűen megvalósítható a kölcsönösen egyértelmű kapcsolatteremtés a logikai rekordok és a fizikai tárolási címek között. A nem teljesen egyenletes eloszlású rekordazonosítók esetén azt a gyakorlatot kell követnünk a kölcsönösen egyértelmű megfeleltetés érdekében, hogy az állományban ténylegesen nem létező rekordok számára is helyet foglalunk. Ezzel a megoldással a tárolóterületen felhasználatlan tárolási egységek (címek) alakulnak ki. A kölcsönösen egyértelmű hash függvény a logikai rekordazonosítók növekvő sorrendjét létrehozva állítja elő az 1., 2., . . . , n. címeket. A hash függvénynek e tulajdonsága teszi lehetővé, hogy a direkt szerkezetű állományokat ne csak közvetlen eléréssel, hanem szekvenciálisan is feldolgozhassuk.

9.6.1. Direkt állományokkal végezhető műveletek A direkt szerkezetű állomány fizikailag egyetlen területből (adatterület) épül föl, és csak címezhető háttértárolón hozható létre. Az állomány helyigényét az elméletileg számba vehető rekordazonosítók darabszáma és a logikai rekordok hossza egyértelműen meghatározza. A direkt szerkezetű állományok csak fix hosszúságú rekordokból építhetők föl. Az állomány rekordjai nem blokkolhatók és nem szegmentálhatók, azaz egy blokk mérete a logikai rekordmérettel egyezik meg. • Az állományt két lépésben lehet létrehozni. Az első lépésben meghatározzuk a hash függvényt, kiszámítjuk a kezelendő rekordok darabszámát, majd

i

i i

i

i


i

9.7.

Random állomány

i

37

kialakítjuk az állomány vázát, azaz előkészítjük a tárolóterületet a rekordok befogadására. A második lépés valójában nem más, mint a már meglévő váz, vagyis az üres állomány feltöltése tartalommal, azaz a tényleges rekordokkal. A művelet végén maradhatnak üres rekordhelyek (ún. álrekordok). • Szűkebb értelemben véve bővítésről nem beszélhetünk. Tágabb értelemben véve új rekordokat a leképezési eljárás (hash függvény) által meghatározott címre lehet beilleszteni. Bővítéskor tehát „csak” a helyére kell tenni az újonnan érkező rekordot. • A szükségtelenné vált rekordokat logikailag töröljük úgy, hogy egy törlőbájttal megjelöljük, hogy az adott rekord már nem élő, vagy a teljes rekordot (esetleg csak a kulcsot) valamilyen jellel felülírjuk. A törlés következtében feleslegessé váló rekordhelyet más logikai azonosítójú rekord tárolására nem lehet felhasználni. • Egy rekordban a logikai rekordazonosítón kívül bármelyik adatelem értékét lehet cserélni. • A rekordok elérése közvetlen. • A keresés nem értelmezett. • A direkt szerkezetű állományok lehetővé teszik a bennük elhelyezkedő rekordoknak mind szekvenciális, mind pedig közvetlen elérésen alapuló feldolgozását, amely ezek szerint lehet: – soros, a rekordok fizikai sorrendjében; – szekvenciális, ami a hash függvény korábban említett tulajdonságából következően megegyezik a soros feldolgozással; – közvetlen, a hash függvény segítségével; – szakaszos szekvenciális, ahol a szakasz első rekordját közvetlenül, a továbbiakat pedig szekvenciálisan érjük el. • Hagyományos értelemben véve a direkt szerkezetű állományok újraszervezésére nincsen szükség, mert az állomány létrehozásakor az elméleti rekordszámnak megfelelő helyet foglaljuk le. Felmerülhet viszont az újraszervezés igénye akkor, ha változik, azaz bővül vagy szűkül az elméletileg számba vehető logikai rekordazonosítók tartománya.

9.7. Random állomány A csak egyértelmű (de nem kölcsönösen egyértelmű) hash függvény miatt előfordul, hogy a különböző azonosítójú rekordok ugyanarra a címre képződnek le. A random

i

i i

i

i


i

38

9.

i

Állományok

szerkezetű állományok túlcsordult rekordjainak elhelyezéséről és kezeléséről külön technika segítségével kell gondoskodnunk.

9.7.1. Túlcsordult rekordok kezelése A túlcsordult rekordok elhelyezésére alapvetően kétféle lehetőség kínálkozik: vagy az elsődleges adatterületen, vagy független túlcsordulási területen. • Nyílt címzés Segítségével a túlcsordulttá váló rekordok az elsődleges adatterületen tárolhatók. A módszer lényege, hogy a túlcsordulttá váló rekordot a leképezési eljárás által megadott címet követő címen próbáljuk elhelyezni. Ha ez nem sikerül, akkor az azt követőn, mindaddig folytatva így a keresést, míg szabad tárolóhelyet nem találunk. Az állomány vége esetén a keresés az állomány elején folytatódik, a leképezési eljárás által megadott címig. Általában e módszer akkor hatékony, ha nagy a tárolási cím kapacitása, és akkor gazdaságtalan, ha a tárolási cím kapacitása kicsi. Nagy hátránya, hogy nem szinonim rekord is túlcsordulttá válhat azáltal, hogy helyét egy előzőleg már túlcsordult rekord elfoglalta. Ez a negatív hatás az állomány két lépésben történő létrehozásával csökkenthető. Az első lépésben csak azokat a rekordokat helyezzük el azállományban, amelyek nem válnak túlcsordulttá. A túlcsorduló rekordokat átmenetileg egy munkaterületre tesszük, és egy második lépésben írjuk fel őket az adatállományba, miután minden nem túlcsordult rekordot felvittünk az állományba. A bővítések során ez a negatív hatás tovább nem csökkenthető. • Láncolás A hash függvény által meghatározott eredeti helyre került rekordot és az onnan túlcsordult rekordokat egy láncba fűzzük fel a rekordokban elhelyezett mutatómező segítségével. A mutató szerkezethordozó információ, nem része a logikai rekordnak, ezzel az állományszerkezet összetetté válik. • Szabad helyek nyilvántartása A módszer lényege, hogy egy külön nyilvántartást (táblázatot) vezetünk azokról a tárolási címekről, melyekhez még szabad hely tartozik. Ez a táblázat a tárban helyezkedik el, mérete kicsi. Ha a hash függvény egy újonnan érkező rekordot olyan tárolási címre képez le, amely már telített, a szabad helyekről vezetett nyilvántartás segítségével könnyen megtalálható az a tárolási cím, mely a címképző eljárás által meghatározott, de már telített tárolási címhez a legközelebb helyezkedik el. Az újonnan érkező rekordot ezen a címen tároljuk. Az újonnan belépett rekord eredeti tárolási címén elhelyezett mutató teremti meg a kapcsolatot a rekord eredeti és tényleges címe között. Ha a tárolási címhez már több túlcsordult rekord tartozik, és e címre egy újabb rekord képződik le, amelyet a szabad helyeket nyilvántartó táblázat

i

i i

i

i


i

9.7.

Random állomány

i

39

alapján elhelyezünk az eredeti tárolási címhez legközelebb, akkor az eredeti címen már nem hagyhatunk a túlcsordultra utaló mutatót, hanem a túlcsordulási lánc utolsó rekordját tartalmazó címhez kötjük a rekordot, azaz itt helyezzük el a kapcsolathoz szükséges mutatót. (Praktikus módon minden tárolási címen két mutató elhelyezésére biztosítunk lehetőséget, az egyik mutató az adott tárolási címhez tartozó első túlcsordult rekordra mutat, míg a második a túlcsordulási lánc utolsó elemére.) A szabad helyek nyilvántartásának módszere akkor alkalmazható hatékonyan, ha a tárolási cím kapacitása viszonylag nagy, és kevés rekordot akarunk tárolni. • Vyssotzky-módszer A túlcsordult rekordok elsődleges adatterületen való tárolására a nyílt címzés és a láncolás mellett használatos még az ún. Vyssotzky-módszer is. A módszer azon alapul, hogy különböző leképezései algoritmusok (hash függvények) különböző címeket eredményeznek. Ha tehát egy rekord túlcsordulttá válik, akkor ugyanazt a rekordazonosítót egy másik hash függvénnyel újabb tárolási címre (rekordhelyre) képezzük le. Ezt mindaddig ismételjük, míg a kérdéses rekord számára szabad rekordhelyet nem találunk. Ha az összes hash függvényt kimerítettük, és a rekordot még mindig nem sikerült egy, a hash függvények által meghatározott címre (tárolási cím) elhelyezni, akkor folytonos kereséssel a rekordot a legközelebbi nagyobb szabad tárolási címre írjuk. • Független túlcsordulási terület használata A független túlcsordulási területet használjuk a túlcsordult rekordok elhelyezésére. Az állományt két lépésben hozzuk létre. Az elsőben kialakítjuk az állomány vázát: mind az elsődleges, mind pedig a túlcsordulási terület minden egyes rekordhelye egy külön mutatómezőt tartalmaz. Az elsődleges területen lévő rekordhelyeken a mutatómezők értéke nil lesz, a túlcsordulási területen lévő rekordhelyeket viszont a mutatómezőkben elhelyezett mutatókkal összeláncoljuk. A túlcsorulási terület első rekordját jelzőrekordként használjuk, mely mindenkor a túlcsordulási területen lévő legelső szabad tárolási címet (rekordhelyet) mutatja. A létrehozás második fázisában helyezzük el a hash függvény által meghatározott címekre a rekordokat. Ha egy rekord túlcsordulttá válik, akkor a jelzőrekord által meghatározott első szabad tárolási címre kerül a túlcsordulási területen. Az elsődleges adatterületen a hash függvény által meghatározott címen lévő rekord mutatómezőjébe (ahonnan a túlcsordulás történt) a túlcsordult rekord címét tesszük. Ezzel egyidejűleg aktualizálódik a jelzőrekord is úgy, hogy a túlcsordulási területre újonnan bevitt rekord tárolási címén lévő mutató kerül a jelzőrekordba (ami a következő szabad helyet címzi), és helyére nil érték íródik.

i

i i

i

i


i

40

9.

i

Állományok

• Osztott szabad helyek módszere Ennél a módszernél az elsődleges adatterületen elkülönített túlcsordulási területeket jelölünk ki a tárolóeszköz felépítésének megfelelően. Ez sáv módban működő lemezeknél lehet például a cilinderen belül egy vagy több sáv. A módszer előnye, hogy nincs szükség külön fejmozgatási időre a túlcsordulási terület, illetve az azon lévő túlcsordult rekord eléréséhez (kivételt képez az a ritka eset, amikor egy túlcsordulási terület betelik), továbbá nincs lánc, így nem kell azt karbantartani, illetve megtakarítható a láncon való végighaladáshoz szükséges idő.

9.7.2. Random állománnyal végezhető műveletek A random állomány mindhárom rekordformátumot (fix, változó és határozatlan) tudja kezelni. A rekordokat általában nem blokkoljuk. • Az állományt két lépésben lehet létrehozni. Az első lépésben meghatározzuk a hash függvényt, kiválasztjuk a túlcsordult rekordok kezelésének a technikáját, kiszámítjuk a kezelendő rekordok darabszámát, majd mindezeket figyelembe véve kialakítjuk az állomány vázát, azaz előkészítjük a tárolóterületet a rekordok befogadására. A második lépés valójában nem más, mint a már meglévő váz, vagyis az üres állomány feltöltése tartalommal, azaz a tényleges rekordokkal. Ha a túlcsordult rekordokat nem túlcsordulási területen helyezzük el, akkor célszerű először csak a nem túlcsordult rekordokat elhelyezni, mert így egy túlcsordult rekord nem foglalhatja el egy később érkező nem túlcsordult rekord helyét. A művelet végén maradhatnak üres rekordhelyek (ún. álrekordok). • Az állomány bővítése új rekorddal a következőképpen történik: először a hash függvény által meghatározott rekordhelyre próbáljuk elhelyezni a rekordot, de ha az a rekordhely már foglalt, akkor a bővítő rekord az alkalmazott szinonimakezelési technika által előírt helyre fog kerülni. • A szükségtelenné vált rekordokat logikailag töröljük úgy, hogy az adott rekordot először megkeressük a hash függvény és az alkalmazott szinonimakezelési technika segítségével, majd egy törlőbájttal megjelöljük, hogy a rekord már nem élő, vagy a teljes rekordot (esetleg csak a kulcsot) valamilyen jellel felülírjuk. • Egy rekordban a logikai rekordazonosítón kívül bármelyik adatelem értékét lehet cserélni. Ha a rekord fix rekordformátummal rendelkezik, vagy ha a csere során csökken a rekord mérete, akkor egyszerűen felülírjuk a módosítandó rekordot a módosított értékkel. Ha viszont a csere során a módosított változat mérete meghaladja a módosítandó rekordét (változó vagy határozatlan rekordformátum esetén), akkor a módosítandó rekordot túlcsordult rekordként kell kezelni, és a bővítés folyamatával azonos módon kell elhelyezni a módosított rekordot, valamint törölni kell a módosítandó rekordot.

i

i i

i

i


i

9.8.

Összetett állományszerkezetek

i

41

• A rekordok elérése közvetlen, a hash függvényen és az alkalmazott szinonimakezelési technikán alapul. • A random állomány feldolgozása alapvetően a közvetlen elérésen alapul. Lehetőség van azonban az ún. cím szerinti szekvenciális, valamint a soros feldolgozásra is. A cím szerinti szekvenciális feldolgozási mód növelheti a hatékonyságot azáltal, hogy először a keresendő logikai rekordok tárolási címeit határozzuk meg a hash függvény, illetve a szinonimakezelési technika segítségével. Ezen címek sorbarendezésével ugyanis jelentős mértékben csökkenthető az egyes rekordok eléréséhez szükséges idő. A soros feldolgozási módot gyakorlatilag csak újraszervezéskor használjuk az újraszervezendő állomány rekordjainak beolvasására. • Az újraszervezési igény általában elég gyakori, hacsak nem statikus állományról van szó. Ha ugyanis nagy a rekordok fluktuációja (sok a törlés és a bővítés), akkor a hash függvény egyre több túlcsordult rekordot állít elő, így egy bizonyos ponton túl gazdaságtalanná válik a kialakított struktúra.

9.8. Összetett állományszerkezetek Az összetett állományszerkezeteket a feldolgozás gyorsítása, kényelmesebbé tétele érdekében alkalmazzuk. Alapját egy egyszerű szerkezetű állomány, az alapállomány képezi, amely legtöbbször szeriális vagy szekvenciális. Az alapállományra épülnek rá a plusz információhordozó adatok. Alapvetően két technikát különböztetünk meg: • láncolás esetén az információhordozó adatok az állományon belül jelennek meg mutatómezők formájában, ekkor a rekordokat láncolt listába fűzzük föl; • indexelés esetén a plusz információk az állományon kívül, általában egy (vagy több) indextábla formájában jelennek meg. Mivel mind a két technika lemezcímeket kezel, ezért az összetett állományszerkezetek csak közvetlen elérésű háttértárolón alakíthatók ki.

9.8.1. Indexelési technikák Egy állományt indexelhetünk a benne tárolt rekordok elsődleges vagy másodlagos kulcsa szerint. Elsődleges kulcs alapján történő indexelés esetén használhatunk egy olyan táblázatot, amelynek kulcs oszlopába az állomány rekordjaiban található elsődlegeskulcs-értékek, az érték oszlopába pedig az megfelelő rekordok lemezcímei kerülnek. Ezt a táblázatot nevezzük indextáblának. Az indextábla egy rendezett táblázat, azaz a kulcs oszlopában az alapállomány rekordjainak azonosítói növekvő sorrendben helyezkednek el. Általában kis méretű, ezért elfér a memóriában, ha mégsem, akkor szekvenciális állományként jelenik meg a háttértáron. Ha az indextábla a

i

i i

i

i


i

42

9.

i

Állományok

memóriában van, akkor bináris keresést alkalmazhatunk egy adott elsődlegeskulcsértékkel rendelkező rekord keresésére. A fenti konstrukciót elsődleges kulcsra épülő, egyszintű, teljes indexelésnek nevezzük. Amennyiben az indextáblában nem minden rekordazonosítót tüntetünk fel, akkor nem teljes (részleges) indexelésről beszélünk. A nem teljes indexelést az indextábla méretének csökkentése érdekében alkalmazzuk: az azonosítók halmazát részhalmazokra osztjuk az alapállomány címtartományának (egyenlő) részekre osztásával, és az indextáblában csak a részhalmazok első elemeit tüntetjük fel. Egy rekord keresésekor először az indextábla alapján behatároljuk a keresett azonosítót, majd a behatárolt részhalmaz kezdőcímétől kiindulva lineáris kereséssel folytatjuk a keresést az alapállományban. A nem teljes indexelés alkalmazásának feltétele, hogy az alapállomány szekvenciális legyen. Máskülönben ugyanis sem a részekre bontásnak, sem a részeken belül történő keresésnek nem lenne értelme. Nagyméretű állományok esetén célszerű lehet magát az indextáblát is indexelni. Az így kapott indextábla igény szerint ismét indexelhető, és így tovább. . . Ezt többszintű indexelésnek nevezzük. A második indexszinttől kezdve csak nem teljes indexelésnek van értelme. Minél magasabb indextábla-hierarchiát építünk föl, az elérés annál több transzformáción keresztül valósítható meg. Az állományt indexelhetjük egy másodlagos kulcs szerint is. Ekkor az indextábla kulcs oszlopába a rekordokban szereplő különböző másodlagoskulcs-értékeket írjuk, tehát a táblának annyi sora lesz, ahány különböző másodlagoskulcs-érték szerepel az alapállományban. Az egyes kulcsértékek mellé az érték oszlopba több lemezcím is kerülhet, azoké a rekordoké, amelyekben megtalálható az adott másodlagoskulcs-érték. Az indexelés most is lehet többszintű, ekkor azonban az első szinten csak teljes indexelésnek van értelme. A fentieket figyelembe véve a következő összetett állományszerkezeteket különböztetjük meg: • láncolt szeriális állomány, • indexelt szeriális állomány, • indexelt szekvenciális állomány, • multilista állomány és • invertált állomány.

9.9. Láncolt szeriális állomány A szeriális alapállomány rekordjainak elsődleges kulcsa szerint felépítünk egy láncszerkezetet, amely a szeriális állomány szekvenciális feldolgozását teszi lehetővé. Minden rekordba beépítünk egy mutatómezőt, amely logikai rekordazonosító szerint növekvő vagy csökkenő sorrendbe rendezve fűzi fel a rekordokat. A mutatómező értéke megmutatja, hogy hol helyezkedik el a tárolóeszközön az adott rekordot logikailag követő rekord. A lánc kezeléséhez szükség van egy, a logikailag első rekordot címző fejmutatóra, amely nem része az állománynak.

i

i i

i

i


i

9.10.

43

Indexelt szeriális állomány

technika kulcs elsődleges kulcs másodlagos kulcs

i

láncolás

indexelés

láncolt szeriális állomány

indexelt szeriális állomány indexelt szekvenciális állomány

multilista állomány

invertált állomány

9.2. ábra. Az összetett állományszerkezetek összefoglaló táblázata

9.9.1. Láncolt szeriális állományokkal végezhető műveletek • Létrehozása két lépésben történik. Első lépésben elhelyezzük a rekordokat a szeriális alapállományban. Második lépésben kialakítjuk a láncszerkezetet a mutatómezők kitöltésével. • Bővítéskor az érkező új rekordot a szeriális alapállomány utolsó rekordja után helyezzük el, majd beillesztjük a láncszerkezetbe a megfelelő helyre. • Rekord törlése az alapállományból a szeriális állománynak megfelelő módon történik, míg a láncszerkezetből minden esetben kiláncoljuk (fizikailag töröljük) a rekordot. • A csere az alapállománynak megfelelő módon történik. Mivel logikai rekordazonosítót nem írhatunk felül, ezért nem érinti a láncszerkezetet. • A rekordok elérése lehet soros (a fizikai sorrend szerint) vagy szekvenciális (a láncolási sorrend alapján). • Az állomány feldolgozása az elérésen alapul, történhet a rekordok fizikai sorrendje vagy a láncolási sorrend szerint. • Az újraszervezés igénye akkor merülhet fel, ha (1) a logikailag törölt rekordokat fizikailag is törölni szeretnénk az állományból, vagy ha (2) a rekordokat ellentétes irányú rendezettség alapján szeretnénk sorba láncolni.

9.10. Indexelt szeriális állomány Ahhoz, hogy egy kulcs szerinti rendezetlen adatállományban biztosítani lehessen az egyes rekordok közvetlen elérhetőségét, kapcsolatot kell teremteni a rekordazonosítók és a tárolási címek között. Ha ez a szükséges kapcsolatteremtés a rekordazonosítók és a tárolási címek között az indexelési technika segítségével valósul meg, akkor indexelt szeriális állományszerkezetet kapunk. Az indexelt szeriális állományszerkezet két fő részből tevődik össze: • egy szeriális alapállományból és

i

i i

i

i


i

44

9.

i

Állományok

• a szeriális alapállomány logikai rekordjainak azonosítóira felépített indexstruktúrából. A két összetevő együttesen alkotja magát az indexelt szeriális állományt. Az alapállomány logikai rekordjainak az indexelése csak teljes lehet, többszintű indexeléskor viszont a magasabb szinten lévő indexek – értelemszerűen – nem teljes indexek lesznek.

9.10.1. Indexelt szeriális állomány létrehozása Az indexelt szeriális állományokat két lépésben hozzuk létre. 1. Az alapállományt alkotó logikai rekordok háttértárolón való elhelyezésével egyidejűleg az indexszerkezet elemeit is kialakítjuk. Minden logikai rekordhoz hozzárendelünk egy elemet az indextáblában, amely a logikai rekord azonosítóját és tárolási címét tartalmazza. 2. Ez után történik az indexstruktúra első szintjének a felépítése, ami azt jelenti, hogy az indextábla első lépésben kialakított elemeit logikai rekordazonosító szerint növekvő sorrendbe rendezzük, hacsak eleve nem rendezett sorrendben tároltuk őket. Ha többszintű indexstruktúrát használunk, akkor a magasabb szintű indexeket egymás után, sorban, az előzőleg létrehozott szintre ráépítve alakítjuk ki.

9.10.2. Indexelt szeriális állomány bővítése Az újonnan érkező rekordok folyamatosan a szeriális szerkezetű alapállomány végére kerülnek. Mivel indexelt szeriális állományok esetén a legalsó szinten csak teljes indexelés valósítható meg, az érkező logikai rekordokkal egyidejűleg az új rekordokhoz tartozó elemek is elhelyezésre kerülnek az indexstruktúrában. • Ha az indexstruktúra egyszintű, és az indextábla elfér a tárban, akkor az újonnan érkező rekordokhoz tartozó elemek az azonosító szerinti szekvenciális sorrendnek megfelelő helyre kerülnek az indextáblában. Ez a művelet ekkor egy rendezett táblázatba történő beszúrás. • Ha az indexstruktúra többszintű, vagy az indextábla nem fér el a központi tárban, akkor egy szekvenciális szerkezetű indexállomány bővítésével állunk szemben. Ilyenkor az indexstruktúra legalsó szintjét valamilyen módon átszervezzük, és – többszintű indexelés esetén – a magasabb szinteken is keresztülvezetjük a változásokat. A gyakorlatban azt a megoldást alkalmazzák, hogy az indexhierarchia legalsó szintjén lévő indexrekordokat csoportokban (bucketekben) helyezik el úgy, hogy a csoportokban üres helyeket hagynak az újonnan érkező indexrekordok számára. Egy csoport meghatározott számú indexrekord befogadására alkalmas. Mérete változó, egy csoport gyakorlatilag egy blokkot jelent. Egy ilyen indexcsoportban az egyes logikai rekordokra vonatkozó indexrekordok sorrendje szekvenciális. A módszer hátránya, hogy

i

i i

i

i


i

9.10.

Indexelt szeriális állomány

i

45

az indexcsoport telítődése után szükségessé válik az indexstruktúra újraszervezése.

9.10.3. Törlés indexelt szeriális állományból Mivel a törölt rekordok helyét nem tudjuk felhasználni, az alapállományból logikailag töröljük a törlendő rekordot. Ha az indexelési eljárás egyszintű, és az index a központi tárban van, akkor az indextáblából mint rendezett táblázatból töröljük a törlendő rekordhoz tartozó elemet. Ha az indexelés többszintű, vagy az indextábla nem fér el a tárban, akkor két lehetőség van: • A törlendő rekordokat csak az alapállományból töröljük logikailag. Ekkor a későbbi feldolgozás során minden logikai rekord olvasását követően el kell döntenünk, hogy a beolvasott rekord törölt-e vagy sem. • A törlendő rekord alapállományból való törlése mellett az indexállományból is töröljük a törlendő rekordhoz tartozó indexrekordot. Ez utóbbi egy szekvenciális állományból történő törlési művelet.

9.10.4. Csere Fix hosszúságú rekordokból felépülő indexelt szeriális szerkezetű állományok esetén a csere az indexstruktúrán keresztül a rekord beolvasását, és módosított változatának visszaírását jelenti. Mivel logikai rekordazonosítót nem cserélhetünk, a csere az indexszerkezetet nem érinti.

9.10.5. Elérés, feldolgozás, újraszervezés Az indexelt szeriális szerkezetű állományok rekordjainak elérése lehet • soros (a rekordok fizikai elhelyezkedésének sorrendjében), • szekvenciális (a rekordok logikai sorrendjének megfelelően, az indexszerkezet alapján), • közvetlen (az indexszerkezet alapján). Ha csak a feldolgozási igényeket vesszük figyelembe, akkor leginkább olyankor célszerű az indexelt szeriális szerkezet alkalmazása, amikor viszonylag ritka a szekvenciális feldolgozási igény, és vagy a közvetlen, vagy a soros elérésen alapuló feldolgozás dominál. Az indexelt szeriális állományok újraszervezésére két okból van szükség: • ha sok a törölt rekord az alapállományban, • ha az indexstruktúra többszintű, és a legalsó szintje nem bővíthető újabb rekordokkal, • ha az indexstruktúra kezelése már nem kellően hatékony.

i

i i

i

i


i

46

9.

i

Állományok

9.11. Indexelt szekvenciális állomány Egy indexelt szekvenciális állomány nem más, mint egy olyan, indexszerkezettel kibővített szekvenciális állomány, mely lehetővé teszi a közvetlen elérésen alapuló feldolgozást és karbantartást is. Az indexelt szekvenciális állomány abban hasonlít a szekvenciális állományhoz, hogy szekvenciálisan is feldolgozható, mivel a benne elhelyezkedő rekordok azonosító szerint szekvenciálisan rendezettek. Ez a szekvenciális sorrend kezdetben (lásd létrehozás) azonos a fizikai sorrenddel, később (lásd bővítés) a kettő bizonyos mértékig elválik. Az indexelt szekvenciális állomány abban hasonlít a random (direkt) állományhoz, hogy az állomány logikai rekordjai közvetlenül elérhetők, ami egy szekvenciális állomány esetén nem lehetséges. Az alapvető különbség az indexelt szekvenciális és a random (direkt) állományszerkezet között az, hogy míg a random (direkt) állománynál a közvetlen hozzáférést az azonosítóból egy algoritmussal képzett cím alapján biztosítjuk, addig az indexelt szekvenciális állományoknál a közvetlen hozzáférést az elkülönítetten kezelt és tárolt indextáblá(k)ban elhelyezett azonosító és cím közötti kapcsolat teszi lehetővé. Az indexelt szekvenciális állományszerkezet tehát két fő részből tevődik össze: • egy (létrehozáskor) szekvenciális szerkezetű alapállományból és • a szekvenciális alapállomány logikai rekordazonosítóira felépített indexstruktúrából. A két összetevő együttesen alkotja magát az indexelt szekvenciális állományt. Egy indexelt szekvenciális állomány csak közvetlen elérésű (címezhető) háttértárolón hozható létre. A rekordokat a szekvenciális alapállományban tároljuk, az egyes logikai rekordokat a rekordazonosítóval különböztetjük meg. Az indexstruktúra segítségével biztosítható az állomány egyes elemeihez való közvetlen hozzáférés.

9.11.1. Indexelt szekvenciális állományok létrehozása Létrehozáskor az alapállomány rekordjainak fizikai és logikai sorrendje azonos. Erre az alapállományra építjük fel létrehozáskor az indexstruktúrának megfelelő indextáblá(ka)t. Az alkalmazott indexelési eljárás lehet teljes és nem teljes is. Mindkét indexelési eljárással felépíthetünk egyszintű és többszintű indexstruktúrát.

9.11.2. Indexelt szekvenciális állományok bővítése A bővítés során továbbra is biztosítani kell mind a szekvenciális, mind pedig a közvetlen elérés lehetőségét. Erre többféle megoldás is kínálkozik: • az állomány újraszervezése, • független túlcsordulási terület(ek) alkalmazása,

i

i i

i

i


i

9.11.

Indexelt szekvenciális állomány

i

47

• osztott szabad helyek módszere. Bővítés újraszervezéssel Az újraszervezéssel történő bővítés csak olyan adatállományok esetén alkalmazható, amelyeknél ritka a változás, a bővítési igény, ugyanakkor gyakori a feldolgozás, melynek során fontos szempont a hatékonyság. Független túlcsordulási terület(ek) használata Ennél a módszernél független túlcsordulási terület(ek)et alkalmazunk az újonnan érkező rekordok elhelyezésére. A túlcsordulási terület(ek)en elhelyezett rekordokat láncolással vagy mutatótömb segítségével kezelhetjük. Túlcsordulási területen elhelyezett rekordok kezelése láncolással Az újonnan érkező rekordok független túlcsordulási területre helyezésével szétválik a már felépített indexelt szekvenciális állományban a rekordok logikai és fizikai sorrendje. Az adatterületen és a túlcsordulási területen lévő rekordok között már csak a logikai sorrendet lehet fenntartani. A fizikailag elkülönült rekordok közötti logikai sorrendet láncolással kétféleképpen hozhatjuk létre. • Az egyik megoldás, hogy minden logikai rekordban elhelyezünk egy mutatómezőt, és ha egy új rekordot túlcsordulási területre teszünk, akkor a kialakított mutatómezőkben elhelyezendő mutatók segítségével beláncoljuk a túlcsordulási területre került rekordot az őt logikailag megelőző és rákövetkező rekordok közé. A megoldás hátránya a bonyolult lánckapcsolatok mellett, hogy a minden rekordban elhelyezett mutatómező növeli az állomány számára szükséges helyet, valamint lerontja az állomány szekvenciális módon való feldolgozásának a hatékonyságát, ha sok a pótlólag bevitt rekord. • Javítható a láncolási technika hatékonysága, ha a logikai rekordokat csoportokba szervezzük, és az így kialakított csoportokhoz túlcsordulási láncokat kapcsolunk. Ez azt jelenti, hogy minden csoporthoz külön túlcsordulási lánc tartozik. A bővítések során a csoportokon belül megtartjuk a logikaival azonos fizikai sorrendet. Egy új rekord beillesztésekor a rekordot a szekvenciális sorrendnek megfelelő helyre (csoportba) írjuk úgy, hogy a csoporton belül is megtartjuk a rekordok szekvenciális sorrendjét. E művelet eredményeképpen az eredetileg a csoportban lévő legnagyobb azonosítójú rekordot – helyhiány miatt – nem tudjuk a csoporton belül elhelyezni. Így ezt a rekordot bekapcsoljuk a csoporthoz tartozó túlcsordulási láncba, melynek kezdőcímét az indexhierarchia legalsó szintjén lévő és az adott csoportot indexelő indexrekordban helyezzük el.

i

i i

i

i


i

48

9.

i

Állományok

Ha az újonnan érkező rekord szekvenciális sorrendnek megfelelő helye eleve valamelyik csoporthoz tartozó túlcsordulási láncba esik, akkor a rekordot a túlcsordulási láncba illesztjük, megtartva a lánc elemeinek szekvenciális sorrendjét. Azt, hogy egy érkező rekord szekvenciális sorrendnek megfelelő helye melyik csoportban van, csak akkor lehet eldönteni, ha az adatcsoportot indexelő indexrekordba a csoporthoz tartozó túlcsordulási lánc kezdőcíme mellett elhelyezzük annak a logikai rekordnak a kulcsát is, amelynek kulcsa létrehozáskor a csoportban a legnagyobb volt. Mindezek mellett az indexrekord tartalmazza a csoportban ténylegesen elhelyezkedő legnagyobb azonosítójú logikai rekord kulcsát is. Így valójában a csoportot indexelő indexrekord négy információt tárol: – a csoportban lévő legnagyobb azonosítójú logikai rekord kulcsát a létrehozáskor, – a csoportban ténylegesen helyet foglaló legnagyobb azonosítójú logikai rekord kulcsát, – a csoporthoz tartozó túlcsordulási lánc kezdőcímét, – a csoport első (a legkisebb azonosítóval rendelkező) logikai rekordjának kezdőcímét. Túlcsordulási területen elhelyezett rekordok kezelése mutatótömbök segítségével A módszer lényege, hogy az indexhierarchia legalsó szintjén lévő indexrekordba nem az indexrekord által indexelt csoporthoz tartozó túlcsordult rekordok láncának kezdőcímét helyezzük csak el, hanem a sávhoz tartozó összes túlcsordult rekord címét. A mutatótömb alkalmazása megszünteti a túlcsordulási területen lévő rekordok hosszadalmas – láncon keresztüli – elérését, lehetővé teszi az összes túlcsordulási területen lévő rekord közvetlen elérését. Külön kérdés annak eldöntése, hogy hány mutatónak jelöljünk ki helyet az indexrekordban. A módszer legnagyobb hátránya éppen a gyakorlati megvalósításában rejlik. Osztott szabad helyek módszere Az újonnan érkező rekordok kezelésének egy másik lehetséges módszere, hogy az állomány létrehozásakor már eleve üres helyeket hagyunk az újonnan érkező rekordok számára. Nem lenne gazdaságos a rekordok tárolásakor minden rekord között üres (szabad) helyeket hagyni, ezért a logikai rekordokat csoportokba szervezzük, és az egyes csoportokban marad üres hely az újonnan érkező rekordok számára. Az üres (szabad) helyeket tartalmazó alapállomány a későbbiekben alkalmas arra, hogy ezekre az üres helyekre a bővítések során érkező új rekordok elhelyezhetők legyenek. Az újonnan érkező rekordok elhelyezésére kétféle lehetőség is kínálkozik:

i

i i

i

i


i

9.11.

Indexelt szekvenciális állomány

i

49

• Az újonnan belépő rekordok elhelyezhetők egy csoportban anélkül, hogy megváltoztatnánk a már ott lévő rekordok sorrendjét. Ez a megoldás nehezíti a visszakeresést, mivel a pótlólag bevitt rekordok megtalálásához végig kell keresni azt a csoportot, ahol az újonnan érkező rekordot elhelyeztük. • A rekord beillesztésekor a csoportba tartozó rekordokat átrendezzük. Ez időigényes megoldás, mert az átrendezéshez a csoportba tartozó összes rekordot a háttértárolóról az operatív tárba és onnan vissza kell mozgatni. A szekvenciális feldolgozás viszont nagyságrendekkel gyorsabb, mivel a logikai rekordok csoporton belüli sorrendje, azaz a fizikai sorrend azonos a logikai sorrenddel. Mivel az állományból való szekvenciális olvasás gyakoribb, mint az új rekordok beillesztése, ez a megoldás jóval gazdaságosabb. Az osztott szabad helyek módszerének további előnye, hogy az újonnan érkező rekordokat az adatterületen helyezzük el, szükségtelenek a logikai sorrendet meghatározó láncok. Ezáltal lényegesen gyorsabb az újonnan bevitt rekordok visszakeresése, hiszen gyakorlatilag nincsenek túlcsordult rekordok az állományban. E módszer segítségével tulajdonképpen dinamikus újraszervezést valósíthatunk meg mindaddig, amíg van szabad hely az újonnan érkező rekordok számára.

9.11.3. További műveletek • Törléskor gyakorlatilag majdnem mindig logikai törlést alkalmazunk az állomány bonyolult szerkezete miatt. A felhasználó feladata a beolvasott rekordról eldönteni, hogy az élő-e vagy törölt. • Fix hosszúságú rekordokat feltételezve a csere a legegyszerűbb karbantartási művelet. Változó hosszúságú rekordok esetén a csere olyan problémákat vet fel, mint például a rekordok bővítése vagy csonkítása. Elsődleges kulcsot nem cserélhetünk, ezért a művelet végrehajtása nem érinti az indexszerkezetet. • A rekordokat kétféleképpen érhetjük el: szekvenciális és közvetlen eléréssel. • Az indexelt szekvenciális állományokat szekvenciálisan vagy közvetlen eléréssel szokás feldolgozni. Bizonyos adatállományokat döntően szekvenciálisan dolgoznak fel, és elenyésző a közvetlen elérés igénye, mások esetében az elérés alapvetően közvetlen, és igen ritka a szekvenciális feldolgozás igénye. Az indexelt szekvenciális szerkezetű állományok hatékonyságát meghatározó tényezőkön elsősorban – a blokkolást, – az indexszintek és az indexelési eljárás helyes megválasztását, – a bővítések kezelésének technikáját, – az újraszervezés módját és – a feldolgozási módot

i

i i

i

i


i

50

9.

i

Állományok

kell érteni. • Az állomány időnkénti újraszervezését – a bővítések okozta többletfeldolgozási idő, – a törölt rekordok által lekötött területek, – a túlcsordulási területek telítettsége és – az állomány fizikai paramétereinek (blokkolás, méret, túlcsordulási területek és indexszintek) helytelen megválasztása teheti szükségessé.

i

i i

i

6 15:51 page 27 #23

Recommend Documents