B ДЕРЕВО в структурі даних: пошук, вставка, видалення OperaПриклад

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

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

• Усі листочки будуть створені на одному рівні.
• 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-Tree

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

Історія B Tree

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

Пошук Operaції

Операція пошуку є найпростішою операцією на дереві B.

Застосовується наступний алгоритм:

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

Insert Operaції

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

Застосовується наступний алгоритм:

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

TIP	Наступне не вірно щодо алгоритму вставки: Оскільки вузол заповнений, він розділиться, а потім буде вставлено нове значення

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

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

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

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

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

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

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

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

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

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

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

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

Застосовується наступний алгоритм:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подивіться процедуру видалення такого ключа:

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

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

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-дерева.

Підсумки

• B Tree — це самобалансуюча структура даних для кращого пошуку, вставки та видалення даних із диска.
• B Дерево регулюється зазначеним ступенем
• B Ключі та вузли дерева розташовані в порядку зростання.
• Операція пошуку B Tree є найпростішою, яка завжди починається з кореня і починає перевіряти, чи цільовий ключ більший або менший за значення вузла.
• Операція вставки B Tree досить детальна, яка спочатку знаходить відповідну позицію вставки для цільового ключа, вставляє його, оцінює валідність B Tree порівняно з різними випадками, а потім відповідно реструктурує вузли B Tree.
• Операція видалення B Tree спочатку шукає цільовий ключ, який потрібно видалити, видаляє його, оцінює дійсність на основі кількох випадків, таких як мінімальний і максимальний ключі цільового вузла, братів і сестер і батьківського вузла.