Базовые структуры данных. Сбалансированные деревья, страница 4

Время работы программы в основном определяется количеством обращений к диску, поэтому имеет смысл сделать так, чтобы вершина дерева полностью заполняла сектор. Типичная степень ветвления Б-деревьев находится между 50 и 2000.

2.2  Определение Б-дерева

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

Б-деревом (B-Tree) называется корневое дерево, устроенное следующим образом:

1.  Каждая вершина содержит поля, в которых хранятся

·  Количество k ключей, хранящихся в ней;

·  Сами ключи key₁<=key₂<=…<=key_k

·  Булевское значение leaf, истинное, когдав вершина является листом.

2.  Если вершина внутренняя, то она содержит k+1 указателей c₁,c₂,…,c_k,c_k+1 на ее детей. У листьев детей нет, и эти поля для них не определены.

3.  Ключ служат границами, разделяющими значения ключей в поддеревьях:

kx₁<=key₁<=kx₂<=key₂<=…<=key_k<=kx_k+1

4.  Все листья находятся на одной и той же глубине (равной высоте h дерева).

5.  Число ключей, хранящихся в одной вершине, ограничено сверху и снизу; границы задаются единым для всего древа t>=2, которое называется минимальной степенью Б-дерева.

·  Каждая вершина, кроме корня, содержит, по крайней мере, t–1 ключей. Таким образом, все внутренние вершины (кроме корня) имеют не менее t детей. Если дерево не пусто, то в корне должен храниться хотя бы один ключ.

·  В вершине хранится не более 2t–1 ключей. Следовательно, внутренняя вершина не может иметь более 2t детей. Вершину, хранящую ровно 2t–1 ключей, назовем полной.

Для всякого Б-дерева высоты h и минимальной степени t>=2, хранящего n>=1 ключей, выполнено неравенство

h<=log_t((n+1)/2)

Как и в красно-черных деревьях, высота Б-дерева есть O(log n), но основание логарифма Б-деревьев много больше, что позволяет сократить количество обращений к диску в log_tn раз.

Мы считаем, что

·  корень Б-дерева всегда находится в оперативной памяти, то есть не требуется считывание объекты перед использованием, но запись осуществляется;

·  все вершины, передаваемые как параметры, уже считаны с диска.

2.3  Поиск в Б-дереве

Рекурсивная процедура, получив на вход указатель на корневую вершину, ищет минимальное i, для которого k<=key_i; если такого нет, то в i помещается k+1. Если дошли до листа, программа заканчивается безрезультатно; иначе она либо возвращает пару (y, i) – (вершина, смещение найденного элемента), либо считывает корень поддерева с диска и вызывается рекурсивно.

2.4  Создание пустого Б-дерева

Чтобы создать Б-дерево, мы сначала создаем пустое Б-дерево, а затем добавляем в него элементы. И та, и другая операция используют процедуру выделения памяти, которая находит место под вершину на диске, занимает время O(1) и не использует обращения к диску. Создадим корневую вершину, пометим ее как лист и положим k=0.

2.5  Разбиение вершины Б-дерева на две

Добавление элемента в Б-дерево – намного более сложная операция, чем добавление элемента в двоичное дерево поиска. Ключевым моментом является разбиение (splitting) полной (с 2t–1 ключами) вершины y на две по t–1 элементов каждая. При это ключ-медиана попадает к родителю x вершины y и становится разделителем двух полученных вершин. Это возможно, если x не полна. Если y – корень, процедура работает аналогично. В этом случае высота дерева увеличивается на 1.

В процедуру передаются указатели y (на полную вершину) и x (на ее родителя, неполную внутреннюю вершину) и число i, такие, что y=x–>c_i. Во время работы процедуры выбирается медиана S, которая переписывается в x, все элементы левее медианы (меньше) остаются в y, правее – переписываются в новую вершину z. Вершина y имела 2t детей, после преобразования в ней осталось t наименьших среди них, остальные t стали детьми новой вершины. Время работы циклов равно Θ(t).