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

B-деревья

Для построения структур поиска, которые могут быть эффективны в динамических ситуациях, мы будем строить многопутевые деревья, но при этом откажемся от ограничения, что каждый узел должен содержать точно M записей. Вместо этого выдвинем условие, что каждый узел должен иметь не более M записей, чтобы они помещались на странице, но узлы могут иметь и меньше записей. Чтобы гарантировать, что узлы имеют достаточное количество записей для обеспечения ветвления, необходимого для предотвращения увеличения длины путей, мы также потребуем, чтобы все узлы имели не менее (допустим) M/2 записей — за исключением, быть может, корня, который должен иметь не менее одной записи (двух ссылок). Причина этого исключения для корня станет понятна при подробном рассмотрении алгоритма построения. Байер (Bayer) и МакКрейт (McCreight) первыми (в 1970 г.) исследовали возможность использования многопутевых сбалансированных деревьев для внешнего поиска и назвали такие деревья B-деревьями. Термин B-дерево часто используется для описания именно той структуры данных, которая строится алгоритмом, предложенным Байером и МакКрейтом; мы же будем использовать его в качестве общего термина для обозначения семейства похожих алгоритмов.
Мы уже встречались с реализацией B-дерева: из определений 13.1 и 13.2 видно, что B-деревья четвертого порядка, в которых каждый узел содержит не более 4 и не менее 2 ссылок, являются ни чем иным, как сбалансированными 2-3-4-деревьями, описанными в "Сбалансированные деревья" . Лежащая в их основе абстракция допускает непосредственное обобщение, так что B-деревья можно реализовать, обобщив реализации нисходящего 2-3-4-дерева, описанные в "Сбалансированные деревья" . Однако различия между внешним и внутренним поиском, упомянутые в разделе 16.1, приводят к ряду различий в реализациях.

• 
  обобщает 2-3-4-деревья до деревьев, имеющих от M/2 до M узлов
  
• 
  представляет многопутевые узлы в виде массива элементов и ссылок
  
• 
  реализует индекс, а не структуру поиска, содержащую элементы
  
• 
  выполняет восходящее разбиение
  
• 
  отделяет индексы от элементов
  

Два последних свойства в этом перечне несущественны, однако во многих ситуациях удобны и часто применяются в реализациях B-деревьев.
На рис. 16.4 показано абстрактное 4-5-6-7-8-дерево, являющееся обобщением 2-3-4-дерева из "Сбалансированные деревья" . Обобщение очевидно: 4-узлы имеют три ключа и четыре ссылки, 5-узлы — четыре ключа и пять ссылок и т.д.: по одной ссылке для каждого возможного интервала ключей. Поиск начинается с корня и проходит от одного узла к другому, определяя в текущем узле интервал, который соответствуюет искомому ключу, и переходя к следующему узлу по соответствующей ссылке. Поиск завершается успешно, если ключ поиска находится в любом из рассмотренных узлов, и неудачно, если он дошел до низа дерева, не обнаружив искомый ключ. Как и в случае 2-3-4-деревьев, новый ключ можно вставить после выполнения поиска в нижнюю часть дерева, если при спуске вниз по дереву выполняется разбиение заполненных узлов: если корень является 8-узлом, он заменяется 2-узлом, связанным с двумя 4-узлами. Затем, каждый раз, когда встречается k-узел с присоединенным 8-узлом, он заменяется (к+1)-узлом с двумя присоединенными 4-узлами. Это правило гарантирует наличие места для вставки нового узла по достижении нижней части дерева.
Или же, как и в "Сбалансированные деревья" применительно к 2-3-4-деревьям, разбиение можно выполнять снизу вверх: после выполнения поиска новый ключ вставляется в нижний узел, если только тот не является 8-узлом — в этом случае он разбивается на два 4-узла со вставкой среднего ключа и двух ссылок в его родительский узел. Восходящее разбиение выполняется до тех пор, пока не встретится узел-предок, отличный от 8-узла.
Замена в предыдущих двух абзацах 4 на M/2, а 8 — на M позволяет преобразовать приведенные описания в описания поиска и вставки в М/2-...-М-деревьях для любого положительного четного M (см. упражнение 16.9).