Чтобы вставить новый элемент в Б-дерево, определите лист, в который должен
быть помещен новый элемент. Если этот узел содержит менее чем 2 * К ключей, то
в нем есть место для вставки нового элемента. Добавьте новый элемент в соответ-
ствующую позицию, чтобы элементы узла были упорядочены.
Если узел уже содержит 2 * К элементов, то места для нового элемента в узле
уже не остается. Чтобы создать необходимое пространство, поделите узел на два
новых узла. Теперь имеется 2 * К + 1 элементов для распределения между двумя
новыми узлами. Разместите К элементов в каждом узле, сохраняя’ соответствую-
щий порядок их расположения. Переместите средний элемент в родительский узел.
Например, нужно вставить элемент Q в Б-дерево, показанное на рис. 7.15. Этот
новый элемент принадлежит второму листу, который уже заполнен. Чтобы разбить
узел, поделите элементы J, К, N, Р и Q между двумя новыми узлами. Расположите
элементы J и К в левом узле, а Р и Q — в правом. Затем переместите средний эле-
мент N в родительский узел. На рис. 7.16 изображено полученное дерево.

Рис. 7.16. Б-дерево после добавления элемента Q
Деление узла на два называется дроблением сегмента. Когда оно происхо-
дит, родительский узел получает новый ключ и новый указатель. Если родитель-
ский узел уже полон, то добавление нового ключа и указателя также может при-
вести к его дроблению, что, в свою очередь, потребует добавления новой записи
на более высоком уровне и т.д. В наихудшем случае добавление элемента вызы-
вает «цепную реакцию» дробления узлов вплоть до корня.
Когда происходит дробление корня, Б-дерево становится глубже. Это един-
ственный способ увеличить его глубину. Поэтому Б-деревья обладают необычным
свойством — они всегда растут от листьев к корню.

Б-деревья
Производительность Б-дерева
Удаление элементов из Б-дерева
Разновидности Б-дерева
Нисходящие Б-деревья
Б+деревья
Усовершенствование Б-деревьев
Добавление свободного пространства