2. gyakorlat

B+ fa

Egy csúcs tartalmazhatna több értéket? Igen!

B+ fában az a jó, hogy nincs hozzá struktogram ezért nem kell megtanulni az egészet.

B+ fában az a rossz, hogy nincsen struktogram, ezért nehezen lehet átlátni az egészet.

• \(d\): hány pointert szeretnénk eltárolni
  • \(d-1\) kulcs
• Minden csúcsban több kulcs
• MINDEN levél azonos szinten van
• MINDEN adat a levél szinten helyezkedik el
  • A többi Node csak "utcatábla", mutatja hogy merre kell menni.

Minden kulcstól balra, ami nála \(<\), jobbra ami \(\geq\).

Minden csúcs bármelyik kulcsa \(\leq\), mint a csúcstól balra lévő kulcs, és \(<\), mint a csúcstól jobbra lévő kulcs.

• Minden csúcsnak legalább \(\left\lfloor \frac d2 \right\rfloor\) gyereke van (kivéve a gyökérnek).
• Minden kulcs megjelenik valamelyik levélben, szig.mon.növ sorrendben

Beszúrás

• Van üres hely, és nem szerepel a kulcsok között
  • Megkeressük a levelet, és a kulcsok közé beszúrjuk, a szig.mon-t megtartva
• Nem szerepel a kulcsok között, de nincs üres hely
  • Ketté vágjuk a levelet
  • A bal és jobb fél két új csúcsba kerül
  • Szülőbe kell új kulcs
  • A kettévágásnál kapott jobb oldal legkisebb csúcsát beszúrjuk a szülőbe
  • A szülőbe beszúrást rekurzívan végezzük
  • Ha a gyökér is tele van, akkor új szülőket csinálunk
    • Ekkor az új gyökérnek csak 1 kulcsa van, itt sérülhet csak meg a \(\left\lfloor \frac d2 \right\rfloor\) követelmény

Törlés

• Ha törlés után megmarad a \(\left\lfloor\frac d2\right\rfloor\)
  • Csak kivesszük a kulcsot
• Ha nem marad meg
  • A levelünktől jobbra lévő levéltől "kölcsönkéri" a legkisebb gyereket
  • 1-3 \(\Rightarrow\) 2-2 (balance-wise)
  • A szülőben az új osztási pontnak megfelelően ki kell cserélni a kulcsot