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

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

A B + Дерево в основном используется для реализации динамического индексирования на нескольких уровнях. По сравнению с B-деревом, дерево B+ хранит указатели данных только в конечных узлах дерева, что делает процесс поиска более точным и быстрым.

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

Вот основные правила для B+ Tree.

• Листья используются для хранения записей данных.
• Он хранится во внутренних узлах Дерева.
• Если значение целевого ключа меньше внутреннего узла, то отслеживается точка слева от него.
• Если значение целевого ключа больше или равно внутреннему узлу, то отслеживается точка справа от него.
• Корень имеет минимум двух дочерних элементов.

Зачем использовать дерево B+

Вот причины для использования B+ Tree:

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

Дерево B+ против дерева B

Вот основные различия между B+ Tree и B Tree.

B + Дерево	Б Дерево
Ключи поиска могут повторяться.	Ключи поиска не могут быть избыточными.
Данные сохраняются только на конечных узлах.	Как листовые узлы, так и внутренние узлы могут хранить данные.
Данные, хранящиеся в конечном узле, делают поиск более точным и быстрым.	Поиск медленный из-за того, что данные хранятся на Leaf и внутренних узлах.
Удаление не представляет сложности, поскольку элемент удаляется только из листового узла.	Удаление элементов – сложный и трудоемкий процесс.
Связанные конечные узлы делают поиск эффективным и быстрым.	Вы не можете связать конечные узлы.

Поиск 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."

Результат:

Соответствующий набор записей, соответствующий точному ключу, отображается пользователю; в противном случае пользователю будет показана неудачная попытка.

Вставить Operaпроизводство

Для операции вставки применим следующий алгоритм:

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

Вставить 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+ объясняется следующими шагами:

• Во-первых, у нас есть 3 узла, и первые 3 элемента (1, 4 и 6) добавляются в соответствующие места в узлах.
• Следующее значение в ряду данных — 12, которое необходимо сделать частью Дерева.
• Для этого разделите узел, добавьте 6 в качестве элемента указателя.
• Теперь создается правая иерархия дерева, и оставшиеся значения данных соответствующим образом корректируются с учетом применимых правил, касающихся значений, равных или превышающих значения, для узлов «ключ-значение» справа.

Удалить Operaпроизводство

Сложность процедуры удаления в дереве B+ превосходит сложность вставки и поиска.

Следующий алгоритм применим при удалении элемента из дерева B+:

• Во-первых, нам нужно найти листовую запись в дереве, содержащую ключ и указатель. , удалите листовую запись из Дерева, если Лист соответствует точным условиям удаления записи.
• Если листовой узел соответствует удовлетворительному фактору заполнения только наполовину, операция завершается; в противном случае узел Leaf имеет минимальное количество записей и не может быть удален.
• Другие связанные узлы справа и слева могут освобождать любые записи, а затем перемещать их в лист. Если эти критерии не выполняются, то следует объединить листовой узел и связанный с ним узел в иерархии дерева.
• При слиянии листового узла с его соседями справа или слева записи значений в листовом узле или связанном соседе, указывающие на узел верхнего уровня, удаляются.

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