Пусть имеется Б-дерево порядка m, в которое требуется добавить новый элемент с ключом х. Как обычно, прежде всего организуется поиск элемента с этим ключом.
Пусть такого элемента в дереве нет. Признаком данной ситуации является попытка загрузки новой страницы с пустой ссылкой. Именно в данный момент и необходимо начать добавление вершины на текущую терминальную страницу.
При этом возможны следующие две ситуации:
· текущая страница, в которую должен быть вставлен новый элемент, заполнена не полностью (pCurrent^.nPage < 2m); в этом случае новый элемент просто вставляется в данную страницу в нужное место, с увеличением счетчика числа элементов на странице
· пусть текущая страница заполнена полностью, т.е. pCurrent^.nPage = 2m; добавление элемента на полностью заполненную страницу реализуется за счет разделения этой страницы на две страницы; создается новая страница, и после этого старая и новые страницы заполняются равномерно:
Ø левые m элементов передаются на новую страницу
Ø правые m элементов остаются на старой странице
Ø центральный (серединный) элемент передается наверх на родительскую страницу
При этом вытолкнутый наверх элемент вставляется на родительской странице в нужное место, если для этого есть свободное место. В противном случае, происходит расщепление родительской страницы на две, с выталкиванием центрального элемента еще выше и т.д. Такой процесс расщепления и выталкивания может дойти до корневой страницы. Если корневая страница заполнена полностью, то она расщепляется на две, с выталкиванием центрального элемента наверх, т.е. создается новая корневая страница, которая будет содержать единственный вытолкнутый снизу элемент. В этом случае высота Б-дерева увеличивается на 1.
|
|
Пример. Пусть в Б-дерево порядка 2 надо добавить вершину с ключом х = 32
 |
Страница, на которую надо добавить ключ 32, заполнена полностью, поэтому создается новая страница с элементами 32 и 35, на старой остаются ключи 42 и 46, а элемент 40 выталкивается на родительскую страницу, занимая в ней крайнее правое место
 |
Такой алгоритм добавления сохраняет структуру Б-дерева, т.к. синхронно на 1 увеличивается число элементов на родительской странице и число ее страниц-потомков.
Если в данном примере добавить еще элементы 36 и 38, то при попытке добавления элемента 33 опять придем к необходимости расщепления страницы:
| |||||||||
| |||||||
 |
Поскольку корневая страница заполнена полностью, происходит ее расщепление на две страницы, выталкивание наверх элемента 30 и создание новой корневой страницы
 |
Рассмотрим вопрос программной реализации алгоритма добавления. Поскольку добавление элемента на терминальной странице может привести к необходимости добавления и на ее родительской странице, а там, в свою очередь – на своей родительской странице и т.д., вплоть до корневой, в процессе поиска надо запоминать пройденный путь, т.е. пройденные на каждой странице точки разветвления. Как обычно, подобное запоминание можно реализовать либо неявно с помощью механизма рекурсии, либо явно с помощью стековой структуры.
|
|
Для рекурсивной реализации надо ввести подпрограмму Add, которая должна использовать три параметра:
· адрес новой текущей страницы, используемый как в процессе движения от корневой страницы к терминальной, так и обратно; поскольку этот адрес автоматически должен запоминаться и восстанавливаться, ссылочный параметр надо объявить как параметр-значение
· выходной логический параметр, который определяет факт расщепления текущей страницы и, следовательно, необходимость добавления выталкиваемого элемента на родительскую страницу
· выходной параметр-переменная, через который на родительскую страницу передается сам выталкиваемый элемент.
Схематично подпрограмма Add описывается следующим образом
procedure Add (pCurrent: pPage; var IsUp: boolean; var Item: TItem);
Begin
if pCurrent = nil then {элемента в дереве нет}
Begin
“формирование полей нового элемента Item”;
IsUp:= true;
End
else begin {продолжаем поиск на странице pCurrent}
“загрузка новой страницы”;
“поиск на странице элемента с заданным ключом”;
if “элемент найден” then “обработка элемента”
Else begin
“определение адреса страницы для продолжения поиска”;
Add (“адрес страницы”, IsUp, Item);
if IsUp then {добавить элемент на текущую страницу }
if pCurrent^.nPage < 2m then
Begin
pCurrent^.nPage:= pCurrent^.nPage + 1;
IsUp:= false;
“добавление элемента Item в страничный массив”
End
Else begin
“создание новой страницы”;
“формирование полей новой страницы”;
“корректировка полей старой страницы”;
“формирование выталкиваемого наверх элемента”
end;
end;
end;
end;
Как обычно, начальный вызов подпрограммы Add выполняется из главной программы, причем после возврата обратно в главную программу, возможно, придется создавать новую корневую страницу:
|
|
Begin
Add (pRoot, IsUp, Item);
if IsUp then
Begin
pTemp:= pRoot; New (pRoot);
pRoot^.nPage:= 1; pRoot^.LeftPage:= pTemp;
pRoot^.mas[1]:= Item;
end;
end;