B+ Tree є розширенням B Tree, яке забезпечує ефективне вставлення, видалення та пошук.
У дереві B ключі та записи можна зберігати як у внутрішніх, так і в листових вузлах. Тоді як у дереві B+ записи (дані) можуть зберігатися лише на листових вузлах, тоді як внутрішні вузли можуть зберігати лише ключові значення.
Листові вузли дерева B+ пов’язані між собою у формі однозв’язаних списків, щоб зробити пошукові запити більш ефективними.
B+ Tree використовується для зберігання великої кількості даних, які не можуть зберігатися в основній пам'яті. Через те, що розмір основної пам’яті завжди обмежений, внутрішні вузли (ключі доступу до записів) дерева B+ зберігаються в основній пам’яті, тоді як листові вузли зберігаються у вторинній пам’яті.
Внутрішні вузли дерева B+ часто називають вузлами індексу. Дерево B+ порядку 3 показано на наступному малюнку.
Переваги B+ Tree
- Записи можна отримати за однакову кількість звернень до диска.
- Висота дерева залишається збалансованою і меншою порівняно з деревом B.
- Ми можемо отримати доступ до даних, що зберігаються в дереві B+, як послідовно, так і безпосередньо.
- Ключі використовуються для індексації.
- Швидші пошукові запити, оскільки дані зберігаються лише на листових вузлах.
B Tree VS B+ Tree
| SN | B Дерево | B+ Дерево |
|---|---|---|
| 1 | Ключі пошуку не можна повторно зберігати. | Можуть бути присутні надлишкові ключі пошуку. |
| 2 | Дані можуть зберігатися як у листових вузлах, так і у внутрішніх вузлах | Дані можуть зберігатися лише на листових вузлах. |
| 3 | Пошук деяких даних є повільнішим процесом, оскільки дані можна знайти на внутрішніх вузлах, а також на кінцевих вузлах. | Пошук порівняно швидший, оскільки дані можна знайти лише на листових вузлах. |
| 4 | Видалення внутрішніх вузлів є дуже складним і трудомістким. | Видалення ніколи не буде складним процесом, оскільки елемент завжди видалятиметься з листових вузлів. |
| 5 | Листові вузли не можуть бути пов'язані між собою. | Листові вузли пов’язані разом, щоб зробити пошукові операції більш ефективними. |
Вставка в дерево B+
Крок 1: Вставте новий вузол як листовий вузол
if else цикл у java
крок 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+. Тому нам потрібно об’єднати його за допомогою 60, 78, 108 і 120.
Тепер висота дерева B+ буде зменшена на 1.
