B+ Tree on B-puun laajennus, joka mahdollistaa tehokkaat lisäys-, poisto- ja hakutoiminnot.
B-puussa avaimet ja tietueet voidaan tallentaa sekä sisäisiin että lehtisolmuihin. B+-puussa tietueita (dataa) voidaan tallentaa vain lehtisolmuihin, kun taas sisäiset solmut voivat tallentaa vain avainarvot.
10 prosenttia 60:stä
B+-puun lehtisolmut on linkitetty yhteen linkitettyjen luetteloiden muodossa hakukyselyiden tehostamiseksi.
B+ Puuta käytetään tallentamaan suuri määrä tietoa, jota ei voida tallentaa päämuistiin. Koska päämuistin koko on aina rajoitettu, B+-puun sisäiset solmut (tietueiden pääsyavaimet) tallennetaan päämuistiin, kun taas lehtisolmut tallennetaan toissijaiseen muistiin.
B+-puun sisäisiä solmuja kutsutaan usein indeksisolmuiksi. Seuraavassa kuvassa on luokkaa 3 oleva B+-puu.
B+ Treen edut
- Tietueita voidaan hakea yhtä monta kertaa levylle.
- Puun korkeus pysyy tasapainoisena ja vähemmän B-puuhun verrattuna.
- Voimme käyttää B+-puuhun tallennettuja tietoja sekä peräkkäin että suoraan.
- Avaimia käytetään indeksointiin.
- Nopeammat hakukyselyt, koska tiedot tallennetaan vain lehtien solmuihin.
B puu VS B+ puu
| SN | B Puu | B+ puu |
|---|---|---|
| 1 | Hakuavaimia ei voi tallentaa toistuvasti. | Redundantteja hakuavaimia voi olla läsnä. |
| 2 | Tietoja voidaan tallentaa lehtisolmuihin sekä sisäisiin solmuihin | Tietoja voidaan tallentaa vain lehtien solmuihin. |
| 3 | Tietyn tiedon etsiminen on hitaampaa, koska tietoja löytyy sekä sisäisistä solmuista että lehtien solmuista. | Haku on suhteellisen nopeampaa, koska tiedot löytyvät vain lehtien solmuista. |
| 4 | Sisäisten solmujen poistaminen on niin monimutkaista ja aikaa vievää. | Poistaminen ei koskaan ole kompleksinen prosessi, koska elementti poistetaan aina lehtien solmuista. |
| 5 | Lehtisolmuja ei voi yhdistää toisiinsa. | Lehtisolmut on linkitetty toisiinsa tehostaakseen hakutoimintoja. |
Lisäys B+-puuhun
Vaihe 1: Lisää uusi solmu lehtisolmuksi
Vaihe 2: Jos lehdellä ei ole tarvittavaa tilaa, jaa solmu ja kopioi keskisolmu seuraavaan indeksisolmuun.
Vaihe 3: Jos indeksisolmussa ei ole tarvittavaa tilaa, jaa solmu ja kopioi keskimmäinen elementti seuraavalle hakemistosivulle.
Esimerkki:
Syötä arvo 195 seuraavan kuvan 5. kertaluvun B+-puuhun.
195 lisätään oikeanpuoleiseen alipuuhun 120 luvun 190 jälkeen. Lisää se haluttuun kohtaan.
Solmu sisältää enemmän kuin enimmäismäärän elementtejä eli 4, joten jaa se ja sijoita mediaanisolmu yläpäähän.
Nyt indeksisolmu sisältää 6 lasta ja 5 avainta, mikä rikkoo B+-puun ominaisuuksia, joten meidän on jaettava se seuraavasti.
Poisto B+-puussa
Vaihe 1: Poista avain ja tiedot lehdistä.
Vaihe 2: jos lehtisolmu sisältää vähemmän kuin vähimmäismäärä elementtejä, yhdistä solmu sen sisaruksen kanssa ja poista avain niiden välistä.
Vaihe 3: jos indeksisolmu sisältää vähemmän kuin vähimmäismäärä elementtejä, yhdistä solmu sisarukseen ja siirrä avain alas niiden välillä.
Esimerkki
Poista avain 200 seuraavassa kuvassa näkyvästä B+-puusta.
foreach java
200 on oikeanpuoleisessa alipuussa 190, 195:n jälkeen. Poista se.
Yhdistä kaksi solmua käyttämällä numeroita 195, 190, 154 ja 129.
Nyt elementti 120 on solmussa oleva yksittäinen elementti, joka rikkoo B+-puun ominaisuuksia. Siksi meidän on yhdistettävä se käyttämällä numeroita 60, 78, 108 ja 120.
Nyt B+ puun korkeutta pienennetään yhdellä.
