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

Рис. 16.5. Построение B-дерева, часть 1
Здесь показаны шесть вставок в первоначально пустое B-дерево, построенное из страниц, которые могут содержать пять ключей и ссылок, при использовании 3-значных восьмеричных ключей (9-разрядных двоичных чисел). Ключи в страницах хранятся по порядку. Шестая вставка приводит к разбиению на два внешних узла с тремя ключами в каждом и внутренний узел, служащий в качестве индекса: его первая запись указывает на страницу, содержащую все ключи, которые больше или равны 000, но меньше 601, а вторая запись — на страницу, содержащую все ключи, которые больше или равны 601.


Рис. 16.6. Построение B-дерева, часть 2
После вставки четырех ключей 742, 373, 524 и 766 в самое правое B-дерево на рис. 16.5 обе внешние страницы оказываются заполненными (слева). Затем, при вставке ключа 2 7 5, первая страница разбивается с передачей ссылки на новую страницу (вместе с ее наименьшим ключом 37 3) вверх по индексу (в центре). Далее, при вставке ключа 7 37 разбивается нижняя страница, также с передачей ссылки на новую страницу вверх по индексу (справа).


Рис. 16.7. Построение B-дерева, часть 3
Продолжая наш пример, мы вставляем 13 ключей 574, 434, 641, 207, 001, 277, 061, 736, 526, 562, 017, 107 и 147 в самое правое B-дерево на рис. 16.6. Разбиения узлов выполняются при вставке ключей 277 (слева), 526 (в центре) и 107 (справа). Разбиение узла, вызванное вставкой ключа 52 6, приводит также к разбиению индексной страницы и увеличению высоты дерева на единицу.
Выполнение вставок сводится лишь к добавлению элемента в страницу, но на основании структуры результирующего дерева можно определить важные события, происшедшие во время его построения. Дерево содержит семь внешних страниц, поэтому должно было быть выполнено шесть разбиений внешних узлов, и поскольку его высота равна 3, корень дерева должен был разбиваться дважды. Эти события описаны в подписях к рисункам.
В программе 16.1 приведены определения типов для узлов нашей реализации B-дерева. Мы не указываем подробно структуру узлов, как в рабочей реализации, т.к. для этого потребовались бы ссылки на конкретные страницы диска. Для простоты мы используем один тип узлов, каждый узел состоит из массива записей, а каждая запись содержит элемент, ключ и ссылку. Каждый узел содержит также счетчик активных записей. Мы не обращаемся к элементам во внутренних узлах, не обращаемся к ссылкам во внешних узлах, и не обращаемся к ключам в элементах дерева. При использовании конкретной структуры данных в реальном приложении можно сэкономить память с помощью конструкций наподобие union или производных классов. Можно было бы также сэкономить память ценой увеличения времени выполнения, используя везде в дереве вместо ключей ссылки на элементы. Такие конструктивные решения достигаются очевидными изменениями кода и зависят от конкретного характера ключей, элементов и ссылок в приложении.
С помощью этих определений и рассмотренных примеров деревьев, код выполнения операции найти, приведенный в программе 16.2, реализуется элементарно. Для внешних узлов мы просматриваем массив узлов, чтобы найти ключ, соответствующий искомому ключу, и возвращаем связанный с ним элемент, если поиск успешен, и пустой элемент, если неудачен. Для внутренних узлов мы просматриваем массив узлов, чтобы найти ссылку на уникальное поддерево, которое может содержать искомый ключ.
Программа 16.3 является реализацией операции вставить для B-деревьев; в ней также применяется рекурсивный подход, используемый во многих других реализациях деревьев поиска из глав 13 и 15. Эта реализация является восходящей, т.к. проверка, нужно ли разбивать узел, выполняется после рекурсивного вызова — поэтому первым разбивается внешний узел. Разбиение требует передачи новой ссылки наверх к родительскому узлу разбиваемого узла, который, в свою очередь, может нуждаться в разбиении и передаче ссылки его родительскому узлу и т.д. — возможно, вплоть до корня дерева (при разбиении корня создается новый корень с двумя дочерними поддеревьями).
В противоположность этому в реализации 2-3-4-дерева в программе 13.6 проверка, нужно ли разбивать узел, выполняется перед рекурсивным вызовом, и поэтому разбиение выполняется при спуске вниз по дереву. Для B-деревьев можно воспользоваться и нисходящим подходом (см. упражнение 16.10). Во многих приложениях, использующих B-деревья, это различие между нисходящим и восходящим подходами несущественно, поскольку такие деревья являются очень плоскими.
Код разбиения узла приведен в программе 16.4. В нем переменная M должна иметь четное значение, и каждый узел дерева может содержать только M — 1 элемент. Этот подход позволяет вставлять M-й элемент в узел перед разбиением этого узла и значительно упрощает код, не оказывая особого влияния на затраты (см. упражнения 16.20 и 16.21). Для простоты аналитических выкладок, приведенных далее в этом разделе, мы вводим ограничение, что количество элементов каждого узла должно быть не больше M; реальные различия несущественны. В нисходящей реализации эта технология не нужна, т.к. в ней наличие свободного места в каждом узле для вставки нового ключа обеспечивается автоматически.