Кључна разлика: У компјутерима, бинарна стабла су структуре података о дрвету које похрањују податке и омогућују кориснику приступ, претраживање, уметање и брисање података у алгоритамском времену. Разлика између Б и Б + стабла је у томе што, у Б-стаблу, кључеви и подаци могу бити ускладиштени у оба унутрашња и лишна чвора, док у Б + стаблу, подаци и кључеви могу бити ускладиштени само у листовима .
Бинарна стабла су балансирана стабла за претраживање која су дизајнирана да раде добро на секундарним уређајима за складиштење са директним приступом, као што су магнетни дискови. Рудолф Баиер и Ед МцЦреигхт измислили су концепт Б-стабла.
Б-стабло је генерализовано стабло бинарног претраживања, у којем сваки чвор може имати више од двоје дјеце. Сваки унутрашњи чвор у Б-стаблу садржи одређени број тастера. Ови тастери раздвајају вредности и даље формирају под-дрвеће. Унутрашњи чворови у Б-стаблу могу имати променљиви број дечјих чворова, који су распоређени унутар унапред дефинисаног опсега. У тренутку када се било који податак убаци или уклони из било ког одговарајућег чвора, долази до промене у броју дечјих чворова. Да би се одржао предефинисани опсег, унутрашњи чворови могу бити спојени или раздвојени. У Б-стаблу, дозвољен је опсег дечјих чворова, због чега се мора одржавати унапред дефинисани опсег.
Б-стабла не морају бити често ребалансирана за разлику од других саморегулативних стабала за претраживање. Чворови ових стабала нису увек пуни; стога се простори конзумирају непотребно у тим стаблима што доводи до расипања простора. Само доња и горња граница броја дјечјих чворова су обично фиксне за одређену имплементацију. На пример, у стаблу од 2-3 Б (које се често назива 2-3 стабло), сваки унутрашњи чвор може имати само 2 или 3 дечије чворове.
Поред тога, Б-стабло је оптимизовано за системе који читају и пишу велике блокове података. Обично се користи у базама података и системима датотека. У стаблу Б, сви чворови се чувају на истим дубинама балансирања од коријенских чворова. Ове дубине се споро повећавају како се број елемената повећава; ово резултира да су сви листови чворова још један чвор даље од корена. Штавише, Б-стабла су повољнија у поређењу са другим имплементацијама у погледу времена потребног за приступ подацима.
Б + стабло је дрво н-низа са чвором, који се састоји од великог броја деце по чвору. Коријен може бити лист или чвор који садржи више од двоје дјеце. Б + стабло се састоји од корена, унутрашњих чворова и листова.
Б + стабло је исто као и Б стабло; једина разлика је у томе што се у Б + стаблу додаје додатни ниво на дну са повезаним листовима. Такође, за разлику од Б стабла, сваки чвор у Б + стаблу садржи само кључеве, а не парове кључ-вредност.
Додатно, фактор балансирања или ред Б + стабла мери капацитет унутрашњих чворова на стаблу, тј. Број чворова које они могу имати. Стварни број деце за чвор је ограничен на унутрашње чворове. Коријен је међутим изузетак јер је дозвољено имати више од два броја дјеце. На пример, ако је ред Б + стабла 7, сваки унутрашњи чвор (осим корена) може имати између 4 и 7 деце; док корен може имати између 2 и 7. Примарна вриједност стабла Б + је у похрањивању података за учинковито проналажење у блок-оријентираном контексту за похрану и посебно у датотечним суставима.
Примарна вредност стабла Б + је у чувању и одржавању података, тако да се подаци не губе. Овај приступ је посебно примењен у блок-оријентисаном контексту за складиштење иу неким одређеним системима датотека. Листови, који су најнижи индексни блокови Б + стабла, често су међусобно повезани у повезаном списку; стога ово чини упите распона или уређену итерацију кроз блокове једноставнијим и ефикаснијим. Штавише, просторни фактор се не губи у дрвећу Б +. Б + стабло пружа ефикасан формат структуре података о становању, што их чини једноставним у приступу и складиштењу. Б + стабла су посебно корисна као индекс система базе података, где се подаци обично налазе на диску.
Поређење између стабла Б и Б + стабла:
Б Трее | Б + Трее | |
Кратки веб описи | АБ стабло је организациона структура за складиштење и проналажење информација у облику стабла у којем су сви терминални чворови на истој удаљености од базе, а сви не-терминални чворови имају између н и 2 н под-дрвећа или показивача ( н је цео број). | Б + стабло је н-низ стабла са променљивом али често великим бројем деце по чвору. Б + стабло се састоји од корена, унутрашњих чворова и листова. Коријен може бити лист или чвор с двоје или више дјеце. |
Такође познат као | Балансирано дрво. | Б плус стабло. |
Спаце | На) | На) |
Претрага | О (лог н) | О (лог б н) |
Инсерт | О (лог н) | О (лог б н) |
Обриши | О (лог н) | О (лог б н) |
Складиште | У стаблу Б, кључеви за претраживање и подаци који се чувају у унутрашњим или листовима чворова. | У Б + стаблу, подаци се чувају само у листовима чворова. |
Дата | Чворови листова трију складишта показују показиваче на записе, а не на стварне записе. | Чвор листова стабла складишти стварни запис а не показиваче на записе. |
Спаце | Ова стабла губе простор | Тамо дрвеће не троши простор. |
Функција листа чворова | У стаблу Б, чвор листа не може да складишти помоћу повезане листе. | У Б + стаблу, подаци о лисном чвору се наручују у секвенцијалној повезаној листи. |
У потрази | Овде претраживање постаје теже у Б-стабу јер се подаци не могу наћи у чвору листа. | Овде је претраживање било ког податка у Б + стаблу веома лако јер су сви подаци пронађени у листовима чворова. |
Приступачност претраживања | Овде у Б стаблу претраживање није тако лако у поређењу са Б + стаблом. | Овде у Б + стаблу претраживање постаје лако. |
Редундант кеи | Они не чувају редундантни кључ за претрагу. | Они складиште сувишан кључ за претрагу. |
Апплицатионс | Они су старија верзија и нису толико повољни у односу на Б + дрвеће. | Многи имплементатори система базе података преферирају структурну једноставност Б + стабла. |