Для вилучення записів з B + дерева, запити пишуться з умовами, які описують бажане значення. Пошук в B +-дереві є ступінчастим процесом, починаючи з кореневого вузла:
Бінарний пошук ключа в поточному вузлі - варто пам'ятати, що пошукові значення сортуються. Шукаємо ключ Кi такий, що Кi? K < Ki1.
Якщо поточний вузол є внутрішнім, відбувається перехід на належну гілку, пов'язану з ключем Кi і повторюється пункт 1.
Якщо поточний вузол є листом, то:
Якщо K=Ki, то запис існує в таблиці, і ми можемо повернути запис, пов'язану з Ki
В іншому випадку, Кі не знайдений серед ключових значень на аркуші, це означає, що в таблиці немає ключів з потрібним значенням.
Обчислювальна складність даної операції в гіршому випадку TFind=O (logb/2n), де b-порядок дерева або коефіцієнт розгалуження; n - кількість елементів у дереві.
Доказ. Пошук елемента в бінарному збалансованому дереві має трудомісткість рівну O (log2n), основна відмінність процесу пошуку в B + дереві в тому, що внутрішній вузол може мати від b / 2 до b дочірніх вузлів (а не обмежується двома). Звідси випливає, що в гіршому випадку обчислювальна складність пошуку в B + дереві буде дорівнювати TFind=O (logb/2n).
Приклад пошуку елемента з ключем рівним 3 (Рис.2):
.2 Вставка записи
Процес додавання запису в B +-дерево аналогічний, як і в інших пошукових деревах: нова запис завжди вставляється в один з кінцевих вузлів. Складність додає те, що вставка може переповнити листової вузол. Коли такі ситуації трапляються, в B +-дерево на тому ж рівні, що й інші кінцеві вузли, додається новий листовий вузол. Кроки для вставки в B +-дерева:
Пошук позиції для додавання нового елемента.
Вставка в знайдений лист L:
Якщо L не повний, то запис просто створюється.
Якщо L повний, то в B +-дерево вводиться новий листовий вузол Lnew, як правий брат L. Ключі в L, разом з новим елементом, розподіляються рівномірно серед L і Lnew. Lnew вставляється в зв'язаний список кінцевих вузлів праворуч від L. Тепер ми повинні пов'язати Lnew c деревом при цьому Lnew повинен бути рідним братом для L. Найменший ключ з Lnew буде скопійований і вставлений в батько L - який також буде батьком Lnew. Весь цей крок відомий як поділ листового вузла.
Якщо батьківський вузол P заповнений, то він розділяється в свою чергу. Однак цей поділ внутрішнього вузла трохи відрізняється. Ключі вузла Р і нова запис повинні бути рівномірно розподілені. Нової вузол повинен бути введений в якості брата Р при цьому, середній ключ переміщається вище вузла (не буде копіюватися!). Це розщеплення вузлів може тривати вгору по дереву від кореня.
Коли ключ додається в повний корінь, то корінь розщеплюється на два, а середній ключ стає новим коренем. Це єдиний спосіб для B +-дерева рости в висоту.
Обчислювальна складність даної операції в гіршому випадку TInsert=O (logb/2n), де b - порядок дерева або коефіцієнт розгалуження; n - кількість елементів у дереві.
Доказ. Пошук місця для вставки має таку ж обчислювальну складність ...
