Keskeinen ero: Tietokoneissa binaaripuut ovat puun tietorakenteita, jotka tallentavat tiedot ja antavat käyttäjälle mahdollisuuden käyttää, hakea, lisätä ja poistaa tietoja algoritmisesti. B- ja B + -puiden välinen ero on se, että B-puussa avaimet ja tiedot voidaan tallentaa sekä sisä- että lehtisolmuihin, kun taas B + -puussa data ja avaimet voidaan tallentaa vain lehtisolmuihin .
Binaaripuut ovat tasapainoisia hakupuita, jotka on suunniteltu toimimaan hyvin toissijaisten tallennuslaitteiden, kuten magneettilevyjen, kanssa. Rudolf Bayer ja Ed McCreight keksi B-puun käsitteen.
B-puu on yleistetty binaarihakupuu, jossa missä tahansa solmussa voi olla enemmän kuin kaksi lasta. Jokainen B-puun sisäinen solmu sisältää useita avaimia. Nämä avaimet erottavat arvot ja muodostavat edelleen alipuut. B-puun sisäisillä solmuilla voi olla vaihtelevia määriä lapsisolmuja, jotka on järjestetty ennalta määritellyn alueen sisällä. Kun jokin data lisätään tai poistetaan mistä tahansa vastaavasta solmusta, lasten solmujen lukumäärä muuttuu. Ennalta määritellyn alueen säilyttämiseksi sisäiset solmut voidaan yhdistää tai jakaa. B-puussa sallitaan joukko lasten solmuja, joiden vuoksi ennalta määritelty alue on säilytettävä.
B-puita ei tarvitse tasapainottaa usein toisin kuin muut itse tasapainottavat hakupuut. Näiden puiden solmut eivät ole aina täynnä; näin ollen tilat kulutetaan tarpeettomasti näissä puissa, mikä johtaa tilan hukkaan. Ainoastaan lapsisolmujen lukumäärän alemmat ja ylemmät rajat on tyypillisesti kiinnitetty tiettyyn toteutukseen. Esimerkiksi 2-3 B-puussa (jota kutsutaan usein 2-3 puuksi) jokaisessa sisäisessä solmussa voi olla vain 2 tai 3 lapsisolmua.
Lisäksi B-puu on optimoitu järjestelmille, jotka lukevat ja kirjoittavat suuria tietolohkoja. Sitä käytetään yleisesti tietokannoissa ja tiedostojärjestelmissä. B-puussa kaikki solmut pidetään samassa tasapainotussyvyydessä juurisolmuista. Nämä syvyydet kasvavat hitaasti, kun elementtien lukumäärä kasvaa; tämä johtaa siihen, että kaikki lehtisolmut ovat vielä yksi solmu kauempana juuresta. Lisäksi B-puut ovat edullisempia verrattuna muihin toteutuksiin, kun otetaan huomioon aika, joka kuluu tietojen käyttämiseen.
B + puu on n-array puu solmulla, joka koostuu suuresta määrästä lapsia solmua kohti. Juuri voi olla lehti tai solmu, joka sisältää enemmän kuin kaksi lasta. B + puu koostuu juuresta, sisäisistä solmuista ja lehdistä.
B + puu on sama kuin B-puu; Ainoa ero on se, että B + -puussa on lisätty taso, johon on lisätty linkitetyt lehdet. Toisin kuin B-puussa, jokainen B + -puun solmu sisältää vain avaimet eikä avaimen arvopareja.
Lisäksi tasapainotuskerroin tai B + -puun järjestys mittaa puun sisäisten solmujen kapasiteettia, ts. Niiden solmujen lukumäärää, joita niillä voi olla. Solmun todellinen lasten määrä on rajoitettu sisäisille solmuille. Juuri on kuitenkin poikkeus, sillä lapsia saa olla enemmän kuin kaksi. Jos esimerkiksi B + -puun järjestys on 7, jokaisella sisäisellä solmulla (paitsi juuri) voi olla 4–7 lasta; kun juurella voi olla välillä 2 - 7. B + -puun ensisijainen arvo on tietojen tallentaminen tehokkaaseen hakuun lohko-orientoidussa tallennuskontekstissa ja erityisesti tiedostojärjestelmissä.
B + -puun ensisijainen arvo on tietojen tallentamisessa ja ylläpidossa, joten tietoja ei menetetä. Tätä lähestymistapaa sovelletaan erityisesti lohkokeskeiseen tallennuskontekstiin ja joihinkin erityisiin tiedostojärjestelmiin. Lehdet, jotka ovat B + -puun alimpia indeksilohkoja, ovat usein yhteydessä toisiinsa linkitetyssä luettelossa; näin ollen se helpottaa ja tehostaa lohkokyselyjä tai tilattua iteraatiota lohkojen kautta. Lisäksi avaruuskerrointa ei hukata B + -puissa. B + -puurakenne tarjoaa tehokkaan asuntotietorakenteen muodon, joka tekee niistä yksinkertaisen pääsyn ja tallennuksen. B + -puut ovat erityisen käyttökelpoisia tietokantajärjestelmän indeksinä, jossa data tyypillisesti sijaitsee levyllä.
B-puun ja B + -puun vertailu:
B Tree | B + puu | |
Lyhyt web-kuvaus | AB-puu on organisaatiorakenne informaation tallennukseen ja hakuun puun muodossa, jossa kaikki päätelaitteet ovat samalla etäisyydellä alustasta, ja kaikilla muilla kuin päätelaitteilla olevilla solmuilla on n ja 2 n alipuita tai osoittimia (missä n on kokonaisluku). | B + puu on n-array-puu, jossa on muuttuva mutta usein suuri määrä lapsia solmua kohti. B + puu koostuu juuresta, sisäisistä solmuista ja lehdistä. Juuri voi olla joko lehti tai solmu, jossa on kaksi tai useampia lapsia. |
Tunnetaan myös | Tasapainoinen puu. | B plus puu. |
tila | Päällä) | Päällä) |
Hae | O (log n) | O (log b n) |
Insert | O (log n) | O (log b n) |
Poistaa | O (log n) | O (log b n) |
varastointi | B-puussa hakukoodit ja sisäiseen tai lehtisolmuun tallennetut tiedot. | B + -puussa tiedot tallennetaan vain lehtisolmuihin. |
data | Kolmen myymälän lehtisolmut osoittavat pikemminkin tietueita kuin todellisia tietueita. | Puun lehtisolmut tallentavat todellisen tietueen kuin viittaukset tietueisiin. |
tila | Nämä puut hävittävät tilaa | Siellä puita ei tuhlata tilaa. |
Lehtisolmujen toiminta | B-puussa lehtisolmu ei voi tallentaa linkitettyä luetteloa. | B + puussa lehtisolmujen tiedot tilataan peräkkäiseen linkitettyyn luetteloon. |
tutkiva | Tässä hakeminen vaikeutuu B-puussa, koska tietoja ei löydy lehtisolmusta. | Täällä kaikkien B + -tietojen haku on erittäin helppoa, koska kaikki tiedot löytyvät lehtisolmuista. |
Hae esteettömyyttä | Tässä B-puussa etsintä ei ole niin helppoa kuin B + -puulla. | Täällä B + puussa haku helpottuu. |
Redundant-näppäin | Ne eivät tallenna tarpeettomia hakusanoja. | Ne tallentavat tarpeettoman hakusanan. |
Sovellukset | Ne ovat vanhempia ja eivät ole niin edullisia kuin B + -puilla. | Monet tietokantajärjestelmien toteuttajat suosivat B +-puun rakenteellista yksinkertaisuutta. |
