B+ Tree je razširitev B Tree, ki omogoča učinkovite operacije vstavljanja, brisanja in iskanja.
V drevesu B lahko ključe in zapise shranite v notranjih in listnih vozliščih. Medtem ko je v drevesu B+ zapise (podatke) mogoče shraniti samo na listnih vozliščih, medtem ko lahko notranja vozlišča shranijo samo ključne vrednosti.
stikalo za tipkopis
Listna vozlišča drevesa B+ so med seboj povezana v obliki enojnih povezanih seznamov, da so iskalne poizvedbe učinkovitejše.
B+ Tree se uporablja za shranjevanje velike količine podatkov, ki jih ni mogoče shraniti v glavni pomnilnik. Zaradi dejstva, da je velikost glavnega pomnilnika vedno omejena, so notranja vozlišča (ključi za dostop do zapisov) drevesa B+ shranjena v glavnem pomnilniku, medtem ko so listna vozlišča shranjena v sekundarnem pomnilniku.
Notranja vozlišča drevesa B+ se pogosto imenujejo indeksna vozlišča. Drevo B+ reda 3 je prikazano na naslednji sliki.
Prednosti drevesa B+
- Zapise je mogoče pridobiti v enakem številu dostopov do diska.
- Višina drevesa ostane uravnotežena in nižja v primerjavi z drevesom B.
- Do podatkov, shranjenih v drevesu B+, lahko dostopamo zaporedno in neposredno.
- Ključi se uporabljajo za indeksiranje.
- Hitrejše iskalne poizvedbe, saj so podatki shranjeni samo na listnih vozliščih.
B drevo VS B+ drevo
| SN | B Drevo | B+ Drevo |
|---|---|---|
| 1 | Iskalnih ključev ni mogoče večkrat shraniti. | Prisotni so lahko odvečni iskalni ključi. |
| 2 | Podatki so lahko shranjeni v listnih vozliščih in notranjih vozliščih | Podatke je mogoče shraniti samo na listnih vozliščih. |
| 3 | Iskanje nekaterih podatkov je počasnejši proces, saj je podatke mogoče najti na notranjih vozliščih in tudi na listnih vozliščih. | Iskanje je sorazmerno hitrejše, saj je podatke mogoče najti le na listnih vozliščih. |
| 4 | Brisanje notranjih vozlišč je tako zapleteno in dolgotrajno. | Brisanje nikoli ne bo zapleten postopek, saj bo element vedno izbrisan iz listnih vozlišč. |
| 5 | Listnih vozlišč ni mogoče povezati skupaj. | Listna vozlišča so med seboj povezana, da so iskalne operacije učinkovitejše. |
Vstavljanje v drevo B+
Korak 1: Vstavite novo vozlišče kot listno vozlišče
2. korak: Če list nima potrebnega prostora, razdelite vozlišče in kopirajte srednje vozlišče v naslednje indeksno vozlišče.
3. korak: Če vozlišče indeksa nima potrebnega prostora, razdelite vozlišče in kopirajte srednji element na naslednjo stran indeksa.
primer:
Vstavite vrednost 195 v drevo B+ reda 5, prikazano na naslednji sliki.
195 bo vstavljen v desno poddrevo 120 za 190. Vstavite ga na želeno mesto.
Vozlišče vsebuje več kot največje število elementov, tj. 4, zato ga razdelite in postavite mediano vozlišče do nadrejenega.
Indeksno vozlišče zdaj vsebuje 6 otrok in 5 ključev, kar krši lastnosti drevesa B+, zato ga moramo razdeliti, kot je prikazano spodaj.
Izbris v drevesu B+
Korak 1: Izbrišite ključ in podatke iz listov.
2. korak: če listno vozlišče vsebuje manj kot minimalno število elementov, združite vozlišče navzdol z bratom in izbrišite ključ med njima.
3. korak: če indeksno vozlišče vsebuje manj kot minimalno število elementov, združite vozlišče s sorodnikom in premaknite navzdol po ključu med njima.
Primer
Izbrišite ključ 200 iz drevesa B+, prikazanega na naslednji sliki.
'kakšna je razlika med levom in tigrom'
200 je prisoten v desnem poddrevesu 190, za 195. ga izbrišite.
Združite obe vozlišči z uporabo 195, 190, 154 in 129.
Zdaj je element 120 edini element, prisoten v vozlišču, ki krši lastnosti drevesa B+. Zato ga moramo združiti z uporabo 60, 78, 108 in 120.
Zdaj se bo višina drevesa B+ zmanjšala za 1.
