5) B + TREE

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 в качестве элемента указателя.
• Теперь создается правая иерархия дерева, и оставшиеся значения данных корректируются соответствующим образом с учетом применимых правил, равных или превышающих значения для узлов ключ-значение справа.

Удалить операцию

Приведенный выше пример иллюстрирует процедуру удаления элемента из дерева B + определенного порядка.

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

• В приведенном выше примере мы должны удалить 31 из дерева.
• Нам нужно найти экземпляры 31 в Index и Leaf.
• Мы видим, что 31 доступен как на уровне индекса, так и на уровне конечного узла. Следовательно, мы удаляем его из обоих экземпляров.
• Но мы должны заполнить индекс, указывающий на 42. Теперь мы рассмотрим правильного потомка младше 25 лет, возьмем минимальное значение и поместим его в качестве индекса. Таким образом, 42, являющееся единственным присутствующим значением, станет индексом.

Удалить алгоритм работы

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 + Tree — это самобалансирующаяся структура данных для точного и быстрого поиска, вставки и удаления данных.
• Мы можем легко получить полные или частичные данные, потому что прохождение через связанную древовидную структуру делает ее эффективной.
• Древовидная структура B + растет и уменьшается с увеличением / уменьшением количества хранимых записей.
• Хранение данных на конечных узлах и последующее разветвление внутренних узлов, очевидно, сокращает высоту дерева, что уменьшает операции ввода и вывода диска, в конечном итоге занимая гораздо меньше места на устройствах хранения.