B+ Tree е разширение на B Tree, което позволява ефективни операции за вмъкване, изтриване и търсене.
В B Tree ключовете и записите могат да се съхраняват както във вътрешните, така и в листовите възли. Докато в B+ дърво записите (данни) могат да се съхраняват само на листовите възли, докато вътрешните възли могат да съхраняват само ключовите стойности.
Листовите възли на B+ дърво са свързани заедно под формата на единично свързани списъци, за да направят заявките за търсене по-ефективни.
B+ Tree се използват за съхраняване на голямо количество данни, които не могат да бъдат съхранени в основната памет. Поради факта, че размерът на основната памет винаги е ограничен, вътрешните възли (ключове за достъп до записи) на B+ дървото се съхраняват в основната памет, докато листовите възли се съхраняват във вторичната памет.
Вътрешните възли на B+ дървото често се наричат индексни възли. B+ дърво от ред 3 е показано на следващата фигура.
Предимства на B+ Tree
- Записите могат да бъдат извлечени при равен брой достъпи до диска.
- Височината на дървото остава балансирана и по-малка в сравнение с B дърво.
- Можем да имаме достъп до данните, съхранени в B+ дърво, както последователно, така и директно.
- Ключовете се използват за индексиране.
- По-бързи заявки за търсене, тъй като данните се съхраняват само в листовите възли.
B Tree VS B+ Tree
| SN | Б Дърво | B+ дърво |
|---|---|---|
| 1 | Ключовете за търсене не могат да се съхраняват многократно. | Могат да присъстват излишни ключове за търсене. |
| 2 | Данните могат да се съхраняват в листови възли, както и във вътрешни възли | Данните могат да се съхраняват само в листовите възли. |
| 3 | Търсенето на някои данни е по-бавен процес, тъй като данните могат да бъдат намерени на вътрешни възли, както и на листови възли. | Търсенето е сравнително по-бързо, тъй като данните могат да бъдат намерени само в листовите възли. |
| 4 | Изтриването на вътрешни възли е толкова сложно и отнема много време. | Изтриването никога няма да бъде сложен процес, тъй като елементът винаги ще бъде изтрит от листовите възли. |
| 5 | Листните възли не могат да бъдат свързани заедно. | Листните възли са свързани заедно, за да направят операциите за търсене по-ефективни. |
Вмъкване в B+ дърво
Етап 1: Вмъкнете новия възел като листов възел
ако иначе баш
Стъпка 2: Ако листът няма необходимо място, разделете възела и копирайте средния възел в следващия индексен възел.
Стъпка 3: Ако индексният възел няма необходимо място, разделете възела и копирайте средния елемент на следващата индексна страница.
Пример:
Вмъкнете стойността 195 в дървото B+ от ред 5, показано на следващата фигура.
195 ще бъде вмъкнато в дясното поддърво на 120 след 190. Вмъкнете го в желаната позиция.
Възелът съдържа повече от максималния брой елементи, т.е. 4, следователно го разделете и поставете средния възел до родителя.
Сега индексният възел съдържа 6 деца и 5 ключа, което нарушава свойствата на B+ дървото, следователно трябва да го разделим, както е показано по-долу.
Изтриване в B+ дърво
Етап 1: Изтрийте ключа и данните от листовете.
Стъпка 2: ако листовият възел съдържа по-малко от минималния брой елементи, обединете възела надолу с неговия брат и изтрийте ключа между тях.
Стъпка 3: ако индексният възел съдържа по-малко от минималния брой елементи, обединете възела с братския и преместете надолу ключа между тях.
Пример
Изтрийте ключ 200 от дървото B+, показано на следващата фигура.
200 присъства в дясното поддърво на 190, след 195. изтрийте го.
Обединете двата възела, като използвате 195, 190, 154 и 129.
Сега елемент 120 е единственият елемент, присъстващ във възела, който нарушава свойствата на B+ Tree. Следователно трябва да го обединим, като използваме 60, 78, 108 и 120.
Сега височината на дървото B+ ще бъде намалена с 1.
