N8

8.

B-fák

˝ Általános keresofák ˝ olyan absztrakt adatszerkezet, amely fa és minden cellájában adatsorozat van; Adat : F → E ∗ . Az általános keresofa Tehát minden p ∈ F -re Adat(p) = ha1 , · · · , ak i. Ekkor azt mondjuk, hogy p rangja k, Rang(p) = k. ˝ ha ∀p ∈ F -re teljesül: Definíció. Az F fa (általános) keresofa, 1. p-nek Rang(p) + 1 = Fok(p) számú fia van. 2. Adat(p) = ha1 , · · · , ak i rendezett sorozat. 3. Max(Ff iu(p,i−1) ) ≤ ai ≤ Min(Ff iu(p,i) ), i = 1, · · · , Rang(p), ahol Ff iu(p,i) az F fa f iu(p, i)-gyökeru˝ részfája. Definíció. Az F fa t -rendu˝ (t ≥ 2) B-fa, ha teljesül rá az alábbi 4 feltétel:

p

...

a1

Ff iu(p,1)

Ff iu(p,0)

ak

Ff iu(p,k)

...

˝ szemléltetése. 1. ábra. Általános keresofa

˝ 1. Keresofa. 2. A gyökér kivételével minden p ∈ F pontra t − 1 ≤ Rang(p) ≤ 2t − 1. 3. Minden p ∈ F nem levél pontra Fiu(p, i) 6=⊥, i = 0, · · · , Rang(p). 4. Minden p ∈ F levélpontra d(p) = h(F), azaz minden levél pont mélysége azonos. ... ... ... ...

...

...

... ...

...

...

...

...

... ...

2. ábra. B-fa séma.

8.1. lemma. Minden n adatot tartalmazó t -rendu˝ F B-fára h(F) ≤ logt n+1 2 + 1. Bizonyítás. A legkevesebb adatot tartalmazó B-fában a gyökérben 1, a többi pontban t − 1 adat van. A második szinten 2 pont

1

Szint Pont 1

1

2

2

2(t − 1)

3

2t

2t(t − 1)

4

2t 2

2t 2(t − 1)

...

... ...

Adat

1

...

...

...

... h

2t h−2

2t h−2(t − 1)

3. ábra. h magasságú, legkevesebb adatot tartalmazó B-fa.

van, az i-ediken i > 2 esetén 2t i−2 pont van. Tehát a h magasságú t -rendu˝ B-fa legalább h

1 + ∑ 2t i−2 (t − 1) = i=2

h

1 + 2(t − 1) ∑ t i−2

=

i=2

h−2

1 + 2(t − 1) ∑ t i 1 + 2(t − 1)

=

i=0 t h−1 − 1

= t −1 1 + 2(t h−1 − 1) = 2t h−1 − 1

Tehát

n ≥ 2t h−1 − 1 n+1 ≥ t h−1 2 n+1 h − 1 ≤ logt 2 n+1 h ≤ logt +1 2

 Például, ha n = 10000000, t = 100, akkor h(F) ≤ 4.349 Egy p pontot telítettnek nevezünk, ha Rang(p) = 2t − 1, illetve minimálisnak, ha Rang(p) = t − 1.

8.1.

˝ B-fa bovítése

˝ oút ˝ pontjainak sorozata, tehát p1 a fa gyökere és pm levélpont. A bovítés ˝ Legyen hp1 , . . . , pm i a k-kulcshoz tartozó bovít mindig levélpontba történik. 8.1.1.

Optimista stratégia

˝ ˝ oút ˝ pm végpontját. Ha pm nem telített, akkor szúrjuk be az új k kulcsú adatot. Ha pm telített, akkor Eloször keressük meg a bovít két két változat szerint folytatódhat a muvelet: ˝ Egyszeru˝ módszer: Vágjuk ketté az aktuális pontot, és a keletkezo˝ (b, q) adat-pointer párnak az apába történo˝ beszúrásával ˝ o˝ úton visszafelé haladva mindaddig, amíg nem telített ponthoz érünk, vagy a gyökérpontot kettévágva új folytassuk a bovít gyökérpont keletkezik (ekkor növekszik a fa magassága). 2

Körültekinto˝ módszer: Ha az aktuális pont bal vagy jobb testvére nem telített, akkor adjunk át egy adat-pointer párt, amivel az aktuális pont telítettségét megszüntetjük. Ha nem lehet átadni egyik testvérnek sem, akkor az egyszeru˝ módszer szerinti kettévágást végezzünk. 8.1.2.

Optimista stratégia

˝ ˝ oút ˝ pm végpontját. Ha pm nem telített, akkor szúrjuk be az új k kulcsú adatot. Ha pm telített, akkor Eloször keressük meg a bovít két két változat szerint folytatódhat a muvelet: ˝ Egyszeru˝ módszer: Vágjuk ketté az aktuális pontot, és a keletkezo˝ (b, q) adat-pointer párnak az apába történo˝ beszúrásával ˝ o˝ úton visszafelé haladva mindaddig, amíg nem telített ponthoz érünk, vagy a gyökérpontot kettévágva új folytassuk a bovít gyökérpont keletkezik (ekkor növekszik a fa magassága). Körültekinto˝ módszer: Ha az aktuális pont bal vagy jobb testvére nem telített, akkor adjunk át egy adat-pointer párt, amivel az aktuális pont telítettségét megszüntetjük. Ha nem lehet átadni egyik testvérnek sem, akkor az egyszeru˝ módszer szerinti kettévágást végezzünk. 8.1.3.

Pesszimista stratégia

˝ oúton ˝ A bovít lefelé haladva minden telített pont telítettségét megszüntetjük, így a pm végponthoz érve az nem lesz telített, tehát beszúrhatjuk az új adatot. A telítettség megszüntetésére két módszer is kínálkozik. Egyszeru˝ módszer: Vágjuk ketté az aktuális pontot, és a keletkezo˝ (b, q) adat-pointer párt szúrjuk be az apába, amely már biztosan nem telített. Körültekinto˝ módszer: Ha az aktuális pont bal vagy jobb testvére nem telített, akkor adjunk át egy adat-pointer párt, amivel az aktuális pont telítettségét megszüntetjük. Ha nem lehet átadni egyik testvérnek sem, akkor az egyszeru˝ módszer szerinti kettévágást végezzünk.

8.2.

B-fa törlés

˝ pontjainak sorozata, tehát p1 a fa gyökere és Kulcs(pu ) = k. Legyen hpu+1 , . . . , pv i Legyen hp1 , . . . , pu i a k-kulcshoz vezeto˝ keresoút ˝ tartalmazó ponthoz vezeto˝ út. Eloször ˝ a k kulcs k1 követojét másoljuk át k helyére a k1 kulcsot (és a hozzá tartozó adatot is, ha azt is tároljuk a fában). A tényleges törlés a pv ponttól indul és célja az aktuális pontbeli hiány megszüntetése.

p1

p2

pu

k 0 p4 p5

0

0 pv

k1 4. ábra. Törléshez tartozó pontsorozat.

3

8.2.1.

Optimista stratégia

˝ ˝ A keresoúton visszafelé haladva, ha a törlést követoen az aktuális pont rangja t − 2-vé válik, akkor szüntessük meg az aktuális pontbeli hiányt. Ha az aktuális pont bal vagy jobb testvérének a rangja legalább t , akkor onnan egy adat-pointer pár átvételével ˝ mert egyik rangja t − 1, a a hiány megszunik. ˝ Egyébként vonjuk össze az aktuális pontot valamelyik testvérével (ez megteheto, másiké t − 2). Ekkor a hiány feljebb megy az apa pontba.

P

R

a

Q

b r

P

b

R

Q r a ˝ 5. ábra. Pótlás a bal testvértol.

P

a

R

Qq

P

R

Q

a q

6. ábra. Két pont összevonása.

8.2.2.

Pesszimista stratégia

˝ A keresoúton lefelé haladva minden minimális (azaz t − 1 rangú) pontot kipótolunk úgy, hogy a rangja legalább t legyen. A pótlást ˝ eloször testvérpontból próbáljuk elvégezni, ha ez nem megy, akkor összevonást végzünk. A pesszimista stratégia belso˝ megvalósítása.

Unit B_FA; Interface Const T=100; TT=2*T-1;{a B-fa rangja T} Type Kulcstip=???; AdatTip =???; BFa = ^BFaPont; 4

P

0 1 a1

i−1 i ... ai−1 ai

i+1 ai+1

R

0 1 ...

u−1 u bu−1 bu

0 1 c1

v cv

...

r0

ru

ru−1

P

0 1 a1

R

0 1 ...

q0

i−1 i ... ai−1 ai u−1 bu−1

qv

i+1 bu

m ... am

0 1 ai+1

...

r0

pi+2

v+1 Q cv ...

... pi−1

Q

...

... pi−1

m am

...

q0

ru

ru−1

qv

pi+2

7. ábra. B ALROL AT(i, P, Q, R). Feltétel: R = P↑.Fiu[i], Q = P↑.Fiu[i + 1], R↑.Rang = u > t − 1, Q↑.Rang = v < 2t − 1.

P

0 1 a1

i−1 i ... ai−1 ai

i+1 ai+1

R

0 1 ...

u−1 u bu−1 bu

0 1 c1

ru

0 1 a1

R

0 1 ...

q0

i−1 i ... ai−1 ai u bu

r0

qv

q1

i+1 c1

m ... am

u+1 0 1 ai+1 c2

v−1 ... cv

pi+2

Q

...

... pi−1

Q

...

r0

P

v cv

...

... pi−1

m am

...

ru

q0

q1

qv

pi+2

8. ábra. J OBBOL AT(i, P, Q, R). Feltétel: R = P↑.Fiu[i], Q = P↑.Fiu[i + 1], R↑.Rang = u < 2t − 1, Q↑.Rang = v > t − 1.

5

P

0 1 a1

. . . ai−1

Q

0 1 b1

. . . bt−1

i−1

i ai

t −1 t bt

i+1 ai+1 t +1 bt+1

Osszevon

q0

qt−1

qt

i−1

P

0 1 a1

. . . ai−1

Q

0 1 a1

...

qt+1

q0

pi+1

q2t−1

i+1 u+1 . . . a bt ai+1 u

i ai

t −1 0 1 bt−1 bt+1

t −1 . . . b2t−1

R

...

...

pi−1

2t − 1 b2t−1

... ...

...

pi−1

Vag

u . . . au

qt−1

qt

qt+1

q2t−1

pi+1

9. ábra. PVAG(i, P, Q, R). Feltétel: Q = P↑.Fiu[i], Q↑.Rang = 2t − 1. O SSZEVON(i, P, Q, R). Feltétel: P↑.Rang > t − 1, Q = P↑.Fiu[i], Q↑.Rang = t − 1, R↑.Rang = t − 1.

BFAPont=Record Level:Boolean; Rang :0..TT; Fiu : Array[0..TT] of BFa; Adat : Array[1..TT] of AdatTip; Kulcs: Array[1..TT] of KulcsTip; End; { M˝ uveletek Bayer-fákon :} Procedure Keres(F:BFa; K:KulcsTip; Var Van:Boolean; Var X:AdatTip); Procedure Bovit(Var F:BFa; K:Kulcstip; X:AdatTip); Procedure Torol(Var F:BFA; K:KulcsTip; Var Volt:Boolean); Implementation Function PKeres(P:BFa; K:Kulcstip):Word; {Output: Max(i):P^.Kulcs[i]<=K
Procedure Keres(F:BFa; K:KulcsTip; Var Van:Boolean; Var X:AdatTip); Var i:Word; Begin{Keres} Van:=False; If F=Nil Then Exit ; While True Do Begin i:=PKeres(F,K); If (i>0) And (F^.Kulcs[i]=K) Then Begin Van:=True; X:=F^.Adat[i]; Exit; End; If F^.Level Then Break; F:=F^.Fiu[i]; End{while}; End { Keres} ; Procedure JobbraLep(P:BFa; i:Word); Var j:Word; Begin For j:=P^.Rang+1 DownTo i+1 Do With P^ Do Begin Adat[j]:=Adat[j-1]; Kulcs[j]:=Kulcs[j-1]; Fiu[j]:=Fiu[j-1]; End; Inc(P^.Rang); End{JobbraLep}; Procedure BalraLep(P:BFa; i:Word); Var j:Word; Begin For j:=i To P^.Rang Do With P^ Do Begin Adat[j-1]:=Adat[j]; Kulcs[j-1]:=Kulcs[j]; Fiu[j-1]:=Fiu[j]; End; Dec(P^.Rang); End{BalraLep}; Procedure PVag(i:Word; P,Q:BFa; Var R:BFa); {Input:P^.Fiu[i]=Q; P^.Rang<2T-1;Q^.Rang=2T-1 Output: Q kettevagva Q-R pontokra } Var j:Word; Begin New(R); With R^ Do Begin Rang:=T-1; Level:=Q^.Level; Fiu[0]:=Q^.Fiu[T]; For j:=T+1 To TT Do Begin Adat[j-T]:=Q^.Adat[j]; Fiu[j-T]:=Q^.Fiu[j]; Kulcs[j-T]:=Q^.Kulcs[j]; End; End; 7

Q^.Rang:=T-1; JobbraLep(P,i+1); P^.Adat[i+1]:=Q^.Adat[T]; P^.Kulcs[i+1]:=Q^.Kulcs[T]; P^.Fiu[i+1]:=R; End{PVag}; Procedure JobbrolAt(i:Word;P,Q,R:BFa); { R=P^.Fiu[i], Q=P^.Fiu[i+1], R^.Rang>=T, Q^.Rang<2*T-1} { P i-edik fia (Q) avesz egy adatot jobb testveretol R-tol.} Var l:Word; Begin Inc(Q^.Rang); l:=(Q^.Rang); Q^.Adat[l]:=P^.Adat[i+1]; Q^.Kulcs[l]:=P^.Kulcs[i+1]; Q^.Fiu[l]:=R^.Fiu[0]; P^.Adat[i+1]:=R^.Adat[1]; P^.Kulcs[i+1]:=R^.Kulcs[1]; R^.Fiu[0]:=R^.Fiu[1]; BalraLep(R,2); End{JobbrolAt}; Procedure BalrolAt(i:Word;P,Q,R:BFa); { R=P^.Fiu[i-1], Q=P^.Fiu[i], R^.Rang>=T, Q^.Rang<2*T-1} { P i-edik fia (Q) atvesz egy adatot bal testveretol R-tol.} Begin JobbraLep(Q,1); Q^.Adat[1]:=P^.Adat[i]; Q^.Kulcs[1]:=P^.Kulcs[i]; Q^.Fiu[1]:=Q^.Fiu[0]; Q^.Fiu[0]:=R^.Fiu[R^.Rang]; P^.Adat[i]:=R^.Adat[R^.Rang]; P^.Kulcs[i]:=R^.Kulcs[R^.Rang]; Dec(R^.Rang); End{BalrolAt}; Procedure Osszevon(i:Word;P,Q,R:BFa); { Q=P^.Fiu[i-1], R=P^.Fiu[i], P^.Rang>=T, Q^.Rang=T-1, R^.Rang=T-1} { Osszevonja P i-1-edik es i-edik fiat } Var j:Word; Begin Q^.Adat[T]:=P^.Adat[i]; Q^.Kulcs[T]:=P^.Kulcs[i]; Q^.Fiu[T]:=R^.Fiu[0]; For j:=1 To T-1 Do Begin {atmasolas} Q^.Adat[T+j]:=R^.Adat[j]; Q^.Kulcs[T+j]:=R^.Kulcs[j]; Q^.Fiu[T+j]:=R^.Fiu[j]; End; Q^.Rang:=TT; BalraLep(P,i+1); Dispose(R); End{Osszevon}; Procedure Bovit(Var F:BFa; K : KulcsTip; X : AdatTip);

8

Var P,Q,R:BFA; i:Word; Begin {Bovit} If F=Nil Then Begin {a fa üres} New(F); With F^ Do Begin {új gyökér létesítése} Rang:=1; Level:=True; adat[1]:=X; Kulcs[1]:=K; End; Exit; End; Q:=F; If F^.Rang=TT Then Begin {a gyöker televan, n˝ o a fa magassága} New(F); {új gyökér létesítés} F^.Rang:=0; F^.Level:=False; F^.Fiu[0]:=Q; {az új gyökérpont 0. fia a régi gyökér} P:=F; i:=0; End; While True Do Begin {P->Q a keresési út két pontja} {ciklus invarians: Q=P^.Fiu[i] es P^.Rang<2*T-1 } If Q^.Rang=TT Then Begin {Q tele van} {1}if (i>0) And ((P^.Fiu[i-1]^.Rang=Q^.Kulcs[1])) Then Begin R:=P^.Fiu[i-1]; JobbrolAt(i-1,P,R,Q); {átadás a bal testvérnek} If K=P^.Kulcs[i+1] Then Q:=R;{kerút R-en át megy} {3}End Else Begin {kettévágás} PVag(i,P,Q,R); If K>=P^.Kulcs[i+1] Then Q:=R;{kerut az úuj ponton át megy} End; End{Q televolt}; i:=PKeres(Q,K); {K keresése a Q pontban} If Q^.Level Then Break; P:=Q; {továbblépés a keresési úton} Q:=Q^.Fiu[i]; End{while}; {Q a Kerut(F,K) vege, level es Q^.Rang<2T-1} JobbraLep(Q,i+1); {b˝ ovítés a Q levél pontban} Q^.Kulcs[i+1]:=K; Q^.Adat[i+1]:=X; {kulcs es adat beillesztése} End{Bovit}; Procedure Torol(Var F: BFA; K: KulcsTip; Var Volt:Boolean); Var P,Q,R,Pt:BFa; i,it: Word; Begin Volt:=False; If F=Nil Then Exit; P:=F; While True Do Begin {P^.Rang>=T, ha P<>F} i:=PKeres(P,K); {a K kulcs keresése a P pontban} 9

If (i>0) And (P^.Kulcs[i]=K) Then Begin{K megvan} Pt:=P; it:=i; Volt:=True; {feljegyezzük} End; If P^.Level Then Break; Q:=P^.Fiu[i]; If Q^.Rang=T-1 Then Begin If i>0 Then Begin R:=P^.Fiu[i-1]; If R^.Rang>=T Then BalrolAt(i,P,Q,R) Else Begin Osszevon(i,P,R,Q); Q:=R End End Else Begin R:=P^.Fiu[i+1]; If R^.Rang>=T Then JobbrolAt(i,P,Q,R) Else Osszevon(i+1,P,Q,R); End; End; P:=Q; End{while}; If Not Volt Then Exit; If i=0 Then i:=1; Pt^.Adat[it]:=P^.Adat[i]; Pt^.Kulcs[it]:=P^.Kulcs[i]; BalraLep(P,i+1); If F^.Rang=0 Then Begin P:=F; If F^.Level Then F:=Nil Else F:=F^.Fiu[0]; Dispose(P); End; End; {Torol} End {B_Fa}.

8.3.

{Q pótlásra szorul} {Q-nak van bal testvére}

{pótlás a bal testvérb˝ ol} {R is és Q is minimális}

{Q-nak csak jobb testvére van}

{pótlás a jobb testvérb˝ ol} {R is és Q is minimális}

{tovaább lefelé a keresési úton}

{átmasolás K helyére} {effektív törlés a levél pontban} {a fa magassága csökkent} {a fa üressé vált}

{a gyökerpontot töröljük}

B-fák külso˝ megvalósítása.

Adatszerkezet külso˝ megvalósítása azt jelenti, hogy minden cellát (pontot) adott file egy rekordja tárol. Tehát egy cellát a filebeli rekordsorszáma azonosít. B-fa külso˝ adatszerkezetként történo˝ megvalósítása esetén exogén ábrázolást célszeru˝ alkalmazni. Tehát külön fileban tároljuk a fa adatszerkezetet és külön fileban az adatokat. A fa (k, r) párokat tartalmaz, ahol r annak az adatelemnek a adatfilebeli rekordsorszáma, amelynek kulcsa k. A törlések miatt a fát tároló file egyes rekordjai használaton kívüliek lehetnek. A töredezettség csökkentése érdekében célszeru˝ ezeket egy láncba szervezni, így új pont létesítésekor ezek újra felhasználhatók lesznek. 8.3.1.

Muveletek ˝ a külso˝ megvalósításhoz

ION YIT(Var F:KBFa; BFaFNev:String ) A muvelet ˝ hozzárendeli az F fához a BFaFNev nevu˝ filet, amely a fa külso˝ megvalósítását ˝ ez nem létezett, akkor új filet hoz létre. Továbbá elokészíti ˝ tárolja. Ha a muvelet ˝ elott (inicializálja) a további muveletek ˝ által használt belso˝ adatszerkezetet.

10

0

1

2

3

m

4

10. ábra. Fa külso˝ tárolása során a szabad rekordokat láncba szervezzük. A file 0. rekordja tartalmazza a fa gyökerének rekordsorszámát és a szabad lánc fejét.

IOZ AR(Var F:KBFa); Lezárja az F fához tartozó filet és felszabadítja a lefoglalt belso˝ adatszerkezetet. IOU J P ONT(Var F:KBFa; Var P:BFa) A muvelet ˝ az F fához egy új pontot hoz létre. Az új pont memória helye a P ↑ .Belso, filebeli rekordsorszáma pedig P ↑ .Kulso lesz. IOPTOROL(Var F:KBFa; Var P:BFa); A muvelet ˝ törli az F fa P ↑ .Kulso pontját és felszabadítja a pont által lefoglalt P ↑ .Belso memóriát. IOB E(Var F:KBFa; r:KPointer; Var P:BFa); Beolvassa a memóriába az F fa r rekordsorszámú pontját. A P változó értéke annak a belso˝ pontnak a címe lesz, ahova az r pontot beolvasta. IOK I(Var F:KBFa; Var P:BFa); A muvelet ˝ kiírja az F fát tároló fileba a memóriában P helyen lévo˝ fa pontot. (A muvelet ˝ végrehajtása nem feltétlenül eredményez tényleges kiírást. Ha a pont nem változott a beolvasás óta, nem kell visszaírni.) IOM OD(Var P:BFa); A muvelet ˝ megjelöli, hogy a P pont módosult. A belso˝ algoritmus átírása külso˝ algoritmussá.

Bels˝ o m˝ uvelet: --------------------------New(P); -------------------------P^.Kulcs[i]:=K; -------------------------Q:=P^.Fiu[i]; -------------------------P:=Q; -------------------------Dispose(P);

A megfelel˝ o küls˝ o m˝ uvelet: --------------------------IOUjPont(F, P); -------------------------P^.Belso.Kulcs[i]:=K; IOMod(P); -------------------------IOKi(F, P); {ha P már nem aktív} IOBe(F, P^.Belso.Fiu[i], Q); -------------------------IOKi(F, P); {ha P már nem aktív} P:=Q; -------------------------IOPTorol(P);

A teljes megvalósítás megtalálható a kb_fa.pas állományban. Az I/O muveletek ˝ egyszeru˝ megvalósítás.

Procedure IOBe(Var F:KBFa; r:KPointer; Var P:BFa); Begin New(P); Seek(F.FaF, r); Read(F.FaF, P^.Belso); P^.Kulso:=r; P^.Modos:=False; End; Procedure IOKi(Var F:KBFa; Var P:BFa); Begin If P^.Modos Then Begin Seek(F.FaF, P^.Kulso); Write(F.FaF, P^.Belso); P^.Kulso:=r; 11

P^.Modos:=False;End; End; Dispose(P); End; Ekkor egyszerre legfeljebb 5 pont van a memóriában (törlés esetén), feltéve, hogy a gyökér mindig benn van. Azonban alkalmazás ˝ gyorsítás során ugyanarra a pontra többször történhet hivatkozás. Ezért, ha van elég memória több pont számára, akkor jelentos érheto˝ el, ha csak akkor írunk ki pontot, ha már egy új pont beolvasásához nincs szabad hely. Ekkor, ha van bent olyan pont, amely nem változott, akkor annak a helyébe olvasunk be, így nem kell kiírni. Továbbá, minden beolvasott ponthoz tartozzon egy Aktiv ˝ amely azt jelezze, hogy a pontot nem lehet felülírni a memóriában, mert még szükség van rá a muveletek mezo, ˝ során.

Puf

Kulso

Belso

Modos Aktiv

1 2 3 4 5 11. ábra. A fa memóriába beolvasott pontjait tároló adatszerkezet.

Unit KB_FaIO; Interface Const T=100; TT=2*T-1; {a B-fa rendje T} IOPufM=400; {az I/O pufferek száma} Type Kulcstip=Single; Adattip=Word; KPointer=Longint; AdatHiv =Longint; BFa = ^BFaPont; KBFAPont=Record Level :Boolean; Fok :0..TT; Fiu : Array[0..TT] of KPointer; Adat : Array[1..TT] of Adathiv; Kulcs : Array[1..TT] of KulcsTip; End; BFAPont=Record Belso :KBFaPont; Kulso :KPointer; Modos, Aktiv :Boolean; End; KBFa=Record FaF:File of KBFaPont; {a B-fa file} AF :File of Adattip; {az adatfile} G:BFa; {a B_fa gyökere (a memóriában)} IOPuf:Array[1..IOPufM] of BFa; FMeret, {a FaF file mérete } FSzabad:Longint {a szabad (törölt rekordok) láncának feje}; End; { Az IO interface m˝ uveletei:} Procedure IONyit(Var F:KBFa; BFaFNev:String ); 12

Procedure Procedure Procedure Procedure Procedure Procedure

IOZar(Var F:KBFa); IOBe(Var F:KBFa; r:KPointer; Var P:BFa); IOKi(Var F:KBFa; Var P:BFa); IOUjPont(Var F:KBFa; Var P:BFa); IOPTorol(Var F:KBFa; Var P:BFa); IOMod(Var P:BFa);

Procedure IONyit(Var F:KBFa; BFaFNev:String); Var r:Longint; i:Integer; Begin With F Do Begin For i:=1 To IOPufM Do Begin {pufferek letesitese, } New(IOPuf[i]); {inincializalasa} IOPuf[i]^.Modos:=False; IOPuf[i]^.Aktiv:=False; {Nem aktiv a puffer} IOPuf[i]^.kulso:=0; {ures a puffer} End; G:=IOPuf[1]; {helyfoglalas a gyokernek} Assign(FaF, BFaFNev); {a B-fat tarolo file megnyitasa} {$I-} Reset(FaF); {$I+} If IOResult<>0 Then Begin {a kulso B-fa meg nem letezett, ujat csinalunk} Rewrite(FaF); G^.Belso.Fok:=0; {ures fa, ures gyokerpont} G^.Kulso:=1; {a gyoker az 1. rekordba megy} G^.Modos:=True; FSzabad:=0; {nincs torolt rekord a fileban} FMeret:=2; {0.,1. rekord mar foglalt} End Else Begin {a kulso B-fa mar letezett} Read(FaF, G^.Belso); {a 0. admin rekord beolvasasa} r:=G^.Belso.Fiu[0]; {a fa gyokerenek rek.sorszama} FSzabad:=G^.Belso.Fiu[1];{a szabad rek. lancanak feje} Seek(FaF, r); {a gyoker beolvasasa} Read(FaF, G^.Belso); G^.Kulso:=r; FMeret:=FileSize(FaF); End; End{with}; F.G^.Aktiv:=True; End{IONyit}; Procedure IOZar(Var F:KBFa); Var i:Integer; Begin With F Do Begin For i:=1 To IOPufM Do If IOPuf[i]^.Modos Then Begin{a modosult rekordok kiirasa} Seek(FaF,IOPuf[i]^.Kulso); Write(FaF,IOPuf[i]^.Belso); End; G^.Belso.Fiu[0]:=G^.Kulso; {a gyoker rek beirasa az admin rekordba} G^.Belso.Fiu[1]:=FSzabad; {a szabad lanc fejenek beirasa } Seek(FaF,0); {a 0. admin rekord kiirasa} Write(FaF,G^.Belso); Close(FaF); 13

End{with}; End{IOZar}; Procedure IOBe(Var F:KBFa; r:KPointer; Var P:BFa); Var i,ri,ui,mi,fi:Integer; Begin ri:=0; ui:=0; mi:=0; fi:=0; With F Do Begin For i:=1 To IOPufM Do If IOPuf[i]<>G Then Begin If IOPuf[i]^.Kulso=r Then ri:=i Else If Not IOPuf[i]^.Aktiv Then Begin fi:=i; If IOPuf[i]^.Kulso=0 Then ui:=i; If Not IOPuf[i]^.Modos Then mi:=i; End; End; If ri>0 Then P:=IOPuf[ri] Else If ui>0 Then P:=IOPuf[ui] Else If mi>0 Then P:=IOPuf[mi] Else If fi>0 Then P:=IOPuf[fi] Else Begin WriteLn(’IOBe: Nincs eleg puffer’); Halt; End; If (P^.Kulso<>r) Then Begin If P^.Modos Then Begin{P modosult, ezert elobb ki kell irni} Seek(FaF, P^.Kulso); Write(FaF, P^.Belso); End; Seek(FaF, r); Read(FaF, P^.Belso); P^.Kulso:=r; P^.Modos:=False; End; End{with}; P^.Aktiv:=Ture; End{IOBe}; Procedure IOUjPont(Var F:KBFa; Var P:BFa); Var r:Longint; i,ui,mi,fi:Integer; Begin With F Do Begin ui:=0; mi:=0; fi:=0; For i:=1 To IOPufM Do {puffer keresese} If (IOPuf[i]<>G) And Not IOPuf[i]^.Aktiv Then Begin fi:=i; {nem aktiv puffer} If IOPuf[i]^.Kulso=0 Then {ures puffer} ui:=i; If Not IOPuf[i]^.Modos Then{nem modosult puffer} mi:=i; 14

End; If ui>0 Then {van-e ures puffer } P:=IOPuf[ui] Else If mi>0 Then {van-e nem modosult puffer} P:=IOPuf[mi] Else If fi>0 Then {csak modosult, de nem Aktiv puffer van} P:=IOPuf[fi] Else Begin WriteLn(’IOUj: Nincs eleg puffer’); Halt; End; If P^.Modos Then Begin Seek(FaF, P^.Kulso); Write(FaF, P^.Belso); End; If FSzabad<>0 Then Begin r:=FSzabad; Seek(FaF, r); Read(FaF, P^.Belso); FSzabad:=P^.Belso.Fiu[0]; End Else Begin r:=FMeret; Inc(FMeret); End; End{with}; P^.Kulso:=r; P^.Modos:=False; P^.Aktiv:=True; End{IOUjPont};

{P modosult, ezert elobb ki kell irni}

{van torolt rekord a faban} {a kovetkezo szabad rekord beolvasasa}

{nincs torolt rekord, a file bovul(a vegen)}

Procedure IOPTorol(Var F:KBFa; Var P:BFa); Begin With F Do Begin P^.Belso.Fiu[0]:=FSzabad; Seek(FaF, P^.Kulso); Write(FaF, P^.Belso); FSzabad:=P^.Kulso; End; P^.Kulso:=0; P^.Modos:=False; P^.Aktiv:=False; End{IOPTorol}; Procedure IOKi(Var F:KBFa; Var P:BFa); Begin If (P<>Nil) And (P<>F.G) Then P^.Aktiv:=False; End{IOKi}; Procedure IOMod(Var P:BFa); Begin P^.Modos:=True; End{IOMod}; End{KB_FaIO}.

15