Вершина В-дерева представляется в виде приведенного ниже набора элементов

- ссылка на вершину, содержащую элементы ;

- ключевые значения;

- соответствующие (ассоциированные) данные (указатели данных);

- ссылки на порождённую вершину (указатели индекса).

«Хранимые» в вершине ассоциированные данные фактически представляют собой совокупность указателей данных и служат для определения физического местоположения данных, ключевые значения которых хранятся в этой вершине.

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

1) для (при этом поиск продолжается в блоке, на который ссылается );

2) (поиск продолжается в блоке, на который ссылается );

3) (поиск продолжается по ссылке ).

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

Поиск элементов В-дерева рассмотрим на примере, изображённом на рис. 4.5.2. Как видно, это фрагмент В-дерева порядка 2 с 3 уровнями (n=2, h=3):

	Рис. 4.5.2. Фрагмент В-дерева порядка 2.

Включение и удаление элементов В-дерева

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

Пусть, например, требуется вставить элемент 22 в В-дерево, изображённое на рис. 4.53. (а).

В этом случае выделяется новый блок и элементы 22, 26, 30, 35 и 40 разделяются поровну между блоком, в который должна была производится вставка, и выделенным новым блоком, а средний элемент 30 записывается в блок верхнего уровня.

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

При удалении элемента из В-дерева возможны две ситуации, связанные с его расположением (либо в блоке-листе, либо в ветвящейся вершине).

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

В случае, если это число равно 2n, то все оставшиеся элементы необходимо перераспределять поровну между этими вершинами, не нарушая правила ссылок. Если же общее число элементов равно 2n-1, то уменьшаемую и соседнюю с ней вершину необходимо объединить и, во избежание нарушения ссылок, перенести соответствующий ключ из вершины предыдущего уровня в объединённую вершину.

Например, пусть имеется дерево порядка 2 (2<m<4), представленное на рис. 4.5.4, и в нём необходимо удалить элемент 24.

Рис. 4.5.4. Удаление элементов из В-дерева

Общее число элементов в уменьшаемой и соседней с ней вершинах равно 2n=4, а в уменьшаемой вершине - меньше 2. Перераспределяя элементы в уменьшаемой и соседней с ней вершинах (элемент 18 при этом попадает в вершину верхнего уровня) получаем сбалансированное В-дерево, представленное на рис. 4.5.4 (б).

Пусть теперь необходимо удалить элемент 22. Общее число элементов в уменьшаемой и соседней с ней вершинах равно 2n-1=3, а в уменьшаемой вершине - также меньше 2. По описанному выше правилу сохранения ссылок имеем соответственно дерево, представленное ниже.

Рис. 4.5.5. Результат удаления элемента 22.

В этом случае сначала были объединены вершины-листья (элемент 18 заимствован из вершины верхнего уровня), затем объединены соседние вершины предыдущего уровня (с заимствованием элемента 25 из корня).

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

Например, пусть имеется дерево порядка 2 (2<m<4), изображённое на рис. 4.5.6 (а), и из него необходимо удалить элемент 20.

Рис. 4.5.6. Удаление элемента из ветвящейся вершины.

После удаления указанного элемента дерево имеет вид, представленный на рис. 4.5.6 (б). Как видно, в данном примере балансировка не требуется.