Ključna razlika: v računalnikih so binarna drevesa drevesne podatkovne strukture, ki shranjujejo podatke in uporabniku omogočajo dostop, iskanje, vstavljanje in brisanje podatkov ob algoritmičnem času. Razlika med drevesi B in B + je v tem, da se lahko v drevesu B ključi in podatki shranijo v notranjih in listnih vozliščih, medtem ko se v drevesu B + podatki in ključi lahko shranijo le v listnih vozliščih. .
Binarna drevesa so uravnotežena drevesa iskanja, ki so zasnovana tako, da dobro delujejo na sekundarnih pomnilniških napravah z neposrednim dostopom, kot so magnetni diski. Rudolf Bayer in Ed McCreight sta izumila koncept B-drevesa.
B-drevo je posplošeno binarno drevo iskanja, v katerem ima lahko katerokoli vozlišče več kot dva otroka. Vsako notranje vozlišče v drevesu B vsebuje več ključev. Te tipke ločujejo vrednosti in nadalje oblikujejo pod-drevesa. Notranja vozlišča v drevesu B imajo lahko spremenljivo število otroških vozlišč, ki so razporejena znotraj vnaprej določenega območja. V času, ko so vsi podatki vstavljeni ali odstranjeni iz vsakega vozlišča, je prišlo do spremembe števila otroških vozlišč. Da bi ohranili vnaprej določeno območje, so lahko notranja vozlišča združena ali razdeljena. V drevesu B je dovoljeno območje otroških vozlišč, zaradi česar je treba ohraniti vnaprej določeno območje.
B-drevesa ni treba pogosto uravnotežiti za razliko od drugih samoregulativnih dreves za iskanje. Vozlišča na teh drevesih niso vedno polna; zato so prostori na teh drevesih nepotrebni, kar vodi do izgube prostora. Samo za spodnjo in zgornjo mejo števila otroških vozlišč je običajno določeno določeno izvedbo. Na primer, v drevesu 2-3 B (ki se pogosto imenuje samo 2-3 drevo) ima lahko vsako notranje vozlišče samo 2 ali 3 podrejena vozlišča.
Poleg tega je B-drevo optimizirano za sisteme, ki berejo in zapisujejo velike bloke podatkov. Običajno se uporablja v podatkovnih bazah in datotečnih sistemih. V drevesu B se vsa vozlišča hranijo na istih globinah uravnoteženja od korenskih vozlišč. Te globine se počasi povečujejo s povečevanjem števila elementov; to pomeni, da so vsa listna vozlišča še eno vozlišče dlje od korena. Poleg tega so B-drevesa ugodnejša v primerjavi z drugimi izvedbami glede na čas, potreben za dostop do podatkov.
Drevo B + je drevo n-nizov z vozliščem, ki je sestavljeno iz velikega števila otrok na vozlišču. Koren je lahko list ali vozlišče, ki vsebuje več kot dva otroka. Drevo B + je sestavljeno iz korena, notranjih vozlišč in listov.
Drevo B + je enako drevesu B; edina razlika je, da je na drevesu B + na dnu dodana dodatna raven s povezanimi listi. Tudi za razliko od B drevesa vsako vozlišče v drevesu B + vsebuje le ključe in ne pare ključ-vrednost.
Poleg tega faktor uravnoteženja ali vrstni red drevesa B + meri zmogljivost notranjih vozlišč v drevesu, tj. Število vozlišč, ki jih lahko imajo. Dejansko število otrok za vozlišče je omejeno za notranja vozlišča. Korenina pa je izjema, saj je dovoljeno imeti več kot dva števila otrok. Na primer, če je vrstni red drevesa B + 7, ima lahko vsako notranje vozlišče (razen korena) od 4 do 7 otrok; medtem ko je lahko koren med 2 in 7. Primarna vrednost drevesa B + je v shranjevanju podatkov za učinkovito iskanje v blokovno usmerjenem pomnilniku in zlasti v datotečnih sistemih.
Primarna vrednost drevesa B + je shranjevanje in vzdrževanje podatkov, tako da se podatki ne izgubijo. Ta pristop se uporablja predvsem v blok-usmerjenem kontekstu shranjevanja in v nekaterih posebnih datotečnih sistemih. Listi, ki so najnižji indeksni bloki drevesa B +, so pogosto povezani med seboj na povezanem seznamu; zato poizvedbe v obsegu ali urejena iteracija postanejo enostavnejše in učinkovitejše. Poleg tega se prostorski faktor ne izgubi v drevesih B +. Drevo B + zagotavlja učinkovito obliko strukture podatkov o stanovanjih, kar omogoča preprosto dostopanje in shranjevanje. Drevesa B + so še posebej uporabna kot indeks sistema baz podatkov, kjer se podatki običajno nahajajo na disku.
Primerjava med drevesoma B in drevesom B +:
B Drevo | B + Drevo | |
Kratki spletni opisi | AB drevo je organizacijska struktura za shranjevanje in pridobivanje informacij v obliki drevesa, v katerem so vsa terminalska vozlišča na enaki razdalji od baze, vsa ne-terminalna vozlišča pa imajo med n in 2 n pod-drevesi ali kazalci ( n je celo število). | B + drevo je n-array drevo z spremenljivko, vendar pogosto veliko število otrok na vozlišče. Drevo B + je sestavljeno iz korena, notranjih vozlišč in listov. Koren je lahko list ali vozlišče z dvema ali več otroki. |
Poznan tudi kot | Uravnoteženo drevo. | B plus drevo. |
Vesolje | O (n) | O (n) |
Iskanje | O (log n) | O (log b n) |
Vstavi | O (log n) | O (log b n) |
Izbriši | O (log n) | O (log b n) |
Shranjevanje | V drevesu B poiščite ključe in podatke, shranjene v notranjih ali listnih vozliščih. | V drevesu B + so podatki shranjeni samo v listnih vozliščih. |
Podatki | Listna vozlišča treh trgovin kažejo na zapise namesto na dejanske zapise. | Listna vozlišča drevesa shranijo dejanski zapis namesto kazalcev na zapise. |
Vesolje | Ta drevesa odpadajo prostor | Tam drevesa ne zapravljajo prostora. |
Funkcija listnih vozlov | V drevesu B se vozlišče listov ne more shraniti s povezanim seznamom. | V drevesu B + so podatki o vozliščih listov urejeni na zaporednem povezanem seznamu. |
Iskanje | Tukaj iskanje postane težje v B-drevesu, saj podatkov ni mogoče najti v vozlišču listov. | Tukaj je iskanje podatkov v drevesu B + zelo enostavno, ker so vsi podatki na voljo v listnih vozliščih. |
Dostopnost iskanja | Tu v B drevesu iskanje ni tako preprosto v primerjavi z drevesom B +. | Tu v B + drevesu iskanje postane enostavno. |
Redundant key | Ne shranjujejo presežnega ključa za iskanje. | Shranijo odvečni ključ za iskanje. |
Aplikacije | So starejša različica in niso tako ugodne v primerjavi z drevesi B +. | Veliko implementatorjev sistema baz podatkov daje prednost strukturni enostavnosti drevesa B +. |