Пре разумевања Б дрво и Б+ дрво разлике, требало би да знамо Б стабло и Б+ стабло одвојено.
Шта је Б дрво?
Б дрво је самобалансирајуће стабло, и то је м-смерно дрво где м дефинише редослед дрвета. Бтрее је генерализација Стабло бинарног претраживања у којој чвор може имати више од једног кључа и више од два детета у зависности од вредности м . У Б стаблу, подаци су наведени у сортираном редоследу са нижим вредностима на левом подстаблу и вишим вредностима у десном подстаблу.
референтни типови података у Јави
Особине Б дрвета
Ово су својства Б стабла:
- У стаблу Б сви чворови листа морају бити на истом нивоу, док у случају бинарног стабла чворови листа могу бити на различитим нивоима.
Хајде да разумемо ово својство кроз пример.
У горњем дрвету, сви чворови листа нису на истом нивоу, али имају највише двоје деце. Стога можемо рећи да је горе наведено дрво а бинарно дрво али не и Б дрво.
- Ако Бтрее има ред од м, онда сваки чвор може имати највише м У случају минималне деце, чворови листа имају нула деце, коренски чвор има два детета, а унутрашњи чворови имају плафон од м/2.
- Сваки чвор може имати највише (м-1) кључева. На пример, ако је вредност м 5, максимална вредност кључева је 4.
- Коријенски чвор има најмање један кључ, док сви остали чворови осим коријенског чвора имају (плафон м/2 минус - 1) минималне кључеве.
- Ако извршимо уметање у Б стабло, онда се чвор увек убацује у лисни чвор.
Претпоставимо да желимо да креирамо Б стабло реда 3 уметањем вредности од 1 до 10.
Корак 1: Прво, креирамо чвор са 1 вредношћу као што је приказано у наставку:
Корак 2: Следећи елемент је 2, који долази после 1 као што је приказано у наставку:
Корак 3: Следећи елемент је 3 и умеће се после 2 као што је приказано испод:
Као што знамо да сваки чвор може имати 2 максимална кључа, тако да ћемо овај чвор поделити кроз средњи елемент. Средњи елемент је 2, тако да се помера на свог родитеља. Чвор 2 нема родитеља, тако да ће постати основни чвор као што је приказано у наставку:
4. корак: Следећи елемент је 4. Пошто је 4 веће од 2 и 3, биће додат после 3 као што је приказано испод:
5. корак: Следећи елемент је 5. Пошто је 5 веће од 2, 3 и 4, биће додат после 4 као што је приказано у наставку:
Као што знамо да сваки чвор може имати 2 максимална кључа, тако да ћемо овај чвор поделити кроз средњи елемент. Средњи елемент је 4, тако да се помера на свог родитеља. Родитељ је чвор 2; према томе, 4 ће бити додато после 2 као што је приказано у наставку:
Корак 6: Следећи елемент је 6. Пошто је 6 веће од 2, 4 и 5, тако ће 6 доћи после 5 као што је приказано испод:
7. корак: Следећи елемент је 7. Пошто је 7 веће од 2, 4, 5 и 6, тако ће 7 доћи после 6 као што је приказано испод:
Као што знамо да сваки чвор може имати 2 максимална кључа, тако да ћемо овај чвор поделити кроз средњи елемент. Средњи елемент је 6, тако да се помера на свог родитеља као што је приказано испод:
Али, 6 се не може додати после 4 јер чвор може имати 2 максимална кључа, тако да ћемо овај чвор поделити кроз средњи елемент. Средњи елемент је 4, тако да се помера на свог родитеља. Пошто чвор 4 нема родитеља, чвор 4 ће постати основни чвор као што је приказано у наставку:
Шта је Б+ дрво?
Тхе Б+ дрво је такође познато као напредно самоуравнотежено дрво јер свака путања од корена дрвета до листа дрвета има исту дужину. Овде иста дужина значи да се сви чворови листа налазе на истом нивоу. Неће се десити да се неки од лисних чворова јављају на трећем, а неки на другом нивоу.
Индекс стабла Б+ се сматра индексом на више нивоа, али структура стабла Б+ није слична секвенцијалним датотекама индекса на више нивоа.
Зашто се користи Б+ дрво?
Б+ стабло се користи за складиштење записа веома ефикасно тако што се записи складиште на индексиран начин користећи индексирану структуру Б+ стабла. Захваљујући индексирању на више нивоа, приступ подацима постаје бржи и лакши.
Чворна структура Б+ стабла
Структура чвора Б+ стабла садржи показиваче и кључне вредности приказане на слици испод:
Као што можемо приметити у горњој структури чвора Б+ стабла да садржи н-1 вредности кључа (к1то кн-1) и н показивача (стр1до стрн).
Вредности кључа за претрагу које су смештене у чвор се чувају у сортираном редоследу. Дакле, ако и
Ограничење на различите типове чворова
Нека је 'б' ред Б+ стабла.
Нон-Леаф чвор
Нека 'м' представља број деце чвора, тада се однос између реда стабла и броја деце може представити као:
Нека к представља вредности кључа за претрагу. Однос између редоследа стабла и кључа за претрагу може се представити као:
Како знамо да је број показивача једнак вредностима кључа за претрагу плус 1, математички се може записати као:
Број показивача (или деце) = Број тастера за претрагу + 1
Према томе, максимални број показивача би био 'б', а минимални број показивача био би горња функција б/2.
Леаф Ноде
Листни чвор је чвор који се јавља на последњем нивоу Б+ стабла, и сваки лисни чвор користи само један показивач да се повеже један са другим како би обезбедио секвенцијални приступ на нивоу листа.
У чвору листа, максималан број деце је:
Максималан број тастера за претрагу је:
Роот Ноде
Максималан број деце у случају коренског чвора је: б
Минимални број деце је: 2
авл ротација стабла
Посебни случајеви у Б+ стаблу
Случај 1: Ако је коренски чвор једини чвор у стаблу. У овом случају, коренски чвор постаје лисни чвор.
У овом случају, максимални број деце је 1, односно сам коренски чвор, док је минимални број деце б-1, што је исто као и код листа чвора.
Представљање лисног чвора у Б+ стаблу
На горњој слици, '.' представља показивач, док су 10, 20 и 30 кључне вредности. Показивач садржи адресу на којој се чува вредност кључа, као што је приказано на горњој слици.
Пример Б+ дрвета
На горњој слици, чвор садржи три вредности кључа, тј. 9, 16 и 25. Показивач који се појављује испред 9 садржи вредности кључа мање од 9 представљене са ки. Показивач који се појављује испред 16, садржи вредности кључа веће или једнаке 9, али мање од 16 представљене са кј. Показивач који се појављује испред 25, садржи вредности кључа веће или једнаке 16, али мање од 25 представљене са кн.
Разлике између Б стабла и Б+ дрвета
Следе разлике између Б стабла и Б+ стабла:
| Б дрво | Б+ дрво |
|---|---|
| У Б стаблу, сви кључеви и записи се чувају како у унутрашњим тако иу листовима чворова. | У Б+ стаблу, кључеви су индекси ускладиштени у интерним чворовима, а записи се чувају у листовима. |
| У стаблу Б, кључеви се не могу више пута чувати, што значи да нема дуплирања кључева или записа. | У Б+ стаблу може постојати сувишност у појављивању кључева. У овом случају, записи се чувају у листовима чворова, док се кључеви чувају у унутрашњим чворовима, тако да сувишни кључеви могу бити присутни у унутрашњим чворовима. |
| У Бдрвету, чворови листа нису повезани једни са другима. | У Б+ стаблу, лисни чворови су повезани један са другим да би се обезбедио секвенцијални приступ. |
| У Бтрее-у претраживање није веома ефикасно јер се записи чувају или у листовима или у унутрашњим чворовима. | У Б+ стаблу претраживање је веома ефикасно или брже јер се сви записи чувају у листовима чворова. |
| Брисање унутрашњих чворова је веома спор и дуготрајан процес јер морамо узети у обзир и дете избрисаног кључа. | Брисање у Б+ стаблу је веома брзо јер се сви записи чувају у лисним чворовима тако да не морамо да разматрамо дете чвора. |
| У Бтрее-у, секвенцијални приступ није могућ. | У Б+ стаблу, сви чворови листа су повезани један са другим преко показивача, тако да је могућ секвенцијални приступ. |
| У Бтрее-у се изводи већи број операција цепања због којих се висина повећава у односу на ширину, | Б+ дрво има већу ширину у односу на висину. |
| У Бтрее-у, сваки чвор има најмање две гране и сваки чвор садржи неке записе, тако да не морамо да прелазимо до лисних чворова да бисмо добили податке. | У Б+ стаблу, унутрашњи чворови садрже само показиваче, а лисни чворови садрже записе. Сви чворови листа су на истом нивоу, тако да морамо да пређемо до чворова листа да бисмо добили податке. |
| Коренски чвор садржи најмање 2 до м деце где је м ред стабла. | Коренски чвор садржи најмање 2 до м деце где је м ред стабла. |