B+ TREE: поиск, вставка и удаление Operaных

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

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

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

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

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

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

Вот причины, по которым стоит использовать дерево B+:

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

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

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

Поиск Operaпроизводство

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

Применим следующий алгоритм поиска:

• Чтобы найти нужную запись, необходимо выполнить команду бинарный поиск по доступным записям в Дереве.
• В случае точного совпадения с ключом поиска пользователю возвращается соответствующая запись.
• Если точный ключ не найден в результате поиска в родительском, текущем или листовом узле, пользователю отображается сообщение «не найдено».
• Процесс поиска можно запустить повторно для получения более качественных и точных результатов.

Поиск 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. If 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 в качестве элемента-указателя.
• Теперь создается правосторонняя иерархия дерева, и оставшиеся значения данных соответствующим образом корректируются с помощью функции `kee`.ping Примите во внимание применимые правила определения значений «равно» или «больше» для узлов «ключ-значение» справа.

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

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

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

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

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

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

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

Удалить Operaалгоритм

1) Start at the root and go up to the 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 и его родительских узлах при необходимости заимствуются ключи у соседних узлов.

Часто задаваемые вопросы (FAQ)