Стр. 50 - Основы алгоритмов и структур данных

48 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
10 15 20
2 5 7 8 16 18 13 14 22 23 24
Рис. 48. Пример B-дерева
Если и там возникло переполнение, то разрешаем его аналогичным
образом.
Так, процесс переполнения и разделения страниц может достичь корня.
Если и корень переполнился, то разделяем его на 2 страницы, а средний ключ
поднимаем вверх и образуем новый корень.
Очевидно, В-деревья растут, начиная с листьев, в ширину, кончая корнем, в
высоту.
При поиске и возможном последующем разделении страниц, каждая
страница на некоторой ветви от корня до листа востребуется дважды: при
поиске и при разделении.
Таким образом, чтобы избежать повторного считывания страницы с
магнитного диска в оперативную память, необходимо выбирать размер
страницы так, чтобы в память одновременно вмещалось столько страниц,
какова высота дерева + одна для разделения.
(Самостоятельно записать алгоритм включения)