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

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

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

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

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

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

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

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

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

B+ Tree проти B Tree

Ось основні відмінності між деревом B+ і деревом B

Пошук Operaції

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

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

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

Пошук Operaції Алгоритм

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

Вихід:

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

Insert Operaції

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

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

Insert Operaції Алгоритм

1.	Even inserting at-least 1 entry into the leaf container does not make it full then add the record  
     2. 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 tree
      b. 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+ Tree пояснюється в наступних кроках:

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

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

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

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

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

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

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

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

видаляти Operaції Алгоритм

1) Start at the root and go up to leaf node containing the key K
2) Find the node n on the path from the root to the leaf node containing K
    A. If n is root, remove K
         a. if root has more than one key, done
         b. if root has only K
            i) if any of its child nodes can lend a node
               Borrow key from the child and adjust child links
            ii) Otherwise merge the children nodes. It will be a new root
         c. If n is an internal node, remove K
            i) 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 node
                    Adjust child links
                Else
                    Merge n with its sibling
                    Adjust child links
         d. If n is a leaf node, remove K
            i) If n has at least ceil(M/2) elements, done!
                In case the smallest key is deleted, push up the next key
            ii) If n has less than ceil(m/2) elements
            If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
            Else
                Merge n and its sibling
                Adjust keys in the parent node

Вихід:

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

Резюме

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