Алгоритм на псевдокоде. Построение Б – дерева (D: Данные, a: pPage, Rost: Boolean, V: Item)

Построение Б – дерева (D: Данные, a: pPage, Rost: Boolean, V: Item)

Обозначим D – добавляемые данные

а – адрес страницы

Rost – логическая переменная; (принимает значение истина, если дерево выросло).

V – рабочая переменная типа Item для элемента, передаваемого вверх по дереву.

u – рабочая переменная типа Item, фактический параметр при вызове процедуры построения

IF (a = NIL) {D нет в дереве, включение}

V.Data:= D

V.p:= NIL

Rost:= ИСТИНА

ELSE Поиск в Б-дереве (D,a)

IF (R > 0 и a→ e_R.data = D) {элемент D есть в дереве}

ELSE (на этой странице ключа D нет)

IF(R = 0) Построение Б-дерева(D, a→p₀, Rost, u)

ELSE Построение Б-дерева (D, a→e_R.p, Rost, u)

FI

IF (Rost = true) {включение u вправо от e_R}

IF (k < 2m) Rost:= false {есть место на странице}

k:= k+1

DO (i = k, k-1,..., R+2) e_i = e_i-1

OD

e _R+1:= u

ELSE {переполнение страницы}

New(b) {создание новой страницы}

IF (R<= m)

IF (R=m) V:= u

ELSE V:=e_m

DO (i = m, m-1,..., R+2) e_i:= e_i-1

OD

e_R+1:= u

FI

DO (i:=1, 2,... m) b→e_i:= a→e_i-1

OD

ELSE {включение в правую страницу}

R:= R-m

V:=e_m+1

DO(i=1, 2,... R-1) b→e_i:= a→e_i+m+1

OD

b→e_R:= u

DO (i:=R+1, R+2,..., m) b→e_i:= a→e_i+m

OD

FI

a→k:= m

b→k:= m

b→p₀:= V.p

V.p:= b

FI

FI

FI

FI

При создании Б-дерева необходимо предусмотреть разделение корневой страницы и создания нового корня из одного элемента. Это будет выполняться, если после обращения к процедуре построения Б-дерева с параметром Rost равным ИСТИНА.