Внешний поиск a

Рис. 16.4. 4-5-6-7-8-дерево
На рисунке показано обобщение 2-3-4-деревьев, которое построено из узлов, содержащих от 4 до 8ссылок (и соответственно от 3 до 7ключей). Как и в случае 2-3-4-деревьев, мы поддерживаем высоту деревьев постоянной, разбивая встречающиеся 8-узлы при работе нисходящего или восходящего алгоритма вставки. Например, для вставки в это дерево еще одного ключа J нужно сначала разбить 8-узел на два 4-узла, а затем вставить ключ M в корень, преобразовав его в 6-узел. При разбиении корня возможно лишь создание нового корня, который будет 2-узлом — поэтому корень не подчиняется общему правилу, согласно которому узлы должны содержать не менее четырех ссылок.
Определение 16.2. B-дерево порядка M — это дерево, которое либо пусто, либо состоит из k-узлов с к — 1 ключами и к ссылками на деревья, представляющими каждый из к ограниченных ключами интервалов, и обладает следующими структурными свойствами: к должно находиться в интервале между 2 и M в корне и между M/2 и M в любом другом узле; все ссылки на пустые деревья должны находиться на равном расстоянии от корня.
Алгоритмы B-деревьев построены на основе этого базового набора абстракций. Как и в "Сбалансированные деревья" , существует значительная свобода в выборе конкретных представлений таких деревьев. Например, можно использовать расширенное RB-представление (см. упражнение 13.69). Для внешнего поиска мы используем еще более простое представление в виде упорядоченного массива, выбирая достаточно большое значение M, чтобы M-узлы заполняли всю страницу. Коэффициент ветвления равен по меньшей мере M/2, поэтому, как следует из текста после леммы 16.1, количество проб, необходимое для выполнения любого поиска или вставки, практически постоянно.
Вместо реализации только что описанного метода рассмотрим вариант, обобщающий стандартный индексный указатель, рассмотренный в разделе 16.1. Будем хранить ключи со ссылками на элементы во внешних страницах в нижней части дерева, а копии ключей со ссылками на страницы — во внутренних страницах. Мы вставляем новые элементы в нижнюю часть, а затем используем базовую абстракцию M/2-...-M дерева. Если страница содержит M записей, мы разбиваем ее на две страницы с M/2 записями в каждой и вставляем в родительскую страницу ссылку на новую страницу. При разбиении корня мы создаем новый корень с двумя дочерними узлами, тем самым увеличивая высоту дерева на 1.
На рис. 16.5 рис. 16.7—16.7 показан процесс построения B-дерева вставками ключей, показанных на рис. 16.1 (в приведенном порядке) в первоначально пустое дерево при M= 5.