Ennen ymmärtämistä B puu ja B+ puu eroista, meidän pitäisi tuntea B-puu ja B+-puu erikseen.
Mikä on B-puu?
B puu on itsetasapainottava puu, ja se on m-suuntainen puu, jossa m määrittelee puun järjestyksen. Btree on yleistys aiheesta Binäärihakupuu jossa solmulla voi olla enemmän kuin yksi avain ja enemmän kuin kaksi alalaista riippuen arvosta m . B-puussa tiedot määritellään järjestykseen siten, että vasemmassa alipuussa on pienemmät arvot ja oikeassa alipuussa korkeammat arvot.
vertaa merkkijonoa javaa
B-puun ominaisuudet
Seuraavat ovat B-puun ominaisuudet:
- B-puussa kaikkien lehtien solmujen tulee olla samalla tasolla, kun taas binääripuussa lehtisolmut voivat olla eri tasoilla.
Ymmärretään tämä ominaisuus esimerkin avulla.
Yllä olevassa puussa kaikki lehtisolmut eivät ole samalla tasolla, mutta niillä on kaksi lasta. Siksi voimme sanoa, että yllä oleva puu on a binääripuu mutta ei B-puuta.
- Jos B-puun kertaluku on m, jokaisella solmulla voi olla enintään m Minimilapsien tapauksessa lehtisolmuissa on nolla lasta, juurisolmulla on kaksi lasta ja sisäisillä solmuilla on yläraja m/2.
- Jokaisella solmulla voi olla maksimiavaimet (m-1). Jos esimerkiksi m:n arvo on 5, avainten maksimiarvo on 4.
- Juurisolmulla on vähintään yksi avain, kun taas kaikilla muilla solmuilla juurisolmua lukuun ottamatta on (katto m/2 miinus - 1) minimiavaimet.
- Jos suoritamme lisäyksen B-puuhun, solmu lisätään aina lehtisolmuun.
Oletetaan, että haluamme luoda B-puun, jonka kertaluku on 3, lisäämällä arvot väliltä 1–10.
Vaihe 1: Ensin luomme solmun, jolla on yksi arvo alla olevan kuvan mukaisesti:
Vaihe 2: Seuraava elementti on 2, joka tulee ykkösen jälkeen alla olevan kuvan mukaisesti:
Vaihe 3: Seuraava elementti on 3, ja se lisätään 2:n jälkeen alla olevan kuvan mukaisesti:
Koska tiedämme, että jokaisella solmulla voi olla enintään 2 avainta, jaamme tämän solmun keskielementin kautta. Keskimmäinen elementti on 2, joten se siirtyy yläelementtiin. Solmulla 2 ei ole pääsolmua, joten siitä tulee juurisolmu alla olevan kuvan mukaisesti:
Vaihe 4: Seuraava elementti on 4. Koska 4 on suurempi kuin 2 ja 3, se lisätään 3:n jälkeen alla olevan kuvan mukaisesti:
Vaihe 5: Seuraava elementti on 5. Koska 5 on suurempi kuin 2, 3 ja 4, se lisätään 4:n jälkeen alla olevan kuvan mukaisesti:
Koska tiedämme, että jokaisella solmulla voi olla enintään 2 avainta, jaamme tämän solmun keskielementin kautta. Keskimmäinen elementti on 4, joten se siirtyy yläelementtiin. Vanhempi on solmu 2; siksi 4 lisätään 2:n jälkeen alla olevan kuvan mukaisesti:
Vaihe 6: Seuraava elementti on 6. Koska 6 on suurempi kuin 2, 4 ja 5, niin 6 tulee 5:n jälkeen alla olevan kuvan mukaisesti:
Vaihe 7: Seuraava elementti on 7. Koska 7 on suurempi kuin 2, 4, 5 ja 6, niin 7 tulee 6:n jälkeen alla olevan kuvan mukaisesti:
Koska tiedämme, että jokaisella solmulla voi olla enintään 2 avainta, jaamme tämän solmun keskielementin kautta. Keskimmäinen elementti on 6, joten se siirtyy yläelementtiin alla olevan kuvan mukaisesti:
Mutta 6:ta ei voi lisätä 4:n jälkeen, koska solmulla voi olla enintään 2 avainta, joten jaamme tämän solmun keskielementin kautta. Keskimmäinen elementti on 4, joten se siirtyy yläelementtiin. Koska solmulla 4 ei ole pääsolmua, solmusta 4 tulee juurisolmu alla esitetyllä tavalla:
Mikä on B+ puu?
The B+ puu Tunnetaan myös kehittyneenä itsetasapainotteisena puuna, koska jokainen polku puun juuresta puun lehtiin on samanpituinen. Tässä sama pituus tarkoittaa, että kaikki lehtisolmut ovat samalla tasolla. Ei tapahdu niin, että osa lehtisolmuista esiintyy kolmannella tasolla ja osa toisella tasolla.
B+-puuindeksiä pidetään monitasoisena hakemistona, mutta B+-puurakenne ei ole samanlainen kuin monitasoisten indeksisekvenssitiedostojen.
Miksi B+-puuta käytetään?
B+-puuta käytetään tallentamaan tietueet erittäin tehokkaasti tallentamalla tietueet indeksoidulla tavalla käyttämällä B+-puun indeksoitua rakennetta. Monitasoisen indeksoinnin ansiosta tietojen käyttö on nopeampaa ja helpompaa.
B+ puun solmurakenne
B+-puun solmurakenne sisältää osoittimia ja avainarvoja, jotka näkyvät alla olevassa kuvassa:
Kuten voimme havaita yllä olevasta B+-puusolmurakenteesta, se sisältää n-1 avainarvoa (k1to kn-1) ja n osoitinta (s1pn).
Solmuun sijoitetut hakuavaimen arvot pidetään lajiteltuna. Joten jos i
Rajoitus erityyppisille solmuille
Olkoon 'b' B+-puun järjestys.
Ei-lehtisolmu
Olkoon 'm' solmun lapsien lukumäärää, jolloin puun järjestyksen ja lasten lukumäärän välinen suhde voidaan esittää seuraavasti:
Olkoon k edustaa hakuavaimen arvoja. Puun järjestyksen ja hakuavaimen välinen suhde voidaan esittää seuraavasti:
Koska tiedämme, että osoittimien määrä on yhtä suuri kuin hakuavaimen arvot plus 1, joten matemaattisesti se voidaan kirjoittaa seuraavasti:
Osoittimien (tai lasten) määrä = Hakunäppäinten määrä + 1
Siksi osoittimien enimmäismäärä olisi 'b' ja osoittimien vähimmäismäärä olisi b/2:n kattofunktio.
Lehtisolmu
Lehtisolmu on solmu, joka esiintyy B+-puun viimeisellä tasolla, ja jokainen lehtisolmu käyttää vain yhtä osoitinta muodostaakseen yhteyden toisiinsa peräkkäisen pääsyn tarjoamiseksi lehtitasolla.
Lehtisolmussa lasten enimmäismäärä on:
Hakuavainten enimmäismäärä on:
Juurisolmu
Lapsien enimmäismäärä juurisolmun tapauksessa on: b
Lasten vähimmäismäärä on: 2
Erikoistapaukset B+-puussa
Tapaus 1: Jos juurisolmu on puun ainoa solmu. Tässä tapauksessa juurisolmusta tulee lehtisolmu.
Tässä tapauksessa lapsien enimmäismäärä on 1, eli itse juurisolmu, kun taas lapsien vähimmäismäärä on b-1, mikä on sama kuin lehtisolmulla.
Lehtisolmun esitys B+-puussa
Yllä olevassa kuvassa '.' edustaa osoitinta, kun taas 10, 20 ja 30 ovat avainarvoja. Osoitin sisältää osoitteen, johon avainarvo on tallennettu, kuten yllä olevassa kuvassa näkyy.
Esimerkki B+-puusta
java pää
Yllä olevassa kuvassa solmu sisältää kolme avainarvoa, eli 9, 16 ja 25. Ennen numeroa 9 näkyvä osoitin sisältää avainarvot, jotka ovat pienempiä kuin 9, joita edustaa k.i. Osoitin, joka näkyy ennen numeroa 16, sisältää avainarvot, jotka ovat suurempia tai yhtä suuria kuin 9, mutta pienemmät kuin 16, joita edustaa kj. Ennen numeroa 25 näkyvä osoitin sisältää avainarvot, jotka ovat suurempia tai yhtä suuria kuin 16, mutta pienemmät kuin 25, joita edustaa k.n.
Erot B-puun ja B+-puun välillä
Seuraavat ovat erot B-puun ja B+-puun välillä:
| B puu | B+ puu |
|---|---|
| B-puussa kaikki avaimet ja tietueet on tallennettu sekä sisäisiin että lehtisolmuihin. | B+-puussa avaimet ovat indeksejä, jotka on tallennettu sisäisiin solmuihin, ja tietueet on tallennettu lehtisolmuihin. |
| B-puussa avaimia ei voi tallentaa toistuvasti, mikä tarkoittaa, ettei avaimia tai tietueita ole päällekkäin. | B+-puussa avainten esiintymisessä voi olla redundanssia. Tässä tapauksessa tietueet tallennetaan lehtisolmuihin, kun taas avaimet tallennetaan sisäisiin solmuihin, joten sisäisissä solmuissa voi olla redundantteja avaimia. |
| B-puussa lehtisolmuja ei ole linkitetty toisiinsa. | B+-puussa lehtisolmut on linkitetty toisiinsa peräkkäisen pääsyn tarjoamiseksi. |
| Btreessä haku ei ole kovin tehokasta, koska tietueet tallennetaan joko lehtiin tai sisäisiin solmuihin. | B+-puussa haku on erittäin tehokasta tai nopeampaa, koska kaikki tietueet on tallennettu lehtisolmuihin. |
| Sisäisten solmujen poistaminen on erittäin hidasta ja aikaa vievä prosessi, koska meidän on otettava huomioon myös poistetun avaimen lapsi. | Poistaminen B+-puussa on erittäin nopeaa, koska kaikki tietueet on tallennettu lehtisolmuihin, joten meidän ei tarvitse ottaa huomioon solmun lapsia. |
| Btreessä peräkkäinen pääsy ei ole mahdollista. | B+-puussa kaikki lehtisolmut ovat yhteydessä toisiinsa osoittimen kautta, joten peräkkäinen pääsy on mahdollista. |
| Btreessä tehdään enemmän halkaisutoimintoja, joiden vuoksi korkeus kasvaa leveyteen verrattuna, | B+ puulla on enemmän leveyttä kuin korkeus. |
| Btreessä jokaisella solmulla on vähintään kaksi haaraa ja jokainen solmu sisältää joitakin tietueita, joten meidän ei tarvitse kulkea lehtisolmuihin saadaksemme tietoja. | B+-puussa sisäiset solmut sisältävät vain osoittimia ja lehtisolmut sisältävät tietueita. Kaikki lehtisolmut ovat samalla tasolla, joten meidän täytyy kulkea lehtien solmuihin saadaksemme tiedot. |
| Juurisolmu sisältää vähintään 2 - m lasta, missä m on puun järjestys. | Juurisolmu sisältää vähintään 2 - m lasta, missä m on puun järjestys. |