B + TREE: Приклад операцій пошуку, вставки та видалення

Зміст:

Anonim

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

В + Дерево в основному використовується для реалізації динамічного індексування на декількох рівнях. Порівняно з B-Tree, B + Tree зберігає покажчики даних лише у листових вузлах дерева, що робить пошук більш точним та швидшим.

У цьому підручнику B + Tree ви дізнаєтесь:

  • Що таке дерево B +?
  • Правила для дерева B +
  • Навіщо використовувати B + Tree
  • B + Tree проти B Tree
  • Пошукова операція
  • Операція вставки
  • Видалити операцію

Правила для дерева B +

Ось основні правила для дерева B +.

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

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

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

  • Ключі в основному використовуються для сприяння пошуку, спрямовуючи на відповідний Лист.
  • Дерево B + використовує "коефіцієнт заповнення" для управління збільшенням і зменшенням дерева.
  • У деревах B + численні клавіші можна легко розмістити на сторінці пам’яті, оскільки вони не мають даних, пов’язаних із внутрішніми вузлами. Тому він буде швидко отримувати доступ до деревних даних, що знаходяться на листовому вузлі.
  • Комплексне повне сканування всіх елементів - це дерево, якому потрібно лише один лінійний прохід, оскільки всі листові вузли дерева B + пов’язані між собою.

B + Tree проти B Tree

Ось основні відмінності між B + Tree та B Tree

B + Дерево B Дерево
Клавіші пошуку можна повторити. Клавіші пошуку не можуть бути зайвими.
Дані зберігаються лише на листових вузлах. Як листові, так і внутрішні вузли можуть зберігати дані
Дані, що зберігаються на листовому вузлі, роблять пошук точнішим та швидшим. Пошук повільний через дані, що зберігаються на Leaf та внутрішніх вузлах.
Видалення не становить труднощів, оскільки елемент видаляється лише з листового вузла. Видалення елементів - складний і трудомісткий процес.
Зв’язані листові вузли роблять пошук ефективним і швидким. Ви не можете пов’язати листові вузли.

Пошукова операція

У B + Tree пошук є однією з найпростіших процедур для виконання та отримання з нього швидких і точних результатів.

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

  • Щоб знайти потрібний запис, вам потрібно виконати двійковий пошук по доступних записах у Дереві.
  • У разі точного збігу з ключем пошуку, відповідний запис повертається користувачеві.
  • У випадку, якщо точний ключ не знайдений за допомогою пошуку в батьківському, поточному або листовому вузлі, тоді користувачеві відображається повідомлення "не знайдено".
  • Процес пошуку можна повторити, щоб отримати кращі та точніші результати.

Алгоритм пошукової операції

1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."

Вихід :

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

Операція вставки

Для операції вставки застосовується наступний алгоритм:

  • 50 відсотків елементів у вузлах переміщуються на новий лист для зберігання.
  • Батьки нового Leaf точно пов’язані з мінімальним значенням ключа та новим місцем у дереві.
  • Розділіть батьківський вузол на більше місць, якщо він буде повністю використаний.
  • Тепер для кращих результатів центральна клавіша пов’язана з вузлом верхнього рівня цього аркуша.
  • Поки вузол верхнього рівня не знайдено, продовжуйте повторювати процес, описаний у вищевказаних кроках.

Вставте алгоритм операції

1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. Else, divide the node into more locations to fit more records.a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the treeb. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.c. Divide the top-level node if it gets full of keys and addresses.i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore.3) Build a new top-level root node of 1 Key and 2 indicators.

Вихід :

Алгоритм визначить елемент і успішно вставить його у необхідний листовий вузол.

Наведений вище приклад зразка дерева B + пояснюється наведеними нижче кроками:

  • По-перше, у нас є 3 вузли, і перші 3 елементи, які є 1, 4 та 6, додаються у відповідні місця у вузлах.
  • Наступне значення в серії даних - 12, яке потрібно зробити частиною дерева.
  • Для цього розділіть вузол, додайте 6 як елемент покажчика.
  • Тепер створюється права ієрархія дерева, а інші значення даних коригуються відповідним чином, маючи на увазі відповідні правила, рівні або більші за значення щодо вузлів ключ-значення праворуч.

Видалити операцію

Складність процедури видалення в дереві B + перевершує складність функцій вставки та пошуку.

Наступний алгоритм застосовується під час видалення елемента з дерева B +:

  • По-перше, нам потрібно знайти запис листа на дереві, який утримує клавішу та вказівник. , видаліть запис листа з дерева, якщо лист відповідає точним умовам видалення запису.
  • Якщо листовий вузол відповідає лише задовільному коефіцієнту наполовину заповненості, тоді операція завершена; інакше вузол Leaf має мінімум записів і його не можна видалити.
  • Інші пов'язані вузли праворуч і ліворуч можуть звільнити будь-які записи, а потім перемістити їх до аркуша. Якщо ці критерії не виконуються, вони повинні поєднувати листовий вузол та пов'язаний вузол у ієрархії дерева.
  • При об'єднанні листового вузла з сусідами праворуч або ліворуч записи значень у вузлі листа або пов'язаного сусіда, що вказують на вузол верхнього рівня, видаляються.

Наведений вище приклад ілюструє процедуру видалення елемента з дерева B + певного порядку.

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

  • У наведеному вище прикладі ми повинні видалити 31 з дерева.
  • Нам потрібно знайти екземпляри 31 в Index та Leaf.
  • Ми бачимо, що 31 доступний як на індексі, так і на рівні вузла Leaf. Отже, ми видаляємо його з обох примірників.
  • Але нам потрібно заповнити індекс, що вказує на 42. Тепер ми розглянемо потрібну дитину віком до 25 років і візьмемо мінімальне значення та розмістимо його як індекс. Отже, будучи єдиним значенням 42, він стане індексом.

Видалити алгоритм операції

1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) If n has at least ceil(m/2) keys, done!ii) If n has less than ceil(m/2) keys,If a sibling can lend a key,Borrow key from the sibling and adjust keys in n and the parent nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node

Вихід :

Ключ "K" видаляється, а ключі запозичуються у братів і сестер для коригування значень в n та його батьківських вузлах, якщо це необхідно.

Короткий зміст:

  • B + Tree - це самобалансуюча структура даних для виконання точного та швидшого пошуку, вставки та видалення процедур даних
  • Ми можемо легко отримати повні дані або часткові дані, оскільки перегляд пов'язаної деревної структури робить її ефективною.
  • Структура дерева B + зростає і зменшується зі збільшенням / зменшенням кількості збережених записів.
  • Зберігання даних на листових вузлах і подальше розгалуження внутрішніх вузлів, очевидно, скорочує висоту дерева, що зменшує операції введення та виведення диска, в кінцевому підсумку споживаючи набагато менше місця на запам'ятовуючих пристроях.