У наступному посібнику ми дізнаємося про структуру даних B Tree і розглянемо її візуалізацію.

Отже, почнемо.

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

The B Дерево це спеціальний тип багатостороннього дерева пошуку , широко відомий як М-шлях дерево, яке врівноважує себе. Завдяки своїй збалансованій структурі ці дерева зазвичай використовуються для роботи та керування величезними базами даних і спрощення пошуку. У B-дереві кожен вузол може мати щонайбільше n дочірніх вузлів. B Tree є прикладом багаторівневого індексування в системі керування базами даних (СУБД). Листові та внутрішні вузли матимуть посилання на записи. Дерево B відоме як збалансоване збережене дерево, оскільки всі листкові вузли знаходяться на одному рівні.

Наступна діаграма є прикладом B-дерева:

Фігура 1. A B Дерево з порядком 3

екземпляр java

Розуміння правил дерева B

Нижче наведено важливі властивості B-дерева:

1. Всі листкові вузли знаходяться на одному рівні.
2. Структура даних B Tree визначається терміном мінімального ступеня 'd'. Значення 'd' залежить від розміру дискового блоку.
3. Кожен вузол, за винятком кореня, повинен складатися щонайменше з d-1 ключів. Кореневий вузол може складатися мінімум з 1 ключа.
4. Усі вузли (включаючи кореневий вузол) можуть складатися щонайбільше з (2d-1) ключі.
5. Кількість дітей вузла дорівнює додавання кількості присутніх у ньому ключів і .
6. Усі ключі вузла сортуються в порядку зростання. Дочірній елемент між двома ключами, k1 і k2, складається з усіх ключів між k1 і k2 відповідно.
7. На відміну від бінарного дерева пошуку, структура даних дерева B зростає та зменшується від кореня. Тоді як бінарне дерево пошуку росте донизу та зменшується донизу.
8. Подібно до інших самозбалансованих бінарних дерев пошуку, часова складність структури даних дерева B для таких операцій, як пошук, вставка та видалення, становить O(log?n) .
9. Вставлення вузла в B-дерево відбувається лише в листовому вузлі.

Розглянемо наступний приклад B-дерева мінімального порядку 5.

малюнок 2. A B Дерево порядку 5

Примітка: вартість мінімального замовлення значно перевищує 5 у практичних B Trees.

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

Формулювання набору правил B Tree:

Кожне B-дерево залежить від позитивного постійного цілого числа, відомого як МІНІМУМ , який використовується для визначення кількості елементів даних, які можуть зберігатися в одному вузлі.

Правило 1: Корінь може мати лише один елемент даних (або навіть не мати елементів даних, якщо він також не є нащадками); кожен інший вузол має принаймні МІНІМУМ елементи даних.

Правило 2: Максимальна кількість елементів даних, що зберігаються у вузлі, дорівнює подвоєному значенню МІНІМУМ .

Правило 3: Елементи даних кожного вузла B-дерева зберігаються в частково заповненому масиві, відсортованому від найменшого елемента даних (за індексом 0 ) до найбільшого елемента даних (у кінцевій використаній позиції масиву).

Правило 4: Загальна кількість піддерев під нелистовим вузлом завжди на один більше, ніж кількість елементів даних у цьому вузлі.

• піддерево 0, піддерево 1,...

Правило 5: Стосовно будь-якого нелистового вузла:

1. Елемент даних за індексом більший за всі елементи даних у номері піддерева i вузла, і
2. Елемент даних за індексом менший за всі елементи даних у піддереві i+1 вузла.

Правило 6: Кожен лист у дереві B має однакову глибину. Таким чином, це гарантує, що дерево B запобігає проблемі незбалансованого дерева.

Операції над структурою даних B Tree

Щоб гарантувати, що жодна з властивостей структури даних B Tree не буде порушена під час операцій, B Tree можна розділити або об’єднати. Нижче наведено деякі операції, які ми можемо виконувати з B-деревом:

комісія з підбору персоналу значення

1. Пошук елемента даних у дереві B
2. Вставка елемента даних у B Tree
3. Видалення елемента даних у дереві B

Операція пошуку на B-дереві

Пошук елемента в B-дереві схожий на пошук у бінарному дереві пошуку. Але замість прийняття двостороннього рішення (ліворуч або праворуч), як у двійковому дереві пошуку, B-дерево приймає m-стороннє рішення на кожному вузлі, де m є кількістю дочірніх елементів вузла.

Кроки для пошуку елемента даних у B-дереві:

Крок 1: Пошук починається з кореневого вузла. Порівняйте пошуковий елемент k з коренем.

Крок 1.1: Якщо кореневий вузол складається з елемента k, пошук буде завершено.

Крок 1.2: Якщо елемент k менший за перше значення в корені, ми перемістимося до крайнього лівого дочірнього елемента та шукатимемо дочірній елемент рекурсивно.

Крок 1.3.1: Якщо корінь має лише двох дочірніх елементів, ми перемістимося до крайнього правого дочірнього елемента та рекурсивно шукатимемо дочірні вузли.

Крок 1.3.2: Якщо корінь має більше двох ключів, ми шукатимемо решту.

Крок 2: Якщо елемент k не знайдено після обходу всього дерева, тоді пошуковий елемент відсутній у дереві B.

Давайте візуалізуємо описані вище кроки за допомогою прикладу. Припустімо, що ми хочемо знайти ключ k=34 у наступному дереві B:

Малюнок 3.1. Дане B дерево

1. По-перше, ми перевіримо, чи ключ k = 34 знаходиться в кореневому вузлі. Оскільки ключ знаходиться не в корені, ми перейдемо до його дочірніх вузлів. Ми також можемо помітити, що кореневий вузол має двох дітей; тому ми порівняємо необхідне значення між двома ключами.
   
   Малюнок 3.2. Ключ k відсутній у корені
2. Тепер, коли ми можемо помітити, що ключ k більший за кореневий вузол, тобто 30, ми продовжимо з правим дочірнім елементом кореня.
   
   Малюнок 3.3. Клавіша k > 30, перехід до правого дочірнього елемента
3. Тепер ми порівняємо ключ k зі значеннями, присутніми на вузлі, тобто 40 і 50 відповідно. Оскільки ключ k менший за лівий ключ, тобто 40, ми перейдемо до лівого дочірнього елемента вузла.
   
   Малюнок 3.4. Ключ к<40, move to left child< li>
4. Оскільки значення лівого дочірнього елемента 40 дорівнює 34, що є необхідним значенням, ми можемо зробити висновок, що ключ знайдено, і операцію пошуку завершено.
   
   Малюнок 3.4. Ключ k = 34, лівий дочірній елемент 40

Ми порівнювали ключ із чотирма різними значеннями у наведеному вище прикладі, поки не знайшли його. Таким чином, час, необхідний для операції пошуку в B-дереві, становить O(log?n) .

Вставлення операції в дерево B

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

Вузол не містить більше МАКСИМАЛЬНОЇ кількості ключів -Ми вставимо ключ у вузол у належне місце.Вузол складається з МАКСИМАЛЬНОЇ кількості ключів -Ми вставимо ключ до повного вузла, а потім відбудеться операція розділення, розбиваючи повний вузол на три частини. Другий або середній ключ переміститься до батьківського вузла, а перша і третя частини діятимуть як лівий і правий дочірні вузли відповідно. Цей процес буде повторено з батьківським вузлом, якщо він також складається з МАКСИМАЛЬНОЇ кількості ключів.

Кроки, щоб вставити елемент даних у B-дерево:

Крок 1: Ми почнемо з розрахунку максимальної кількості ключів у вузлі на основі порядку B-дерева.

кортеж python відсортовано

Крок 2: Якщо дерево порожнє, виділяється кореневий вузол, і ми вставимо ключ, який діє як кореневий вузол.

крок 3: Тепер ми шукатимемо відповідний вузол для вставки.

крок 4: Якщо вузол заповнений:

Крок 4.1: Ми вставимо елементи даних у порядку зростання.

Крок 4.2: Якщо кількість елементів даних перевищує максимальну кількість ключів, ми розділимо повний вузол по медіані.

Крок 4.3: Ми підштовхнемо середню клавішу вгору та розділимо ліву та праву клавіші як ліву та праву дочірню частину.

крок 5: Якщо вузол не заповнений, ми вставимо вузол у порядку зростання.

Давайте візуалізуємо описані вище кроки за допомогою прикладу. Припустімо, що нам потрібно створити B Tree порядку 4. Елементи даних, які потрібно вставити в B Tree: 5,3,21,11,1,16,8,13,4 і 9 .

1. Оскільки m дорівнює 3, максимальна кількість ключів для вузла = m-1 = 3-1 = 2 .
2. Почнемо зі вставки 5 в порожньому дереві.
   
   Малюнок 4.1. Вставка 5
3. Тепер ми вставимо 3 у дерево. Оскільки 3 менше 5, ми вставимо 3 ліворуч від 5 у той самий вузол.
   
   Малюнок 4.2. Вставка 3
4. Тепер ми вставимо 21 у дерево, а оскільки 21 більше за 5, воно буде вставлено праворуч від 5 у тому самому вузлі. Однак, оскільки ми знаємо, що максимальна кількість ключів у вузлі становить 2, один із цих ключів буде переміщено до вузла вище, щоб розділити його. Таким чином, 5, середній елемент даних, переміститься вгору, а 3 і 21 стануть його лівим і правим вузлами відповідно.
   
   Малюнок 4.3. Вставка 21
5. Тепер настав час вставити наступний елемент даних, тобто 11, який більше за 5, але менше за 21. Тому 11 буде вставлено як ключ ліворуч від вузла, що складається з 21 як ключа.
   
   Малюнок 4.4. Вставка 11
6. Подібним чином ми вставимо наступний елемент даних 1 у дерево, і, як ми бачимо, 1 менше 3; отже, він буде вставлений як ключ ліворуч від вузла, що складається з 3 як ключ.
   
   Малюнок 4.5. Вставка 1
7. Тепер ми вставимо в дерево елемент даних 16, який перевищує 11, але менше 21. Однак кількість ключів у цьому вузлі перевищує максимальну кількість ключів. Тому вузол розділиться, перемістивши середній ключ до кореня. Таким чином, 16 буде вставлено праворуч від 5, розділяючи 11 і 21 на два окремих вузла.
   
   Малюнок 4.6. Вставка 16
8. Елемент даних 8 буде вставлено як ключ ліворуч від 11.
   
   Малюнок 4.7. Вставка 8
9. Ми вставимо в дерево 13, яке менше за 16 і більше за 11. Тому елемент даних 13 слід вставити праворуч від вузла, що складається з 8 і 11. Однак, оскільки максимальна кількість ключів у дереві може буде тільки 2, відбудеться розбиття, переміщення середнього елемента даних 11 до вищезгаданого вузла, а 8 і 13 — до двох окремих вузлів. Тепер вищевказаний вузол складатиметься з 5, 11 і 16, що знову перевищує максимальну кількість ключів. Таким чином, буде ще один розкол, що зробить елемент даних 11 кореневим вузлом з 5 і 16 його дочірніми вузлами.
   
   Малюнок 4.8. Вставка 13
10. Оскільки елемент даних 4 менший за 5, але більший за 3, він буде вставлений праворуч від вузла, що складається з 1 і 3, що знову перевищить максимальну кількість ключів у вузлі. Таким чином, розлив відбудеться знову, перемістивши 3 у верхній вузол поруч із 5.
    
    Малюнок 4.9. Вставка 4
11. Нарешті, елемент даних 9, який більше 8, але менше 11, буде вставлено праворуч від вузла, що складається з 8, як ключ.
    
    Малюнок 4.10. Вставка 9

У наведеному вище прикладі ми виконали різні порівняння. Перше значення було безпосередньо вставлено в дерево; після цього кожне значення потрібно було порівняти з вузлами, доступними в цьому дереві. Часова складність операції вставки в B-дерево залежить від кількості вузлів і .

Видалення операції на дереві B

Видалення елемента даних у B-дереві містить три основні події:

1. Пошук вузла, де існує ключ, який потрібно видалити,
2. Видалення ключа і

• Балансування дерева, якщо необхідно.

Під час видалення елемента з дерева може виникнути стан, відомий як Underflow. Недостатнє переповнення виникає, коли вузол складається з менш ніж мінімальної кількості ключів; це повинно триматися.

Нижче наведено деякі терміни, які необхідно зрозуміти перед візуалізацією операції видалення/видалення:

Попередник у порядку:Найважливіший ключ лівого дочірнього елемента вузла відомий як його порядковий попередник.Наступник по порядку:Додатковий ключ правого дочірнього вузла відомий як його наступник за порядком.

Нижче наведено три відомі випадки операції видалення в B-дереві:

Випадок 1: видалення/видалення ключа лежить у листовому вузлі - Далі цей випадок поділяється на два різні випадки:

1. Видалення/видалення ключа не порушує властивість мінімальної кількості ключів, яку повинен містити вузол.

Давайте візуалізуємо цей випадок на прикладі, коли ми видалимо ключ 32 з наступного дерева B.

список масивів Java

Малюнок 4.1: Видалення ключа кінцевого вузла (32) з B-дерева

Як ми можемо помітити, видалення 32 із цього дерева не порушує наведену вище властивість.

2. Видалення/видалення ключа порушує властивість мінімальної кількості ключів, яку повинен містити вузол. У цьому випадку ми повинні запозичити ключ від його найближчого вузла-брата в порядку зліва направо.

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

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

Давайте тепер візуалізуємо цей випадок за допомогою прикладу, де ми видалимо 31 із вищевказаного дерева B. У цьому випадку ми запозичимо ключ від лівого однорідного вузла.

Малюнок 4.2: Видалення ключа кінцевого вузла (31) з B-дерева

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

Давайте візуалізуємо знову, видаливши ключ 30 із вищевказаного дерева B.

Малюнок 4.3: Видалення ключа кінцевого вузла (30) з дерева B

Випадок 2: Видалення/видалення ключа знаходиться у нелистовому вузлі - Цей випадок далі поділяється на різні випадки:

1. Видалений вузол, який не є Leaf/Internal, замінюється попередником у порядку, якщо лівий дочірній вузол має більше ніж мінімальна кількість ключів.

Давайте візуалізуємо цей випадок на прикладі, коли ми видалимо ключ 33 з дерева B.

Малюнок 4.4: Видалення ключа кінцевого вузла (33) з B-дерева

2. Видалений вузол, який не є Leaf/Internal, замінюється наступним за порядком, якщо правий дочірній вузол має більше ніж мінімальна кількість ключів.

Якщо будь-який із дочірніх елементів має мінімальну кількість ключів, тоді ми об’єднаємо лівий і правий дочірні вузли.

Давайте візуалізуємо цей випадок, видаливши ключ 30 з дерева B.

list.sort java

Малюнок 4.5: Видалення ключа кінцевого вузла (30) з B-дерева

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

Випадок 3: У наступному випадку висота дерева зменшується. Якщо цільовий ключ знаходиться у внутрішньому вузлі, і видалення ключа призводить до меншої кількості ключів у вузлі (що є меншим за мінімально необхідний), тоді шукайте попередника за порядком і наступника за порядком. Якщо обидва діти мають мінімальну кількість ключів, то запозичення не може відбутися. Це призводить до Випадок 2(3) , тобто об’єднання дочірніх вузлів.

Ми знову будемо шукати брата чи сестру, щоб позичити ключ. Однак, якщо братський вузол також складається з мінімальної кількості ключів, тоді ми об’єднаємо вузол із братським вузлом разом із батьківським вузлом і розташуємо дочірні вузли відповідно до вимог (у порядку зростання).

Давайте візуалізуємо цей випадок за допомогою прикладу, де ми видалимо елемент даних 10 із заданого дерева B.

Малюнок 4.6: Видалення ключа кінцевого вузла (10) з B-дерева

Часова складність у наведених вище прикладах залежить від місця, звідки потрібно видалити ключ. Таким чином, часова складність для операції видалення в B-дереві становить O(log?n) .

Висновок

У цьому підручнику ми дізналися про дерево B і візуалізували його різні операції на різних прикладах. Ми також зрозуміли деякі фундаментальні властивості та правила B Tree.