B-дерево порядка 2.

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

1. Выясняется, что ключ 17 отсутствует. Включение в страницу с ключами 13 … 18 невозможно, так как она уже заполнена.
2. Заполненная страница расщепляется на две страницы, т.е. размещается новая страница.
3. Количество m+1 ключей поровну распределяется на двух страницах, а средний ключ перемещается на один уровень вверх, на страницу-предка.

Алгоритм поиска с включением по В-дереву оформлен в виде процедуры search. Его основная структура проста и напоминает структуру простого поиска по бинарному делу, с той разницей, что дальнейший путь выбирается не из двух возможных ветвей. Вместо этого «поиск внутри страницы» оформлен как бинарный поиск в массиве. Алгоритм включения сформулирован в виде отдельной процедуры лишь для ясности. Эта процедура вызывается после того, как Search указывает, что элемент нужно передать вверх по дереву (в направлении к корню).

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

type

Ref=^Page;

Index=0..Nn;

Item=Record

Key:Integer;

P:Ref;

Count:Integer;

End;

Page=Record

M:Index; (* Число элементов *)

P0:Ref; (* Указатель на страницу В-дерева *)

E:Array[1..Nn] of Item;

End;

Procedure Search (X:Integer;A:Ref;Var H:Boolean; Var V:Item);

(* Добавление узла в В-дерево *)

Var

K,L,R:Integer;

Q:Ref;

U:Item;

Procedure Insert;

(* Включение U справа от A^.E[R] *)

Var

I:Integer;

B:Ref;

Begin

With A^ do

begin

If M<Nn then

begin

M:=M+1;

H:=False;

For I:=M Downto R+2 do E[I]:=E[I-1];

E[R+1]:=U;

end

Else (* Старница A^ заполнена, расщепить ее и присвоить полученный элемент V *)

Begin

New(B);

If R<=N Then

Begin

If R=N then V:=U

Else

Begin

V:=E[N];

For I:=N Downto R+2 do E[I]:=E[I-1];

E[R+1]:=U;

end;

For I:=1 to N do B^.E[I]:=A^.E[I+N]

End

Else (* Включение U в первую страницу *)

begin

R:=R-N;

V:=E[N+1];

For I:=1 To R-1 Do B^.E[I]:=A^.E[I+N+1];

B^.E[R]:=U;

For I:=R+1 To N Do B^.E[I]:=A^.E[I+N];

end;

M:=N;

B^.M:=N;

B^.P0:=V.P;

V.P:=B;

end

end;

End;

begin

(* Поиск ключа X на странице A^; H=False *)

If A=Nil then (* Элемента C с ключом X нет в дереве *)

begin

H:=True;

With V do

begin

Key:=X;

Count:=1;

P:=Nil;

end

end

Else (* Двоичный поиск в массиве *)

With A^ do

begin

L:=1;

R:=M;

Repeat

K:=(L+R) div 2;

If X<=E[K].Key then R:=K-1;

If X>=E[K].Key then L:=K+1;

Until R<L;

If L-R>1 then (* Элемент найден *)

begin

E[K].Count:=E[K].Count+1;

H:=False;

end

Else (* Элемента нет на этой странице *)

begin

If R=0 then Q:=P0 else Q:=E[R].P;

Search(X,Q,H,U);

If H then Insert

end;

end;

end;