Лабораторная работа №5

Управление B-деревом

1. Цель работы

Цель данной работы:

1. Изучить принцип хранения множества значений в B-дереве.
2. Программно реализовать 3 основных операции: поиск, добавление, удаление элемента.

2. Краткие сведения из теории

2.1. Что такое B-дерево

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

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

Как мы уже видели, очень эффективным является хранение множества в виде дерева. Поэтому попробуем создать такое дерево, которое будет обеспечивать при своем обслуживании относительно небольшое количество обращений к внешней памяти.

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

Узел такого дерева назовем страницей поиска. Рассмотрим структуру узла B-дерева.

В каждом узле мы будем хранить не более NumberOfItems записей. Также нам надо будет хранить текущее количество записей в узле. Для удобства возврата назад к корню дерева будем запоминать для каждого узла указатель на его узел-предок.

Type
  PBTreeNode = ^TBTreeNode;
  TBTreeNode = record {узел дерева}
    Count: Integer;
    PreviousNode: PBTreeNode;
    Items: array[0..NumberOfItems+1] of record
      Value: ItemType;
      NextNode: PBTreeNode;
    end;
  end;

У элемента 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.

Type
TBTree = TBTreeNode;

Прежде чем рассматривать алгоритмы, соберем воедино все требования к B-дереву:

1. каждый узел имеет не более NumberOfItems сыновей;


2. каждый узел, кроме корня, имеет не менее NumberOfItems/2 сыновей;


3. корень, если он не лист, имеет не менее 2-х сыновей;


4. все листья расположены на одном уровне (дерево сбалансировано);


5. нелистовой узел с k сыновьями содержит не менее k-1 ключ.

Из всего вышесказанного можно сразу сформулировать алгоритм поиска элемента в B-дереве.

2.2. Поиск элемента в B-дереве

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

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

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

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

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

function BTree.Exist(Item: ItemType): Boolean;
Var
  CurrentNode: PBTreeNode;
  Position: Integer;
begin
  Exist := False;
  CurrentNode := @BTree;
  Repeat
    Position := LookFor(CurrentNode, Item);
    if (CurrentNode.Count>=Position)and
     (CurrentNode.Items[Position].Value=Item) then
    begin
      Exist := 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), можно воспользоваться дихотомическим поиском, который описан ранее в главе, где разбирались способы хранения множества элементов в последовательном массиве.

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

2.3. Добавление элемента в B-дерево

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

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

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

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

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

Посмотрим, как это будет работать, на примере.

Возьмем нарисованное ниже дерево и добавим в него элемент 13.

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

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

Мы опять получили переполнение, при обработке которого узел, содержащий элементы 8, 10 и 12 разделится на два узла: узел с элементом 8 и узел с элементом 12, – а средний элемент 10 будет вынесен на верхний уровень. И теперь дерево примет такой вид:

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

Теперь полученное дерево не имеет переполнения.

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

2.4. Удаление элемента из B-дерева

Удаление элемента из 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 элементов (произошло антипереполнение), то

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

• Node = родительский узел Neighbor1 и Neighbor2.

4. Если Node не корень дерева, то переход к пункту 3.
5. Если корень дерева пуст, то удалим его. Новым корнем дерева будет тот единственный узел, на который осталась ссылка в старом корне.

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

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

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

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

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

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

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

2.5. Еще немного о B-деревьях

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

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

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

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

Поскольку узлы могут заполняться не полностью (иметь менее NumberOfItems элементов), то можно говорить о коэффициенте использования памяти. Эндрю Яо доказал, что среднее число узлов после случайных вставок при больших n и NumberOfItems составит N/(m*ln(2))+F(n/m²), так что память будет использоваться в среднем на ln(2)*100%» 69,3%.

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

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

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

3. Контрольные вопросы

1. Перечислить требования, которым должны удовлетворять B-деревья.
2. Что такое страница поиска? Какой метод поиска из разобранных во 2-ой лабораторной работе наиболее подходит для поиска внутри страницы поиска?
3. В чем сходство и в чем различие сбалансированных и B-деревьев?
4. Какова сфера применения B-деревьев? Почему в этой сфере они предпочтительнее сбалансированных деревьев?
5. Описать словесно процедуру модификации элемента, содержащегося в B-дереве.
6. Доказать, что все основные операции (добавление/удаление/поиск/модификация) могут быть выполнены за T(log(n)) действий.
7. Что такое переполнение? Что такое антипереполение? Привести примеры.
8. В чем заключается усовершенствование предложенное самими же авторами идеи B-деревьев Р.Бэйером и Э.Мак-Крэйтом? (Подсказка: техника «переливаний»)

4. Методические указания

Перед выполнением индивидуального задания ознакомиться с тем, что такое B-дерево, управлением таким деревом, анализом алгоритмов управления.

При выполнении индивидуального задания придерживаться следующей последовательности действий:

1. изучить словесную постановку задачи;
2. разработать программу, решающую поставленную задачу;
3. оттестировать и отладить программу;
4. написать и представить к защите отчет по работе.

5. Содержание отчета

1. Титульный лист.
2. Словесная постановка задачи.
3. Описание использованного способа хранения B-дерева во внешней памяти.
4. Листинг программы, работающей с B-деревом.
5. Ответы на контрольные вопросы по согласованию с преподавателем.

6. Варианты индивидуальных заданий

В этой лабораторной работе задание одно общее для всех.

Требуется организовать хранение B-деревьев во внешней памяти. Реализовать три основных операции: поиск/добавление/удаление.