Что такое B + Tree?
В + Дерево в основном используется для реализации динамического индексирования на нескольких уровнях. По сравнению с B-деревом, B + Tree хранит указатели данных только в конечных узлах дерева, что делает поиск более точным и быстрым.
В этом руководстве по B + Tree вы узнаете:
- Что такое B + Tree?
- Правила для B + Tree
- Зачем использовать B + Tree
- B + Tree против B Tree
- Поисковая операция
- Вставить операцию
- Удалить операцию
Правила для B + Tree
Вот основные правила для B + Tree.
- Листья используются для хранения записей данных.
- Он хранится во внутренних узлах Дерева.
- Если значение целевого ключа меньше внутреннего узла, то отслеживается точка слева от него.
- Если значение целевого ключа больше или равно внутреннему узлу, то отслеживается точка справа от него.
- У корня есть минимум два дочерних элемента.
Зачем использовать B + Tree
Вот причины для использования B + Tree:
- Ключ в первую очередь используется для помощи в поиске путем направления к нужному листу.
- B + Tree использует «коэффициент заполнения» для управления увеличением и уменьшением дерева.
- В деревьях 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 точно связан с минимальным значением ключа и новым местоположением в дереве.
- Разделите родительский узел на большее количество мест на случай, если он будет полностью использован.
- Теперь, для лучших результатов, центральный ключ связан с узлом верхнего уровня этого 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 + Tree объясняется в следующих шагах:
- Во-первых, у нас есть 3 узла, и первые 3 элемента, а именно 1, 4 и 6, добавляются в соответствующие места в узлах.
- Следующее значение в серии данных - 12, которое необходимо сделать частью Дерева.
- Чтобы добиться этого, разделите узел, добавьте 6 как элемент указателя.
- Теперь создается иерархия справа в дереве, и оставшиеся значения данных корректируются соответствующим образом с учетом применимых правил равных или больших значений для узлов "ключ-значение" справа.
Удалить операцию
По сложности процедура удаления в B + Tree превосходит функциональность вставки и поиска.
Следующий алгоритм применим при удалении элемента из B + Tree:
- Во-первых, нам нужно найти листовую запись в дереве, которая содержит ключ и указатель. , удалите листовую запись из Дерева, если Лист удовлетворяет точным условиям удаления записи.
- В случае, если листовой узел удовлетворяет удовлетворительному фактору заполнения только наполовину, операция завершается; в противном случае узел Leaf имеет минимум записей и не может быть удален.
- Другие связанные узлы справа и слева могут освободить любые записи, а затем переместить их в Leaf. Если эти критерии не выполняются, они должны объединить конечный узел и связанный с ним узел в иерархии дерева.
- При слиянии листового узла с его соседями справа или слева удаляются записи значений в листовом узле или связанном соседе, указывающие на узел верхнего уровня.
В приведенном выше примере показана процедура удаления элемента из дерева B + определенного порядка.
- Во-первых, в дереве указываются точные местоположения удаляемого элемента.
- Здесь удаляемый элемент может быть точно идентифицирован только на конечном уровне, а не при размещении индекса. Следовательно, элемент может быть удален, не затрагивая правила удаления, которые являются значением минимального ключа.
- В приведенном выше примере мы должны удалить 31 из Дерева.
- Нам нужно найти экземпляры 31 в Index и Leaf.
- Мы видим, что 31 доступен как на уровне узлов индекса, так и на уровне листа. Следовательно, мы удаляем его из обоих экземпляров.
- Но мы должны заполнить индекс, указывающий на 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 + растет и сжимается с увеличением / уменьшением количества хранимых записей.
- Хранение данных на листовых узлах и последующее разветвление внутренних узлов, очевидно, сокращает высоту дерева, что сокращает операции ввода и вывода на диск, в конечном итоге занимая гораздо меньше места на устройствах хранения.