Операция включения в В – дерево.

Предположим, что страница уже считана в оперативную память. Она представляет собой последовательность ключей.

k₁ £ k₂ £ … £ k_m

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

1. k _i < x < k _{i + 1},1 < i £ m поиск продолжается по указателю p_i ^

2. x < k _m поиск продолжается по указателю p_o ^

3. x > k_m поиск продолжается по указателю p_m^

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

При m < 2*n алгоритм прост.

Пример.

Необходимо включить 22.

1. Поиск этого элемента, если нет, то

2. Определение страницы, где он должен находиться (в данном случае вторая)

3. Если необходимо, расщепить страницу. Суть этой операции : при включении элемента В – дерево должно оставаться В – деревом. Количество элементов 2*n + 1 делится поровну между новой и старой страницей.

Медиана ( средний элемент ) передаётся вверх к родителю . Родитель тоже может быть переполнен включением нового элемента, над этим родителем происходит операция расщепления и так до корня . Такая схема сохраняет все характерные свойства В – дерева и в крайнем случае включение элемента может подняться до самого корня . Фактически только в этом случае может увеличиться высота В – дерева . Таким образом В – дерево растёт от листьев к корню .

Типы переменных, которые используются в В – дереве .

Type Ptr = ^Page ;

Index = 0 .. 2*n ;

Element = record

key : integer ;

p : Ptr ;

count : integer ;

end ;

Page = record

M : Index ;

p0 : Ptr ;

e : array [ 1 .. 2*n ] of element

end ;