13. Особенности операций над B -деревьями
 

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

Включение элемента в В-дерево. Сначала определяется узел в который должен быть включен элемент. Если элемент включается в узел, содержащий m<2n элементов, то он помещается в соответствующее место в упорядоченной последовательности находящихся в узле элементов, как, например, при вставке элемента с ключом 22 или 23 на рисунке. Включение элемента в уже заполненный узел влияет на структуру дерева и вызывает появление новой страницы.

Теперь рассмотрим на примере. Включим элемент с ключом 4. Его место в самом левом листовом узле, однако там нет места, так как включении получилось бы пять элементов: 2, 4, 7, 8, 9. В этом случае образуется новая страница. В старой странице остаются первые n элементов (2, 4), последние n элементов (8, 9) переносятся в новую страницу, а средний элемент поднимается в вышестоящий узелпредок с корректировкой указателей в нем

Если в результате образования нового узла и переноса среднего элемента будет переполнен узел-предок, то он, в свою очередь, разбивается на две части, образуется новая страница и т.д. При переполнении корневого узла высота дерева увеличивается на 1. Таким образом, в отличие от обычных деревьев В-дерево растет с листьев, а не с корня.

Удаление элемента из В-дерева. Оно несколько сложнее, чем включение, когда возникают случаи несбалансированности, т.е. в узле остается меньше n ключей. В таком случае можно либо позаимствовать один элемент из соседней страницы, если там число элементов больше n, либо слить две страницы в одну.

Обработка данных. Различают два вида обработки: выборочную обработку отдельного элемента и последовательную обработку всех элементов или группы элементов с ключами в заданных пределах. Выборочная обработка включает поиск элемента, и если он найден, то выборку или обновление данных в элементе.

При последовательной обработке осуществляются обход либо всех узлов дерева, либо узлов в заданных пределах и обработка элементов в посещаемых узлах. Левый смешанный обход приводит к обработке элементов в порядке возрастания их ключей.