Включение нового значения индексируемого поля происходит посредством выполнения следующих действий.

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

· Если листовая страница не заполнена полностью, в нее записывается новое значение индексируемого поля и указатель на страницу файла данных, содержащую соответствующую запись (строку таблицы).

· Если листовая страница уже заполнена, то она делится «пополам», и тем самым порождается новая листовая страница. Среднее значение исходной листовой страницы записывается в вершину - предок на соответствующее место так, чтобы в странице обеспечивался последовательный порядок расположения значений индексируемого поля по схеме, приведенной на рис. 2.19. При этом после вставленного значения образуется указатель-ссылка на новую листовую страницу, образованную остатком от разделённой исходной листовой страницы.

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

Рис. 2.19. Структура внутренней вершины Б-дерева.