У наступному посібнику ми дізнаємося про структуру даних B Tree і розглянемо її візуалізацію.
Отже, почнемо.
Що таке дерево B?
The B Дерево це спеціальний тип багатостороннього дерева пошуку , широко відомий як М-шлях дерево, яке врівноважує себе. Завдяки своїй збалансованій структурі ці дерева зазвичай використовуються для роботи та керування величезними базами даних і спрощення пошуку. У B-дереві кожен вузол може мати щонайбільше n дочірніх вузлів. B Tree є прикладом багаторівневого індексування в системі керування базами даних (СУБД). Листові та внутрішні вузли матимуть посилання на записи. Дерево B відоме як збалансоване збережене дерево, оскільки всі листкові вузли знаходяться на одному рівні.
Наступна діаграма є прикладом B-дерева:
Фігура 1. A B Дерево з порядком 3
екземпляр java
Розуміння правил дерева B
Нижче наведено важливі властивості B-дерева:
- Всі листкові вузли знаходяться на одному рівні.
- Структура даних B Tree визначається терміном мінімального ступеня 'd'. Значення 'd' залежить від розміру дискового блоку.
- Кожен вузол, за винятком кореня, повинен складатися щонайменше з d-1 ключів. Кореневий вузол може складатися мінімум з 1 ключа.
- Усі вузли (включаючи кореневий вузол) можуть складатися щонайбільше з (2d-1) ключі.
- Кількість дітей вузла дорівнює додавання кількості присутніх у ньому ключів і .
- Усі ключі вузла сортуються в порядку зростання. Дочірній елемент між двома ключами, k1 і k2, складається з усіх ключів між k1 і k2 відповідно.
- На відміну від бінарного дерева пошуку, структура даних дерева B зростає та зменшується від кореня. Тоді як бінарне дерево пошуку росте донизу та зменшується донизу.
- Подібно до інших самозбалансованих бінарних дерев пошуку, часова складність структури даних дерева B для таких операцій, як пошук, вставка та видалення, становить O(log?n) .
- Вставлення вузла в B-дерево відбувається лише в листовому вузлі.
Розглянемо наступний приклад B-дерева мінімального порядку 5.
малюнок 2. A B Дерево порядку 5
Примітка: вартість мінімального замовлення значно перевищує 5 у практичних B Trees.
На наведеній вище діаграмі ми можемо помітити, що всі листові вузли знаходяться на одному рівні, а всі нелистові вузли не мають порожнього піддерева і складаються з ключів, на один менше, ніж кількість їх дочірніх елементів.
Формулювання набору правил B Tree:
Кожне B-дерево залежить від позитивного постійного цілого числа, відомого як МІНІМУМ , який використовується для визначення кількості елементів даних, які можуть зберігатися в одному вузлі.
Правило 1: Корінь може мати лише один елемент даних (або навіть не мати елементів даних, якщо він також не є нащадками); кожен інший вузол має принаймні МІНІМУМ елементи даних.
Правило 2: Максимальна кількість елементів даних, що зберігаються у вузлі, дорівнює подвоєному значенню МІНІМУМ .
Правило 3: Елементи даних кожного вузла B-дерева зберігаються в частково заповненому масиві, відсортованому від найменшого елемента даних (за індексом 0 ) до найбільшого елемента даних (у кінцевій використаній позиції масиву).
Правило 4: Загальна кількість піддерев під нелистовим вузлом завжди на один більше, ніж кількість елементів даних у цьому вузлі.
- піддерево 0, піддерево 1,...
Правило 5: Стосовно будь-якого нелистового вузла:
- Елемент даних за індексом більший за всі елементи даних у номері піддерева i вузла, і
- Елемент даних за індексом менший за всі елементи даних у піддереві i+1 вузла.
Правило 6: Кожен лист у дереві B має однакову глибину. Таким чином, це гарантує, що дерево B запобігає проблемі незбалансованого дерева.
Операції над структурою даних B Tree
Щоб гарантувати, що жодна з властивостей структури даних B Tree не буде порушена під час операцій, B Tree можна розділити або об’єднати. Нижче наведено деякі операції, які ми можемо виконувати з B-деревом:
комісія з підбору персоналу значення
- Пошук елемента даних у дереві B
- Вставка елемента даних у B Tree
- Видалення елемента даних у дереві 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 дерево
- По-перше, ми перевіримо, чи ключ k = 34 знаходиться в кореневому вузлі. Оскільки ключ знаходиться не в корені, ми перейдемо до його дочірніх вузлів. Ми також можемо помітити, що кореневий вузол має двох дітей; тому ми порівняємо необхідне значення між двома ключами.
Малюнок 3.2. Ключ k відсутній у корені - Тепер, коли ми можемо помітити, що ключ k більший за кореневий вузол, тобто 30, ми продовжимо з правим дочірнім елементом кореня.
Малюнок 3.3. Клавіша k > 30, перехід до правого дочірнього елемента - Тепер ми порівняємо ключ k зі значеннями, присутніми на вузлі, тобто 40 і 50 відповідно. Оскільки ключ k менший за лівий ключ, тобто 40, ми перейдемо до лівого дочірнього елемента вузла.
Малюнок 3.4. Ключ к<40, move to left child< li> - Оскільки значення лівого дочірнього елемента 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 .
- Оскільки m дорівнює 3, максимальна кількість ключів для вузла = m-1 = 3-1 = 2 .
- Почнемо зі вставки 5 в порожньому дереві.
Малюнок 4.1. Вставка 5 - Тепер ми вставимо 3 у дерево. Оскільки 3 менше 5, ми вставимо 3 ліворуч від 5 у той самий вузол.
Малюнок 4.2. Вставка 3 - Тепер ми вставимо 21 у дерево, а оскільки 21 більше за 5, воно буде вставлено праворуч від 5 у тому самому вузлі. Однак, оскільки ми знаємо, що максимальна кількість ключів у вузлі становить 2, один із цих ключів буде переміщено до вузла вище, щоб розділити його. Таким чином, 5, середній елемент даних, переміститься вгору, а 3 і 21 стануть його лівим і правим вузлами відповідно.
Малюнок 4.3. Вставка 21 - Тепер настав час вставити наступний елемент даних, тобто 11, який більше за 5, але менше за 21. Тому 11 буде вставлено як ключ ліворуч від вузла, що складається з 21 як ключа.
Малюнок 4.4. Вставка 11 - Подібним чином ми вставимо наступний елемент даних 1 у дерево, і, як ми бачимо, 1 менше 3; отже, він буде вставлений як ключ ліворуч від вузла, що складається з 3 як ключ.
Малюнок 4.5. Вставка 1 - Тепер ми вставимо в дерево елемент даних 16, який перевищує 11, але менше 21. Однак кількість ключів у цьому вузлі перевищує максимальну кількість ключів. Тому вузол розділиться, перемістивши середній ключ до кореня. Таким чином, 16 буде вставлено праворуч від 5, розділяючи 11 і 21 на два окремих вузла.
Малюнок 4.6. Вставка 16 - Елемент даних 8 буде вставлено як ключ ліворуч від 11.
Малюнок 4.7. Вставка 8 - Ми вставимо в дерево 13, яке менше за 16 і більше за 11. Тому елемент даних 13 слід вставити праворуч від вузла, що складається з 8 і 11. Однак, оскільки максимальна кількість ключів у дереві може буде тільки 2, відбудеться розбиття, переміщення середнього елемента даних 11 до вищезгаданого вузла, а 8 і 13 — до двох окремих вузлів. Тепер вищевказаний вузол складатиметься з 5, 11 і 16, що знову перевищує максимальну кількість ключів. Таким чином, буде ще один розкол, що зробить елемент даних 11 кореневим вузлом з 5 і 16 його дочірніми вузлами.
Малюнок 4.8. Вставка 13 - Оскільки елемент даних 4 менший за 5, але більший за 3, він буде вставлений праворуч від вузла, що складається з 1 і 3, що знову перевищить максимальну кількість ключів у вузлі. Таким чином, розлив відбудеться знову, перемістивши 3 у верхній вузол поруч із 5.
Малюнок 4.9. Вставка 4 - Нарешті, елемент даних 9, який більше 8, але менше 11, буде вставлено праворуч від вузла, що складається з 8, як ключ.
Малюнок 4.10. Вставка 9
У наведеному вище прикладі ми виконали різні порівняння. Перше значення було безпосередньо вставлено в дерево; після цього кожне значення потрібно було порівняти з вузлами, доступними в цьому дереві. Часова складність операції вставки в B-дерево залежить від кількості вузлів і .
Видалення операції на дереві B
Видалення елемента даних у B-дереві містить три основні події:
- Пошук вузла, де існує ключ, який потрібно видалити,
- Видалення ключа і
- Балансування дерева, якщо необхідно.
Під час видалення елемента з дерева може виникнути стан, відомий як 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.