Programozás | Programozás-elmélet » Fábián Zoltán - A B-fa adatszerkezete és algoritmusa

8. B-fák A bináris fa hátrányai Ha rendezett adatokat feszünk fel, akkor egy része elfajulhat, a keresés lelassul Ha sok adatot szeretnénk tárolni a fában, lehetséges, hogy nem fér el a memóriában. ✁✂✂✄☎ ✆✝✞✝✟✝✠ ✂✡✠✝ ☛☞☎✄✆✠✌✍ ✎ ✆✝✞✝✟☎✏✆ ✄✆✑✎✒☞✒ ✒✄✂✂✎✆ ✆✎✒✒abb A B-fa (Bayer, 1972) A B-fákban a csúcsoknak sok gyerekük lehet, akár több ezer is. A B-✓☞✂ ✝✆☞✔✎✟☞✒✌ ☛✡✠✕✝✟✏✖✝ sokkal nagyobb, mint a bináris fáké, ezért magasságuk lényegesen kisebb. Ha a B-fa egy X csúcsa N[X] kulcsot tartalmaz, akkor az X-nek N[X]+1 gyereke van. Ha a Bfákban egy kulcsot keresünk, akkor (N[X]+1)-féle választásunk lehet, mert a keresett kulcsot N[X] kulccsal hasonlítjuk össze. A B-✓✎ ✞✎✔✎✒✒☞✔✎ ✎ ✗✝✠✠✝ ✆✡✑✏ ✘✒✙✘✒✄✂ ✒✟☞✞☞✠✎✂ ✠✚✑✝✆✡✒✝✂✄☎ ✘✒✎✂

✎ ✘✒✙✘✒✒✟☞✠✄✂ ✆✄✔✎☎✌☛✞✛✒☞✑✎✆ ✠✏✜ Tulajdonságai A kitöltöttségi faktor (a redundáns adatok száma) 50%-nál jobb a B-fa esetében Egy lemez-szektorba bele kell férjen a fa egy mezejének tartalma, így pl. a BlockRead eljárással gyors adatkezelés valósul meg Minden lap legfeljebb 2n tételt tartalmaz (n jelenti a B-fa rendjét) Minden lapon -a gyökérlapot kivéve- legalább n tétel van Egy lap lehet levél (utód nélküli) vagy n+1 utóddal rendelkezik, ahol n a kulcsok száma Minden levél-lap ugyanazon a szinten helyezkedik el 19.3 ábra Egy 2 magasságú B-fa, amelynek több, mint egymilliárd kulcsa van Mindegyik ✗✝✆✒✏ ✘✒✙✘✒✠✎✂ ✡✒ ✆✝✑✡✆✠✝✂ ✢✣✣✣ ✂✛✆✘✒✎ ✑✎✠✜ ✤✟ ✢ ✞✡✆✕✒✡✔✗✝✠ ✢✣✣✢ ✘✒✙✘✒ ✑✎✠✥ ✎ ✦ ✞✡✆✕✒✡✔✗✝✠ több, mint egymillió levél található. Minden x csúcsban

n[x], azaz az x-✗✝✠ ✆✝✑✏ ✂✛✆✘✒✄✂ ✒✟☞✞✎ is látható. Beszúrás A B-fa t minimális fokszáma 3, ezért egy csúcsnak legfeljebb 5 kulcsa lehet. Azokat a csúcsokat, amelyeket a beszúrás alatt módosítottunk, halványabban sötétítettük. (a) A példában ✁✂✄✂☎✆✝ ✞✟ ✠✂✁✡✂☛☞ ✌✆✆✟☎✍☛✟✎ ✏✑✒ ✓ ✔ ✑✂ ✁✕✄✌ ✌✖✟✠ ✟✁ ✂✄✂✡✗✘✖✙✂✚ ✂✁ ✂✛✙ ✂✛✙ ✁✂✄✜ ✂ ✂☛✢ ✂✛✙ ✆✂✣✘✆✑✂ ✠✂✆✆✂☛☛ ✑✂ ✁✕✄✖☞✎ ✏✤✒ ✓✁ ✂✆✝✁✝ ✞✌✑✟ ✂✛✙ ✥ ✠✦✆✤ ✍☛ ✁✕✄☛✦✖✠ ✑✂✎ ✓✁ ✧★✩✪✫ ✤ ✕✤ ✠✘☛ részre bomlott, az RS és az UV csúcsokra, a T a gyökércsúcsba ment, és a Q a baloldali új csúcsba (RS-be) került. (d) Az ✂✆✝✁✝ ✞✌✑✟ ✂✛✙ ✬ ✠✦✆✤ ✍☛ ✁✕✄☛✦✖✠ ✑✂✎ ✓

✛✙✭✠✘✄✤ ✕✤ ✍☛ ✞✂✆ ✠✂✆✆✂☛☛ bontani, mivel már telített volt, így a B-✞✟ ✗✟✛✟ ✌✛✟ ✂✛✛✙✂✆ ✖✝☛☛✎ ✮✁✦☛✌✖ ✟✁ ✬ ✠✦✆✤ ✍☛ ✟ ✯✰-t ☛✟✄☛✟✆✗✟✁✱ ✆✂✣✘✆✑✂ ✁✕✄☛✦✠ ✑✂✎ ✏✂✒ ✓✁ ✂✆✝✁✝ ✞✌✑✟ ✟✁ ✲ ✠✦✆✤ ✍☛ ✁✕✄☛✦✠ ✑✂✎ ✓✁ ✓✔✳✴✮ ✤ ✕✤ ✍☛ szétvágtuk, és ezután az F kulcsot a jobboldali új csúcsba (DE-be) szúrtuk be. Törlés A B- ✁ ✂✄☎✄✂✆✝✄✞ ✟✠✞✡✆✂✁ ☛ ☞ ✌✍ ✎✏✑ ✁ ✒✞✓✒✞✟✠☎✁✠ ✔✁ ✏✑✕✠✖✗✒✞✓✒✞✟☛ ✠✄✘✖✘✙✚ ☎✙✂ ✝✙✛✙☛ ✠✙☛☛✜☎✖✝ kevesebb kulcsa. A módosított csúcsokat kevésbé sötétítettük be (a) A 197(e) ábrán látható B✁✢ ✔✣✚ ✤✡ ✥ ☛✕✗✝✖✞✙✢ ✦✡ ✁✡

✝✙✞✙☛✧ ✙✏✑ ✙✏✑✞✡✙✗★ ☛✕✗✝✖✞ ✁ ✝✙✘✖✝✣✜✝✢ ✔✒✚ ✤✡ ✩ ☛✕✗✝✖✞✙✢ ✦✡ ✁ ✪✁✢ ✙✞✙☛✧ L-☛✍ ✁✂✄ ✁✡ ✩ ✂✙✏✙✝✜✡✜✫✙✍ ✙✝✘✄✞✞✡✬✠ ✁✡ ✩ ✛✙✝✑✖✗✙✢ ✔✭✚ ✤ ✮ ☛✕✗✝✖✞✙✢ ✦✡ ✁ ✪✒✢ ✙✞✙☛✧ ✤ ✮-t levisszük, és elkészítjük a DEGJK csúcsot, majd a G-☛ ✠✄☛✕✗✕✝✫✬✠ ✙✣✣✜✝ ✁ ✒✞✓✒✞✣✯✝✢ ✔✙✚ ✤ ✰ törlése. Ez a 3b eset: a rekurziót nem lehet levinni a CL csúcsba, mivel annak csak 2 kulcsa van, ezért a P-t kell levinni, egyesíteni a CL-t és a TX -et a CLPTX csúcsba; ezután a D ☛✕✗✕✝✛✙☛✜ ✁ ✝✙✘✖✝✣✜✝ ✔✱✢ eset). (e) A (d) után a fa gyökércsúcsát töröljük, ezzel a fa magassága eggyel csökken. (f) A B törlése Ez a 3a eset: A C elfoglalja a B helyét, E pedig a C

pozícióját 1. Ha a k kulcs az x csúcsban van, és x egy levél, akkor az x kulcsot töröljük az x-✣✜✝✢ ✪✢ ✲✁ ✁ ✠ ✠✳✝✒✞ ✁✡ ✴ ✒✞✓✒✞✣✁☎ ✘✁☎✍ ✖✞ ✴ ✁ ✁ ✙✏✑ ✣✙✝✞✜ ✒✞✓✒✞✁✍ ✁✠✠✟✗ ✁ ✠✕✘✙☛✠✙✡✜✠✙☛ ✠✙✝✝ végrehajtani: a. Ha y az x-nek gyereke, y tartalmaz egy k-☛ ✂✙✏✙✝✜✡✜ ✠✳✝✒✞✟☛✍ ✖✞ ✑-nak legalább t kulcsa van, akkor keressük meg az y gyökércsúcsú részfában a k-☛ ✠✕✡✘✙☛✝✙☎✬✝ ✂✙✏✙✝✜✡✜ ✠✵ kulcsot. Rekurzívan töröljük k-t, és helyettesítsük k-t k -vel az x-ben (A k ✂✙✏✠✙✗✙✞✖✞✖✛✙✡ ✖✞ ☛✕✗✝✖✞✖✛✙✡ ✙✏✑ ✝✙ ✙✝✖ ✛✁✝✁✭✯ ✂✙☎✙☛ ✙✝✙✏✙☎✭✜✢✚ b. Szimmetrikusan, ha a z gyerek következik az x-beli k után, és z-nek legalább t kulcsa van, akkor keressük meg

a z gyökércsúcsú részfában a k-☛ ✠✕✡✘✙☛✝✙☎✬✝ ✠✕✘✙☛✜ ✠✵ ✠✳✝✒✞✟☛✢ Rekurzívan töröljük k -t, és helyettesítsük k -t k -vel az x -ben. (A k megkereséséhez és ☛✕✗✝✖✞✖✛✙✡ ✙✏✑ ✝✙ ✙✝✖ ✛✁✝✁✭✯ ✂✙☎✙☛ ✙✝✙✏✙☎✭✜✢✚ c. Egyébként, ha mind y -nak, mind z -nek csak t - 1 kulcsa van, akkor egyesítsük k-t és a z kulcsait y-ba, úgy, hogy x-✣✜✝ ☛✕✗✕✝✫✬✠ ✁ ✠-t és a z-re mutató pointert. Ekkor y -nak 2t - 1 kulcsa lesz. Ezután szabadítsuk fel z -t és rekurzívan töröljük k -t az y -ból 3. Ha a k ✠✳✝✒✞ ☎✄☎✒✞ ✣✙☎☎✙ ✁✡ ✴ ✣✙✝✞✜ ✒✞✓✒✞✣✁☎✍ ✁✠✠✟✗ ✛✁☛✆✗✟✡✡✳✠ ✂✙✏ ✁☎☎✁✠ ✁ ✂✙✏ ✙✝✙✝✜ részfának a ci[x] gyökércsúcsát, amelyben a k biztosan benne van, ha egyáltalán benne van k a fában. Ha ci[x] -nek

csak t - 1 kulcsa van, akkor hajtsuk végre a 3a vagy a 3b pontban leírtakat, mivel biztosítani kell azt, hogy annak a csúcsnak, amelyre lelépünk, legalább t kulcsa ✝✙✏✑✙☎✢ ✦✡✳☛✆☎ ✁ ✂★✘✙✝✙☛✙☛ ✁✡ ✴ ✂✙✏ ✙✝✙✝✜ ✏✑✙✗✙✠✖☎ ✗✙✠✳✗✡✄✯✘✁✝ befejezhetjük. a. Ha ci [x] -nek csak t- 1 kulcsa van, de van egy testvére, melynek t kulcsa van, akkor vigyünk le ci[x]-be egy kulcsot x-✣✜✝✍ ✁ ✒✄✶✴✷ ✠✕✡✘✙☛✝✙☎ ✣✁✝✟✝✭✁✝✄ ✘✁✏✑ ✫✟✣✣✟✝✭✁✝✄ ☛✙✞☛✘✖✗✖☛✜✝ ✸✙✭✄✏ ✘✄✏✑✬☎✠ ✙✝ ✙✏✑ ✠✳✝✒✞✟☛ ✴-✣✙✍ ✖✞ ✘✄✏✑✬✠ ✆☛ ✁ ✂✙✏ ✙✝✙✝✜ ✏✑✙✗✙✠✙☛ ✁ ☛✙✞☛✘✖✗☛✜✝ ✁ ✒✄ ✶✴✷ -be. b. Ha c2 [x] -nek, és a ci [x] minden testvérének t - 1 kulcsa van, akkor egyesítsük ci -t az egyik

testvérével, és utána vigyünk le egy kulcsot x -✣✜✝ ✙✣✣✙ ✁✡ ✙✏✑✙✞✎☛✙☛☛ ✒✞✓✒✞✣✁✍ ✙✡ ✁ ✠✳✝✒✞ ✝✙✞✡ ✁✡ ✙✏✑✙✞✎☛✙☛☛ ✒✞✓✒✞ ✠✕✡✖✸✞✜ ✠✳✝✒✞✁✢ Mivel egy B- ✆✣✁☎ ✁ ✠✳✝✒✞✟✠ ☛✕✣✣✞✖✏✙ ✝✙✘✙✝✙✠✣✙☎ ✘✁☎✍ ✘✁✝✯✞✡✎☎★✍ ✛✟✏✑ ✁ ☛✕✗✝✖✞ ✂★✘✙✝✙☛✙✠ ☎✁✏✑ ✗✖✞✡✙ ✝✙✘✙✝✙✠✣✜✝ ☛✕✗✕✝ ✠✳✝✒✞✟☛✢ ✦✠✠✟✗ ✁ B-FábóL-TÖRÖL eljárás a fában lefelé haladó, ✙✏✑✂✙☎✙☛✙✞✍ ✘✄✞✞✡✁✝✖✸✖✞ ☎✖✝✠✬✝✄ ✸✗✟✒✙✭✓✗✁✢ ✤✡✟☎✣✁☎✍ ✛✁ ✙✏✑ ✣✙✝✞✜ ✒✞✓✒✞✣✯✝ ✠✙✝✝ ✙✏✑ ✠✳✝✒✞✟☛ törölni, az eljárás egy lefelé haladó menetben megy le a fában, de

utána visszatér abba a ✒✞✓✒✞✣✁✍ ✁✛✟☎☎✁☎ ✙✏✑ ✠✳✝✒✞✟☛ ☛✕✗✕✝☛✍ ✁✡✖✗☛✍ ✛✟✏✑ ✙✡☛ ✁ ✂✙✏✙✝✜✡✜ ✘✁✏✑ ✠✕✘✙☛✜ ✠✳✝✒✒✞✁✝ helyettesítse (2a. és 2b eset) ✹✆✗ ✙✡ ✁✡ ✙✝✫✆✗✆✞ ✣✟☎✑✟✝✳✝☛☎✁✠ ☛★☎✄✠✍ ✙✏✑ ✛ ✂✁✏✁✞✞✆✏✓ ✹- ✆✗✁ ✁ ✝✙✂✙✡✂★✘✙✝✙☛✙✠ ✞✡✆✂✁ ✺✔✛✚✍ mivel csak 0(1) LEMEZR✻✼-OLVAS és LEMEZRE-✽✾ ✂★✘✙✝✙☛✙☛ ✛✁✫☛ ✗✙✠✳✗✡✎✘ ✛✎✘✆✞✁✄ ✠✕✡✕☛☛✢ ✤ ✞✡✬✠✞✖✏✙✞ ✠✕✡✸✟☎☛✄ ✙✏✑✞✖✏ ✄✭✜ O(th) = O(t logt n). ✘✖✏✗✙ ✁✡ ✙✝✫✆✗✆✞ 9. Egy B-fa teljes algoritmusa program Bfa; const N=2, NN=4; //NN jelentése: 2N type REF=^LAP; TETEL= RECORD KULCS: integer; szam: integer; {a

fájlbeli adatok helye} end; LAP=RECORD E: Array[1.NN] of TETEL; {a tétel-elemeket tartalmazza} end; var gyoker, A: REF; x : integer; h : boolean; {azt mutatja meg, hogy meg kell-e osztani a lapot} procedure Keres(x: integer, A: REF; var H: boolean, var T: TETEL); var K,L,R: integer; Q : REF; U : TETEL; procedure Betesz; var I: integer; B: REF; begin {Az U elemet beszúrja az A^.E[R] jobb oldalára} with A^ do begin If M<NN then begin {ha megtelik a lap, kettéosztjuk,} H:=false; {ekkor NN elem van az aktuális lapon} for i:=1 downto R+2 do begin E[i]:=E[i-1]; end; E[R+1]:=U; end; else begin new(B); If R<=N then {R tárolja, hova kell berakni az elemeket} begin If R=N then V:=U {ha R az utolsó, felküldjük} begin V:=E[N]; for i:=N downto R+2 do begin E[i]:=E[i-1]; end; E[R+1]:=U; end; jük} for i:=1 to N do {Abegin {a B lapra} B^.E[i]:=A^E[i+n]; end; end else {U beszúrása a jobb lapra} begin R:=R-N; V:=E[N+1]; {helycsinálás} for i:=1 to R-1 do begin

B^.E[i]:=A^E[i+N+1]; end; B^.E[R]:=U; for i:=R+1 to N do begin B^.E[i]:=A^E[i+N]; end; end; M:=N; {az aktuális lapra ennyi elem kerül} B^.M:=N; {aktuális elemszám} V.P:=B; end; end; BEGIN {keresi az x kulcsot a B lapon} If A=nil then begin H:=true; with U^do begin kulcs:=x; szam:=1; p:=nil; end; end else begin with A^ do begin L:=1; R:=M; repeat K:=(L+R) div 2; If x<=E[k].kulcs then R := k-1; If x>E[k].kulcs then R := k+1; until R<K If L-R<1 then {megvan a keresett elem} begin inc(E[k],szam); {számoljuk, hogy hányszor keresünk egy elemet} H:=false; end else begin else Q:=E[R].P; Keres(x,Q,H,U); If H=true then Betesz; end; end; end; END; procedure Torol(x: integer; A: REF; var H: boolean); var I,K,LR : integer; Q : REF; procedure Kislap(C,A:REF; s: integer; var H: boolean); var {C - ahonnan hívtuk, A- az alulcsordult lap} B : REF; I,K,MB,MC : integer; begin MC := C^.M; H := true; A^.M := N-1; If s<MC then begin s := s+1; B := C^.E[s]P; MB := B^.M; K :=

(MB-N+1) div 2; A^.E[N] := C^E[s]; A^.E[N]P := B^P0; If k>0 then {----------------------} begin for i:=1 to k-1 do begin A^.E[i+N]:=B^E[i]; end; C^.E[s]:=B^E[k]; C^.E[s]P:=B; B^.P0:=B^E[k]P; MB:=MB-k; for i:=1 to MB do begin B^.E[i]:=B^E[i+k]; end; B^.M:=MB; A^.M:=M-1+k; H:=false; end else {nincs átmozgatható tétel} begin for i:=1 to N do begin A^.E[i+N]:=B^E[i]; end; for i:=s to MC-1 do begin C^.E[i]:=C^E[i+1]; end; A^.M:=NN; C^.M:=MC-1; Dispose(B); end; else begin If s=1 then B:=C^.P0 else B:=C^.E[s-1]P; MB:=B^.M+1; K:=(MB-N) div 2; If k>0 then begin {k tételt átmásolunk Bfor i:= N+1 downto 1 do begin A^.E[i+k]:=A^E[i]; end; A^.E[k]:=C^E[s]; A^.E[k]P:=A^P0; MB:=MB-k; for i:=k-1 downto 1 do begin A^.E[i]:=B^E[i+MB]; end; A^.P0:=B^E[MB]; C^.E[s]:=B^E[MB]; C^.E[s]P:=A; B^.M:=MB-1; A^.M:=N-1+k; M:=false; end else {A és B összeolvasztása} begin B^.E[MB]:=C^E[s]; B^.E[MB]P:=A^P0; for i:=1 to N-1 do begin B^.E[i+MB]:=A^E[i]; end; B^.M:=NN; C^.M:=MC-1; dispose(A); end;

-ra} end; end; procedure Tor(P: REF; var H: boolean); var Q: REF; H: Boolean; {szükség van-e a fa magasságának csökkentésére?} begin with P^ do begin Q:=E[M].P; If Q<>nil then begin Tor(Q,H); If (H=true) then begin Kislap(P,Q,M,H); end else begin P^.E[M]P:=A^E[k]P; A^.E[k]:=P^E[M]; M:=M-1; {nem lesz kihasználva 50%-ban a lap} H:=M<N; {alulcsordulás} end; end; end; end; BEGIN {Torol} If A=nil then begin Kiir(Az elem nincs a fán!) H:=false; end else begin L:=1; R:=M; repeat k:=(L+R) div 2; If x<=E[k].kulcs then R:=K-1; If x>=E[k].kulcs then L:=K+1; until L>R; If R=0 then Q:=P0 else Q:=E[R].P; If ((L-R)>1) then {*} begin If Q=nil then {-} begin M:=M-1; H:=M<N; for i=k to M do begin E[i]:=E[i+1]; end; end else {-} begin Tor(Q,H); If H then Kislap(A,Q,R,H); end else {*} begin Torol(X,Q,H); If H then Kislap(A,Q,R,H); end; end; end; END;