тривается вопрос об оптимальном размере страницы п, опъш сильно зависит от характеристик памяти и вычисли-!ельн0й системы.

Вариации схемы Б-дерева обсуждаются в книге Кнута ,г2.7], т. 3, с. 567-570). Одно важное замечание заключает-

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

iJ.2. Бинарные Б-деревья

разновидность Б-деревьев, которая кажется наименее интересной,- Б-деревья первого порядка (n=l). Но иногда стоит обратить внимание и на этот случай. Ясно, однако, что Б-деревья первого порядка бесполезны для представления больших, упорядоченных, индексированных множеств данных, требующих внешней памяти; примерно 50% всех страниц будут содержать только один элемент. Поэтому мы забудем о внешней памяти и вновь рассмотрим деревья поиска, расположенные в оперативной памяти.

Бинарное Б-дерево (ББ-дерево) состоит из узлов (страниц) с одним или двумя элементами. Следовательно, страница содержит две или три ссылки на потомков, отсюда термин 2-5 дерево. Согласно определению Б-деревьев, все листья находятся на одном уровне, а все нетерминальные сграницы, в том числе корень, имеют двух или трех потомков. Поскольку теперь мы имеем дело только с оперативной памятью, то обязательно оптимальное использование памяти, поэтому представление элементов узла в виде массива здесь №.подходит. Альтернатива этому - динамическое, связанное размещение, т. е. внутри каждого узла имеется связанный Мисок элементов длиной 1 или 2. Поскольку каждый узел teer не более трех потомков и поэтому должен содержать ймое большее три ссылки, мы попытаемся комбинировать сылки на потомков и ссылки в списке элементов, как показано на рис. 4.50. Тем самым узел Б-дерева теряет свою целостность, и элементы выполняют роль узлов в обычном би-jPHOM дереве. Но необходимо различать ссылки на потомков ,ртикальные) и ссылки на братьев - элементы той же Раницы (горизонтальные). Поскольку лишь ссылки направо !гут быть горизонтальными, для указания этого различия статочно одного разряда. Поэтому мы вводим булевское К фиксирующее горизонталь . Описание узла дерева, Снованное на таком представлении, дано в (4.84). Оно было ложено Р. Бэйером [4.3] в 1971 г. Деревья поиска, по-

left,right: ref; (Щ

h: boolean

Рассматривая проблему включения, следует различать ч тыре возможные ситуации, которые возникают при увеличе'

А

Рис. 4.50. Представление узлов ББ-дерева.

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

Самый простой случай - это (1), когда растет правое поддерево узла А и когда Л - единственный ключ на (гипотетической) странице. Тогда потомок В просто становится братом Л, т. е. вертикальная ссылка становится горизонтальной. Такой простой подъем правой ветви невозможен, если Л уже имеет брата. Тогда мы получаем страницу с тремя узл^ ми и должны расщепить ее (случай 2). Ее средний узел передается на ближайщий более высокий уровень.

Теперь предположим, что увеличилась высота левого поА; дерева узла В. Если узел В снова один на странице (случ 3), т. е. его правая ссылка указывает на потомка, то лев- поддерево (А) может стать братом В. Нужен простой пов рот ссылок, так как левая ссылка не может быть горизонталь ной. Но если В уже имеет брата, подъем А дает стране с тремя узлами, что требует расщепления. Это расщеплен , выполняется очень просто: С становится потомком В, коЮР поднимается на ближайший более высокий уровень (случай

строенные из таких узлов, гарантируют максимальную п пути р== 2-[logЛ/].

type node = record Ле;;; integer;

Следует заметить, что при поиске ключей нет особой раз-двигаемся мы по горизонтальной или вертикальной

Рис. 4.51. Включение узлов в ББ-дерево.

Ь1лке. Поэтому забота о том, чтобы левая ссылка в случае 3 ановилась горизонтальной, хотя страница по-прежнему со-рРЖит не более двух узлов, кажется надуманной. Действи-Чьно, алгоритм включения проявляет странную асимметрию