B Дерево в структурі даних: пошук, вставка, видалення

Що таке дерево B?

B Дерево — це самобалансуюча структура даних, що базується на певному наборі правил для пошуку, вставки та видалення даних швидшим та ефективнішим з точки зору використання пам'яті способом. Для досягнення цієї мети для створення B-дерева дотримуються наступних правил.

B-дерево – це особливий тип дерева в структурі даних. У 1972 році цей метод вперше представили МакКрейт і Байєр, які назвали його «Висотно-збалансоване m-стороннє дерево пошуку». Воно допомагає зберігати відсортовані дані та дозволяє виконувати різні операції, такі як вставка, пошук і видалення, за менший час.

Правила для B-Tree

Ось важливі правила для створення B-дерева:

• Усі листочки будуть створені на одному рівні.
• B-дерево визначається певним числом ступенів, який також називають «порядком» (визначається зовнішнім актором, таким як програміст), що називається m далі. Значення m залежить від розміру блоку на диску, на якому в основному розташовані дані.
• Ліве піддерево вузла матиме менші значення, ніж права сторона піддерева. Це означає, що вузли також сортуються в порядку зростання зліва направо.
• Максимальна кількість ключів, яку може містити кореневий вузол, а також його дочірні вузли, розраховується за цією формулою: m − 1, Наприклад:

  m = 4
  max keys: 4 − 1 = 3

• Кожен вузол, крім кореневого, повинен містити мінімальну кількість ключів [m/2] − 1, Наприклад:

  m = 4
  min keys: 4/2 − 1 = 1

• Максимальна кількість дочірніх вузлів, які може мати вузол, дорівнює його ступеня, тобто m.
• Мінімальна дочірня кількість, яку може мати вузол, становить половину порядку, тобто m/2 (береться максимальне значення).
• Усі ключі у вузлі сортуються в порядку зростання.

Навіщо використовувати B-Tree

Ось причини для використання B-дерева:

• Зменшує кількість операцій зчитування з диска.
• B-дерева можна легко оптимізувати для налаштування їхнього розміру (тобто кількості дочірніх вузлів) відповідно до розміру диска.
• Це спеціально розроблена техніка для роботи з великою кількістю даних.
• Це корисний алгоритм для баз даних і файлових систем.
• Гарний вибір, коли справа доходить до читання та запису великих блоків даних.

Історія B Tree

• Дані зберігаються на диску блоками. Ці дані, коли вони переносяться в основну пам'ять (або оперативну пам'ять), називаються структурою даних.
• У випадку величезних обсягів даних, пошук одного запису на диску вимагає зчитування всього диска; це збільшує час та споживання основної пам'яті через високу частоту звернення до диска та розмір даних.
• Щоб подолати це, створюються індексні таблиці, які зберігають посилання на записи на основі блоків, у яких вони знаходяться. Це значно зменшує споживання часу та пам'яті.
• Оскільки ми маємо величезні дані, ми можемо створювати багаторівневі таблиці індексів.
• Багаторівневий індекс можна розробити за допомогою B-дерева для зберігання.ping дані відсортовані самобалансуючим способом.

Пошук Operaції

Операція пошуку є найпростішою операцією на B-дереві. Застосовується наступний алгоритм:

• Нехай ключ (значення), яке потрібно знайти, буде «k».
• Почніть пошук із кореня та рекурсивно переходьте вниз.
• Якщо k менше за значення кореня, пошук виконується в лівому піддереві; якщо k більше за значення кореня, пошук виконується в правому піддереві.
• Якщо вузол має знайдене k, просто поверніть вузол.
• Якщо k не знайдено у вузлі, перейдіть до дочірнього елемента з більшим ключем.
• Якщо k не знайдено в дереві, ми повертаємо NULL.

Insert Operaції

Оскільки B-дерево є самобалансуючим деревом, ви не можете примусово вставити ключ у будь-який вузол. Застосовується наступний алгоритм:

• Запустіть операцію пошуку та знайдіть відповідне місце вставки.
• Вставте новий ключ у належне місце, але якщо вузол уже має максимальну кількість ключів:
• Вузол разом із щойно вставленим ключем відокремиться від середнього елемента.
• Середній елемент стане батьківським для двох інших дочірніх вузлів.
• Вузли повинні переставити ключі в порядку зростання.

У наведеному вище прикладі:

• Знайдіть відповідну позицію у вузлі для ключа.
• Вставте ключ у цільовий вузол та перевірте наявність правил.
• Після вставки, чи має вузол більше або дорівнює мінімальній кількості ключів, яка дорівнює 1? У цьому випадку так, має. Перевірте наступне правило.
• Після вставки, чи має вузол більше максимальної кількості ключів, яка дорівнює 3? У цьому випадку ні, немає. Це означає, що B-дерево не порушує жодних правил, і вставку завершено.

У наведеному вище прикладі:

• Вузол досяг максимальної кількості ключів.
• Вузол розділиться, і середній ключ стане кореневим вузлом для решти двох вузлів.
• У випадку парної кількості ключів, середній вузол буде вибрано за допомогою лівого або правого зміщення.

У наведеному вище прикладі:

• Вузол має менше ніж максимальна кількість ключів.
• 1 вставляється поруч із 3, але правило зростання порушується.
• Щоб виправити це, ключі сортуються.

Аналогічно, 13 та 2 можна легко вставити у вузол, оскільки вони відповідають правилу «менше за максимум ключів» для вузлів.

У наведеному вище прикладі:

• Вузол має ключі, що дорівнюють max ключам.
• Ключ вставлено в цільовий вузол, але це порушує правило максимальної кількості ключів.
• Цільовий вузол розділено, а середній ключ за лівим ухилом тепер є батьківським для нових дочірніх вузлів.
• Нові вузли розташовані в порядку зростання.

Так само, на основі наведених вище правил і випадків, решту значень можна легко вставити в дерево B.

видаляти Operaції

Операція видалення має більше правил, ніж операції вставки та пошуку. Застосовується наступний алгоритм:

• Виконайте операцію пошуку та знайдіть цільовий ключ у вузлах.
• Залежно від розташування цільового ключа застосовуються три умови, як пояснено в наступних розділах.

Якщо цільовий ключ знаходиться в листовому вузлі

• Target знаходиться в кінцевому вузлі, більше ніж min ключів. Видалення цього не порушить властивість B-дерева.
• Target знаходиться в кінцевому вузлі та має min ключових вузлів. Видалення цього порушить властивість B-дерева.
• Цільовий вузол може позичити ключ у безпосереднього лівого вузла або безпосереднього правого вузла (брата).
• Брат скаже так якщо він має більше мінімальної кількості ключів.
• Ключ буде запозичено з батьківського вузла, максимальне значення буде передано батьківському вузлу, максимальне значення батьківського вузла буде передано цільовому вузлу, а цільове значення буде видалено.
• Target знаходиться в кінцевому вузлі, але жоден з братів і сестер не має більше мінімальної кількості ключів: пошук ключа, об'єднання з братами і сестрами та мінімальною кількістю батьківських вузлів, загальна кількість ключів тепер буде більше min, а цільовий ключ буде замінено мінімальним ключем батьківського вузла.

Якщо цільовий ключ знаходиться у внутрішньому вузлі

• Виберіть або попередника за порядком, або наступника за порядком.
• У випадку попередника в порядку порядку буде вибрано максимальний ключ з його лівого піддерева.
• У випадку наступника в порядку порядку буде вибрано мінімальний ключ з його правого піддерева.
• Тільки якщо попередник цільового ключа за порядком має більше ключів, ніж мінімальна кількість, то цільовий ключ може замінити ключем максимального значення попередника за порядком.
• Якщо попередник цільового ключа за порядком не має більше ніж min ключів, шукайте мінімальний ключ наступника за порядком.
• Якщо порядковий попередник і наступник цільового ключа мають менше ніж min ключів, тоді об’єднайте попередника та наступника.

Якщо цільовий ключ знаходиться в кореневому вузлі

• Замініть максимальним елементом піддерева-попередника за порядком.
• Якщо після видалення цільовий вузол має менше ніж min ключів, то цільовий вузол запозичить максимальне значення у свого брата через батьківського вузла брата.
• Максимальне значення батьківського елемента буде взято цільовим елементом, але з вузлами максимального значення рідного елемента.

Тепер розберемо операцію видалення на прикладі.

Наведена вище діаграма показує різні випадки операції видалення в B-дереві. Це B-дерево має порядок 5, що означає, що мінімальна кількість дочірніх вузлів, які може мати будь-який вузол, дорівнює 3, а максимальна кількість дочірніх вузлів, які може мати будь-який вузол, дорівнює 5. Тоді як мінімальна та максимальна кількість ключів, які може мати будь-який вузол, дорівнюють 2 та 4 відповідно.

У наведеному вище прикладі:

• Цільовий вузол має цільовий ключ для видалення.
• Цільовий вузол має більше ключів, ніж мінімальна кількість ключів.
• Просто видаліть ключ.

У наведеному вище прикладі:

• Цільовий вузол має ключі, що дорівнюють мінімальній кількості ключів, тому ми не можемо видалити його безпосередньо, оскільки це порушить умови.

Тепер на наступній схемі пояснюється, як видалити цей ключ:

• Цільовий вузол позичить ключ у безпосереднього брата, у цьому випадку, попередника за порядком (лівого брата), оскільки у нього немає наступника за порядком (правого брата).
• Максимальне значення попередника в порядку порядку буде передано батьківському вузлу, а батьківський вузол передасть максимальне значення цільовому вузлу (див. діаграму нижче).

У наведеному нижче прикладі показано, як видалити ключ, який потребує значення, із його наступника за порядком.

• Цільовий вузол позичить ключ у безпосереднього брата, у цьому випадку, у наступника за порядком (правого брата), оскільки його попередник за порядком (лівого брата) має ключі, що дорівнюють мінімальній кількості ключів.
• Мінімальне значення наступника за порядком буде передано батьківському вузлу, а батьківський вузол передасть максимальне значення цільовому вузлу.

У наведеному нижче прикладі цільовий вузол не має жодного брата/сестри, який може передати свій ключ цільовому вузлу. Тому потрібне об'єднання. Див. процедуру видалення такого ключа:

• Об'єднайте цільовий вузол з будь-яким із його безпосередніх братів і сестер разом з батьківським ключем.
• Вибирається ключ з батьківського вузла, який знаходиться між двома вузлами, що об'єднуються.
• Видаліть цільовий ключ з об'єднаного вузла.

видаляти OperaПсевдо Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

вихід: Найбільший елемент видаляється з B-дерева.

Поширені запитання