Ključna razlika: u računalima binarna stabla su strukture podataka o stablu koje pohranjuju podatke i omogućuju korisniku pristup, pretraživanje, umetanje i brisanje podataka u algoritamskom vremenu. Razlika između stabla B i B + je u tome što se u stablu B ključevi i podaci mogu pohraniti u unutarnjim i listnim čvorovima, dok se u stablu B + podaci i ključevi mogu pohraniti samo u čvorovima lista,
Binarna stabla su uravnotežena stabla pretraživanja koja su dizajnirana da rade dobro na sekundarnim uređajima za pohranu s izravnim pristupom, kao što su magnetski diskovi. Rudolf Bayer i Ed McCreight izmislili su koncept B-stabla.
B-stablo je generalizirano binarno stablo pretraživanja, u kojem bilo koji čvor može imati više od dvoje djece. Svaki unutarnji čvor u B-stablu sadrži brojne tipke. Ove tipke razdvajaju vrijednosti i dalje oblikuju pod-stabla. Unutarnji čvorovi u B-stablu mogu imati varijabilni broj dječjih čvorova, koji su raspoređeni unutar unaprijed definiranog raspona. U trenutku kada su bilo koji podaci umetnuti ili uklonjeni iz bilo kojeg odgovarajućeg čvora, došlo je do promjene u broju dječjih čvorova. Da bi se održao unaprijed definirani raspon, unutarnji čvorovi mogu biti spojeni ili podijeljeni. U stablu B dopušten je raspon dječjih čvorova, zbog čega se mora održavati unaprijed definirani raspon.
B-stabla ne moraju često biti rebalansirana za razliku od drugih samo-balansirajućih stabala za pretraživanje. Čvorovi u tim stablima nisu uvijek puni; stoga se prostori konzumiraju nepotrebno u tim stablima što dovodi do rasipanja prostora. Samo se donja i gornja granica broja dječjih čvorova obično fiksiraju za određenu implementaciju. Na primjer, u stablu od 2-3 B (koje se često naziva 2-3 stablo), svaki unutarnji čvor može imati samo 2 ili 3 dječja čvora.
Osim toga, B-stablo je optimizirano za sustave koji čitaju i pišu velike blokove podataka. Obično se koristi u bazama podataka i sustavima datoteka. U stablu B svi se čvorovi čuvaju na istim dubinama uravnoteženja od korijenskih čvorova. Te se dubine polako povećavaju kako se broj elemenata povećava; to rezultira time da su svi listovi čvorova još jedan čvor dalje od korijena. Nadalje, B-stabla su povoljnija u usporedbi s drugim implementacijama u odnosu na vrijeme potrebno za pristup podacima.
B + stablo je stablo n-polja s čvorom, koji se sastoji od velikog broja djece po čvoru. Korijen može biti list ili čvor koji sadrži više od dvoje djece. B + stablo sastoji se od korijena, unutarnjih čvorova i lišća.
B + stablo je isto kao i B stablo; jedina razlika je u tome što se u B + stablu dodaje dodatna razina na dnu s povezanim lišćem. Također, za razliku od B stabla, svaki čvor u B + stablu sadrži samo ključeve, a ne parove ključ-vrijednost.
Dodatno, faktor uravnoteženja ili redoslijed B + stabla mjeri kapacitet unutarnjih čvorova na stablu, tj. Broj čvorova koje mogu imati. Stvarni broj djece za čvor je ograničen na unutarnje čvorove. Korijen je međutim iznimka jer je dopušteno imati više od dva broja djece. Na primjer, ako je redoslijed B + stabla 7, svaki unutarnji čvor (osim korijena) može imati između 4 i 7 djece; dok korijen može imati između 2 i 7. Primarna vrijednost stabla B + je u pohranjivanju podataka za učinkovito pronalaženje u blok-orijentiranom kontekstu za pohranu i posebno u datotečnim sustavima.
Primarna vrijednost stabla B + je u pohranjivanju i održavanju podataka, tako da se podaci ne gube. Ovaj pristup je posebno primijenjen u blok-orijentiranom kontekstu pohrane iu nekim određenim datotečnim sustavima. Listovi, koji su najniži indeksni blokovi B + stabla, često su međusobno povezani u povezanom popisu; stoga to čini upite raspona ili uređenu iteraciju kroz blokove jednostavnijim i učinkovitijim. Nadalje, prostorni faktor se ne gubi u B + stablima. Stablo B + pruža učinkovit format strukture podataka o stanovanju, što ih čini jednostavnim u pristupu i pohranjivanju. Stabla B + osobito su korisna kao indeks sustava baza podataka, gdje se podaci obično nalaze na disku.
Usporedba između stabla B i stabla B +:
B Stablo | B + stablo | |
Kratki web opisi | AB stablo je organizacijska struktura za pohranjivanje i dohvaćanje podataka u obliku stabla u kojem su sva terminalna čvorišta na istoj udaljenosti od baze, a svi ne-terminalni čvorovi imaju između n i 2 n pod-stabala ili pokazivača (gdje n je cijeli broj). | B + stablo je n-niz stabla s promjenljivim, ali često velikim brojem djece po čvoru. B + stablo sastoji se od korijena, unutarnjih čvorova i lišća. Korijen može biti list ili čvor s dvoje ili više djece. |
Također poznat kao | Uravnoteženo drvo. | B plus stablo. |
Prostor | Na) | Na) |
traži | O (log n) | O (log b n) |
Umetnuti | O (log n) | O (log b n) |
Izbrisati | O (log n) | O (log b n) |
skladištenje | U stablu B, pretražite ključeve i podatke pohranjene u unutarnjim ili listnim čvorovima. | U stablu B + podaci se pohranjuju samo u čvorovima listova. |
Podaci | Čvorište lista triju pohranjuje pokazivače na zapise, a ne na stvarne zapise. | Čvor listova stabla pohranjuje stvarni zapis, a ne pokazivače na zapise. |
Prostor | Ova stabla gube prostor | Stabla ne troše prostor. |
Funkcija čvorova lista | U stablu B, čvor lista ne može pohraniti pomoću povezanog popisa. | U B + stablu, podaci o čvoru lista su poredani u sekvencijalno povezani popis. |
Pretraživanje | Ovdje pretraživanje postaje teško u B-stablu jer se podaci ne mogu pronaći u čvoru lista. | Ovdje je pretraživanje bilo kojih podataka u B + stablu vrlo jednostavno jer se svi podaci nalaze u čvorovima listova. |
Pristupačnost pretraživanja | Ovdje u B stablu pretraživanje nije tako jednostavno u usporedbi s B + stablom. | Ovdje u B + stablu pretraživanje postaje lako. |
Redundantni ključ | Ne pohranjuju suvišan ključ za pretraživanje. | Oni pohranjuju suvišan ključ za pretraživanje. |
Prijave | Oni su starija verzija i nisu toliko povoljni u usporedbi sa stablima B +. | Mnogi implementatori sustava baze podataka preferiraju strukturnu jednostavnost stabla B +. |