Алгоритмы и структуры данных

Type

PBTreeNode = ATBTreeNode;

TBTreeNode = record {вершина дерева}

Count: integer; {количество записей в вершине}

PreviousNode: PBTreeNode; {указатель на предка}

Items: array[0..m+1] of record   {массив записей} Value: ItemType; NextNode: PBTreeNode; end; end;

TBTree = PBTreeNode;

У элемента Items[0] будет использоваться только поле NextNode. Дополнительный элемент Items[NumberOfItems + 1] предназначен для обработки переполнения, о чем будет рассказано ниже, при описании алгоритма добавления элемента в B-дерево.

Поскольку дерево упорядочено, то

Items[1].Value<Items[2].Value<...<Items[Count].Value.

Указатель Items[i] .NextNode указывает на поддерево элементов, больших Items[i].Value и меньших Items[i + 1].Value. Понятно, что указатель Items[0] .NextNode будет указывать на поддерево элементов, меньших Items[1] .Value, а указатель

Items[Count] .NextNode - на поддерево элементов, больших Items[Count] .Value.

У корневой вершины PreviousNode будет равен nil.

1.4.2.2. Основные операции

Основные операции, производимые с B-деревьями:

• поиск элемента;
• добавление элемента;
• удаление элемента.

При рассмотрении этих основных операций будут разбираться небольшие деревья, хотя в реальности B-деревья применяются при работе с большими массивами информации. Кроме того, для наглядности, на рисунках будут опускаться поля указателей.

Поиск элемента будем начинать с корневой вершины. Если искомый элемент присутствует в загруженной вершине, то завершаем поиск с положительным ответом, иначе загружаем следующую вершину, и так до тех пор, пока либо найдем искомый элемент, либо не окажется следующей вершины (пришли в лист B-дерева).

Посмотрим на примере, как это реализуется (рис. 20).

Будем искать элемент 11. Сначала загрузим корневую вершину. Эта вершина содержит элементы 5 и 13. Искомый элемент больше 5, но меньше 13. Значит, следует идти по ссылке, идущей от элемента 5. Загружаем следующую вершину (с элементами 8 и 10). Эта вершина тоже не содержит искомого элемента. Замечаем, что 11 больше 10, следовательно, двигаемся по ссылке, идущей от элемента 10. Загружаем соответствующую вершину (с элементами 11 и 12), в которой и находим искомый элемент. Итак, в этом примере, чтобы найти элемент, потребовалось три раза обратиться к внешней памяти для чтения очередной вершины.

Если бы в примере осуществлялся поиск, допустим, элемента 18, то, просмотрев три вершины (последняя с элементом 17), было бы обнаружено, что от элемента 17 нет ссылки на поддерево с элементами, большими, чем 17, и на основании этого сделали бы вывод, что элемента 18 в дереве нет.

Теперь приведем точно сформулированный алгоритм поиска элемента Item в B-дереве, предположив, что функция LookFor возвращает номер первого большего или равного элемента вершины (фактически производит поиск в вершине).

function BTree Search(Item: ItemType, BTree: PBTreeNode): boolean; var

CurrentNode: PBTreeNode; Position: integer; begin

BTree_Search := False; CurrentNode := BTree; repeat

{Ищем в текущей вершине}

Position := LookFor(CurrentNode, Item);

if (CurrentNode.Count >= Position) and

(CurrentNode.Items[Position].Value = Item) then begin {Элемент найден} BTree_Search := True; Exit; end;

if CurrentNode.Items[Position-1].NextNode = nil then

{Элемент не найден и дальше искать негде}

break else

{Элемент не найден, но продолжаем поиск дальше} CurrentNode := CurrentNode.Items[Position-1].NextNode; until False; end;

Здесь пользуемся тем, что, если ключ лежит между Items[i].Value и Items[i+1] .Value, то во внутреннюю память надо подкачать вершину, на которую указывает Items[i] .NextNode.

Заметим, что для ускорения поиска ключа внутри вершины (функция LookFor), можно воспользоваться бинарным поиском (см. 2.3.1.2).

Учитывая то, что время обработки вершины есть величина постоянная, пропорциональная размеру вершины, временная сложность T(n) алгоритма поиска в B-дереве будет пропорциональна O(h), где h - глубина дерева.

Теперь рассмотрим добавление элемента в B-дерево Для того чтобы B-дерево можно было считать эффективной структурой данных для хранения множества значений, необходимо, чтобы каждая вершина заполнялась хотя бы наполовину. Дерево строится снизу. Это означает, что любой новый элемент добавляется в лист. Если при этом произойдет переполнение (на этот случай в каждой вершине зарезервирован лишний элемент), т. е. число элементов в вершине превысит NumberOfItems, то надо будет разделить вершину на две вершины и вынести средний элемент на верхний уровень. Может случиться, что при этой операции на верхнем уровне тоже получится переполнение, что вызовет еще одно деление. В худшем случае эта волна делений докатится до корня дерева.

В общем виде алгоритм добавления элемента Item в B-дерево можно описать следующей последовательностью действий:

1. Поиск среди листьев вершины Node, в которую следует произве- 
сти добавление элемента Item.

2. Добавление элемента Item в вершину Node.

3. Если Node содержит больше, чем NumberOfItems элементов 
(произошло переполнение), то:

• делим Node на две вершины, не включая в них средний элемент;
• Item := средний элемент Node;
• Node := Node.PreviousNode;
• переходим к пункту 2.

Заметим, что при обработке переполнения надо отдельно обработать случай, когда Node - корень, так как в этом случае Node.PreviousNode  = nil.

Рассмотрим пример. Возьмем дерево (рис. 21, а) и добавим в него элемент 13.

Двигаясь от корня, найдем лист, в который следует добавить искомый элемент. Таким узлом в нашем случае окажется лист, содержащий элементы 11 и 12. Добавим в него элемент 13 (рис. 21, б).

Понятно, что при этом получается переполнение. При его обработке вершина, содержащая элементы 11, 12 и 13, разделится на две части: вершину с элементом 11 и вершину с элементом 13, - а средний элемент 12 будет вынесен на верхний уровень (рис. 21, в).

 

 

Опять получилось переполнение, при обработке которого вершина, содержащая элементы 8, 10 и 12 разделится на две вершины: вершину с элементом 8 и вершину с элементом 12, - а средний элемент 10 будет вынесен на верхний уровень (рис. 21, г).

Получилось переполнение в корне дерева. Как оговаривалось ранее, этот случай надо обработать отдельно. Это связано с тем, что здесь необходимо создать новый корень, в который во время деления будет вынесен средний элемент. Теперь полученное дерево не имеет переполнения (рис. 21, д).

В этом случае, как и при поиске, время обработки вершины есть величина постоянная, пропорциональная размеру вершины, а значит, временная сложность T(n) алгоритма добавления в B-дерево будет также пропорциональна O(h), где h - глубина дерева.

Удаление элемента из B-дерева предполагает успешный предварительный поиск вершины, содержащей искомый элемент. Если такая вершина не найдена, то удаление не производится.

При удалении, так же как и при добавлении, необходимо делать так, чтобы число элементов в вершине лежало между NumberOfItems/2 и NumberOfItems. Если при добавлении могла возникнуть ситуация переполнения вершины, то при удалении можно получить порожнюю вершину. Это означает, что число элементов в вершине оказалось меньше NumberOfItems/2. В этом случае надо посмотреть, нельзя ли занять у соседней вершины слева или справа («перелить» часть элементов от нее) некоторое количество элементов так, чтобы их (элементов) стало поровну и не было порожних вершин. Такое переливание возможно, если суммарное число элементов у данной вершины и соседней больше или равно NumberOfItems.

Если переливание невозможно, то объединяем данную вершину с соседней. При этом число элементов в родительской вершине уменьшится на единицу и может статься, что опять получаем порожнюю вершину. В худшем случае волна объединений дойдет до корня. Случай корня надо обрабатывать особо, потому что в корне не может быть менее одного элемента. Поэтому, если в корне не осталось ни одного элемента, надо сделать корнем ту единственную вершину, на который ссылается корень через ссылку Node.Items[0] .NextNode, а старый корень удалить.

Приведем алгоритм удаления элемента Item из B-дерева:

1. Поиск вершины Node, которая содержит элемент Item. Если такой вершины нет, то удаление невозможно.
2. Если Node - лист, то удалить из Node элемент Item, иначе заменить элемент Item узла Node на самый левый элемент правого поддерева элемента Item (тем самым сохраняется упорядоченность дерева: аналогично можно заменять элемент Item на самый правый элемент левого поддерева), Node := вершина, из которой был взят элемент для замены.
3. Если в Node меньше NumberOfItems/2 элементов (получилась порожняя вершина), то:

 

• выбрать две соседние вершины Neighbor1 и Neighbor2: одна из них - Node, вторая - ее левая или правая ближайшие;
• если в Neighbor1 и Neighbor2 в сумме меньше чем NumberOfItems элементов, то слить вершины Neighbor1 и Neighbor2 иначе перераспределить элементы между Neighbor1 и Neighbor2 так, чтобы количество элементов в них не отличалось больше чем на единицу, Node := родительская вершина Neighbor1 и Neighbor2.

4. Если Node не корень дерева, то перейти к пункту 3.

5. Если корень дерева пуст, то удалить его. Новым корнем дерева 
будет та единственная вершина, на которую осталась ссылка в старом 
корне.

Рассмотрим работу алгоритма на примере. Возьмем дерево, получившееся в предыдущем примере после добавления элемента (рис. 22, а).

Будем удалять из этого дерева элемент 10. Сначала надо, двигаясь от корня, найти вершину дерева, содержащую этот элемент. Он находится в корне. Теперь поскольку элемент находится не в листовом узле, надо заменить его, например, на самый левый элемент правого поддерева. Делаем один шаг вправо и попадаем в корень правого поддерева. Теперь пока не достигнем листа, переходим на самого левого потомка.

Таким образом, найдем вершину, из которой позаимствуем элемент для замены удаленного элемента 10. В найденной вершине возьмем самый левый элемент. Таковым оказывается 11. Произведем замену элемента 10 на 11 и удалим элемент 11 (рис. 22, б).

Теперь проверим вершину, из которой был удален элемент, не стала ли она порожней. Число элементов в вершине равно нулю. Это меньше половины размера вершины. Следовательно, вершина порожняя. Выберем две соседние вершины: одна - та, из которой было удалено 11,

 

 

вторая - соседняя вершина с числом 13. Суммарное число элементов в этих вершинах не превышает максимального размера вершины, значит, нам следует произвести слияние вершин. При слиянии элемент 12 родителя попадает в результирующий узел и удаляется из родителя (рис.

22, в).

Теперь переходим к родителю, из которого был удален элемент, и проверяем, не является ли он порожним. Опять имеем порожнюю вершину, и необходимо выбрать две соседние вершины (в данном случае: вершину, из которой был удален элемент 12 и вершину с элементом 17) и произвести слияние двух вершин. При слиянии получается вершина с элементами 14 и 17, где 14 позаимствовано у родителя. Естественно, элемент 14 из родителя удаляется (рис. 22, г).

Поскольку опять был удален элемент родителя, то переходим к родителю и повторяем процесс проверки и слияния. Получаем вершину с элементами 5 и 11, где 5 позаимствовано у родителя и удалено из него (рис. 22, д).

Опять переходим к родителю. Поскольку родитель оказывается корнем, то цикл обработки порожних вершин заканчивается. Осталось проверить, не пуст ли корень дерева. Корень дерева пуст, поэтому его можно удалить. Новым корнем дерева будет та единственная вершина, на которую есть ссылка в старом корне. Это вершина с элементами 5 и 11 (рис. 22, е).

В этом случае, как и при поиске, время обработки вершины есть величина постоянная, пропорциональная размеру вершины, а значит, временная сложность T(n) алгоритма удаления из B-дерева будет также пропорциональна O(h), где h - глубина дерева.

1.4.2.3. Общая оценка B-деревьев

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

Ярким примером практического применения B-деревьев является файловая система NTFS, где B-деревья применяются для ускорения поиска имен в каталогах. Если сравнить скорость поиска в этой файловой системе и в обычной FAT на примере поиска на жестком диске большого объема или в каталоге, содержащем очень много файлов, то можно будет констатировать превосходство NTFS. Поиск файла в каталоге всегда предшествует запуску программы или открытию документа.

B-деревья обладают прекрасным качеством: во всех трех операциях над данными (поиск/удаление/добавление) они обеспечивают сложность порядка O(h), где h - глубина дерева. Это значит, что чем больше узлов в дереве и чем сильнее дерево ветвится, тем меньшую часть узлов надо будет просмотреть, чтобы найти нужный элемент. Попробуем оценить зависимость временной сложности операций T(h) от высоты дерева h.

Число элементов в вершине есть величина вероятностная с постоянным математическим ожиданием MK. Математическое ожидание числа вершин равно n/MK ~ n, где n - число элементов, хранимых в B-дереве. Это дает сложность T(h) ~ O(log n), а это очень хороший результат.

Поскольку вершины могут заполняться не полностью (иметь менее NumberOfItems элементов), то можно говорить о коэффициенте использования памяти. Существуют доказательства, что память будет использоваться в среднем на ln2-100% ~ 69,3%.

В отличие от сбалансированных деревьев, которые рассматриваются далее, B-деревья растут не вниз, а вверх. Поэтому (и из-за разной структуры узлов) алгоритмы включения или удаления принципиально различны, хотя цель их в обоих случаях одна - поддерживать сбалансированность дерева.

Идея внешнего поиска с использованием техники B-деревьев была предложена в 1970 году Р. Бэйером и Э. Мак-Крэйтом и независимо от них примерно в то же время М. Кауфманом. Естественно, что за это время было предложено ряд усовершенствований B-деревьев, связанных с увеличением коэффициента использования памяти и уменьшением общего количества расщеплений.

Одно из таких усовершенствований было предложено Р. Бэйером и Э. Мак-Крэйтом и заключалось в следующем. Если вершина дерева переполнена, то прежде чем расщеплять эту вершину, следует посмотреть, нельзя ли «перелить» часть элементов соседям слева и справа. При использовании такой методики уменьшается общее количество расщеплений и увеличивается коэффициент использования памяти.