Б+ Трее је проширење Б стабла које омогућава ефикасно уметање, брисање и операције претраживања.
У Б стаблу, кључеви и записи могу да се чувају у унутрашњим као иу листовима чворова. Док, у Б+ стаблу, записи (подаци) могу да се чувају само на лисним чворовима, док унутрашњи чворови могу да чувају само вредности кључа.
јава петље
Листови чворова Б+ стабла су повезани заједно у облику једноструко повезаних листа како би упити за претрагу били ефикаснији.
Б+ Трее се користи за складиштење велике количине података који се не могу ускладиштити у главној меморији. Због чињенице да је величина главне меморије увек ограничена, унутрашњи чворови (кључеви за приступ записима) Б+ стабла се чувају у главној меморији, док се листови чворови чувају у секундарној меморији.
Унутрашњи чворови Б+ стабла се често називају индексним чворовима. Б+ стабло реда 3 је приказано на следећој слици.
Предности Б+ Трее
- Записи се могу преузети у истом броју приступа диску.
- Висина стабла остаје уравнотежена и мања у поређењу са Б стаблом.
- Можемо приступити подацима ускладиштеним у Б+ стаблу секвенцијално као и директно.
- Кључеви се користе за индексирање.
- Бржи упити за претрагу јер се подаци чувају само на листовима чворова.
Б дрво ВС Б+ дрво
| СН | Б Дрво | Б+ Трее |
|---|---|---|
| 1 | Кључеви за претрагу се не могу више пута чувати. | Могу бити присутни сувишни тастери за претрагу. |
| 2 | Подаци се могу чувати у лисним чворовима као иу унутрашњим чворовима | Подаци се могу чувати само на листовима чворова. |
| 3 | Тражење неких података је спорији процес јер се подаци могу наћи на унутрашњим чворовима као и на листовима. | Претраживање је релативно брже јер се подаци могу пронаћи само на чворовима листа. |
| 4 | Брисање унутрашњих чворова је тако компликовано и дуготрајно. | Брисање никада неће бити сложен процес јер ће елемент увек бити обрисан из листова чворова. |
| 5 | Листни чворови се не могу међусобно повезати. | Листни чворови су повезани заједно како би операције претраживања биле ефикасније. |
Уметање у Б+ дрво
Корак 1: Уметните нови чвор као лисни чвор
Корак 2: Ако лист нема потребан простор, поделите чвор и копирајте средњи чвор у следећи индексни чвор.
Корак 3: Ако индексни чвор нема потребан простор, поделите чвор и копирајте средњи елемент на следећу страницу индекса.
Пример:
Убаците вредност 195 у Б+ стабло реда 5 приказано на следећој слици.
195 ће бити уметнуто у десно подстабло од 120 после 190. Уметните га на жељену позицију.
Чвор садржи већи од максималног броја елемената, тј. 4, стога га поделите и поставите средњи чвор до родитеља.
Сада, индексни чвор садржи 6 деце и 5 кључева што нарушава својства Б+ стабла, стога морамо да га поделимо, приказано на следећи начин.
Брисање у Б+ стаблу
Корак 1: Избришите кључ и податке са листова.
Корак 2: ако листни чвор садржи мање од минималног броја елемената, спојите чвор са његовим братом и избришите кључ између њих.
Корак 3: ако индексни чвор садржи мање од минималног броја елемената, спојите чвор са братом и сестром и померите надоле кључ између њих.
Пример
Избришите кључ 200 из Б+ стабла приказаног на следећој слици.
питхон __наме__
200 је присутно у десном подстаблу од 190, после 195. обришите га.
Спојите два чвора користећи 195, 190, 154 и 129.
Сада, елемент 120 је једини елемент присутан у чвору који крши својства Б+ стабла. Стога, морамо га спојити користећи 60, 78, 108 и 120.
Сада ће висина Б+ стабла бити смањена за 1.
