Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l дерево
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
инимальное значение ключа у записей, входящих в блок. Последовательность блоков представляет собой последний уровень В-дерева. Строится индекс предыдущего уровня. Записи этого уровня содержат значение ключа блока следующего уровня и указатель - адрес связи соответствующего блока ; записи этого уровня также объединяются в блоки. Затем аналогично строится индекс более высокого уровня и т.д., пока количество записей индекса на определенном уровне будет не более установленного числа записей в блоках.
В В-дереве не должно быть блоков, заполненных меньше, чем наполовину. Значение ключа первой записи индексного блока пропускается.
Каждая нелистовая вершина Б-дерева имеет вид:
Здесь pi представляет собой указатель на i -го потомка, а ki - значение ключа поиска (указатели на записи основного файла ради простоты не указаны). Для любого i в диапазоне [1, m-1] все ключи, расположенные в поддереве, на которое указывает указатель pi, находятся в диапазоне [ki, ki+1]. Соответственно, все ключи поддерева p0 будут меньше k1, а все ключи поддерева pm- больше km.
Поиск некоторого k ключа в Б-дереве происходит следующим образом. Начиная с корневой вершины выполняется следующая последовательность действий:
Просматриваются ключи k1, k2, , km, Если искомый ключ k найден, то по соответствующему указателю извлекается запись основного файла. Для поиска ключа в вершине может использоваться либо простой последовательный поиск, если m невелико, или двоичный поиск, для достаточно больших m.
Если ki< k< ki+1 для i в диапазоне [1, m-1], то поиск продолжается на странице pi.
Если k< k1, то поиск продолжается на странице p0.
Если k>km, то поиск продолжается на странице pm.
При вставке ключа сначала происходит поиск соответствующей вершины (очевидно, что это будет листовая вершина). Затем происходит следующие операции:
Если найденная вершина содержит менее 2*n ключей, то ключ просто добавляется к данной вершине.
Если страница уже заполнена, то она разделяется на две. При этом 2*n из 2*n+1 ключей пополам (с учетом порядка) распределяются между получившимися вершинами. Центральный ключ (по значению) помещается в родительскую вершину. При этом может произойти ее разделение.
Когда происходит разделение корневой вершины, Б-дерево вырастает на один уровень.
При удалении из Б-дерева происходит балансировка и слияние страниц. Процедуру удаления можно описать следующим образом:
Если удаляемый ключ находится на листовой вершине, то он просто удаляется.
Если удаляемый ключ находится на промежуточной вершине, то он заменяется на смежный элемент, который расположен на листовой вершине.
Если в результате удаления количество ключей вершины стало меньше n, то выполняется балансировка - ключи поровну распределяются между данной, родительской и смежной вершинами.
Если количество ключей на смежной вершине равно n, то балансировка невозможна, но можно слить данную и смежную вершины, заняв один ключ из родительской. Это может привести в свою очередь к балансировке или слиянию на следующем уровне.
Обычно В-дерево храниться в файле по вершинам - каждая вершина занимает виртуальный блок файла, а значит, требует одной операции ввода/вывода. Порядок дерева зависит от размера блока и от размера ключа поиска. Чем больше количество ключей располагается в блоке, тем меньше будет операции ввода/вывода, однако больше операций потребуется для обработки отдельного блока (например, при поиске). Уменьшение количества ключей в блоке приводит к увеличению операций ввода/вывода. На практике критическим местом обычно является именно ввод/вывод, соответственно стремятся увеличивать количество ключей в блоке. Это тем более важно, потому, что доступ к блокам происходит в порядке близком к случайному.
2. Программная реализация
.1 Типы данных
Данная программа реализована на объектно-ориентированном языке Delphi. Состоит из 2-x модулей и одной формы.
В программе использованы следующие типы данных:
Key: array [1..KEYS] of integer - массив, хранящий ключи записей.
Child: array [0..KEYS] of TBTreeNode - массив указателей на другие записи.
Сразу можно заметить, что массив Key можно сделать типом record и задать ему тем самым любую структуру. В виду острой нехватки времени был выбран именно просто массив ключей, с которым работать намного быстрее. В соответствующих местах в коде программы, при изменении типа массива Key и соблюдении соответствующих индексов, остается лишь необходимым прописать заполнение и обработку соответствующих полей.
.2 Добавление элемента в В-дерево
Вставка элемента производится вызовом процедуры TBTree.Add(new_key: integer), которая со вспомогательными параметрами вызывает процедуру TBTree.AddNode(var node: TBtreeNode; new_key: Integer;
var up_node: TBtreeNode; var up_key: Integer; var split: Boolean). Именно эта процедура является основной. Сначала проверяем не пуст ли корень, если пуст - вставляем первый ключ, иначе мы проверяем наш сегмент дальше.
Если мы находим что ключ не в этом сегменте, то рекурсивно вызываем процедуру AddNode для узла потомка. Если же наш узел должен находиться в этом сегменте, то проверяем место в сегменте, при условии что он уже полон вызываем процедуру для дробления нашего блока SplitNode, иначе у нас еще есть место и вставка производиться через процедуру AddWithRoom (рисунок 1).
Рисунок 1 - Алгоритм добавления элемента
Процедура AddWithRoom при необходимости сдвигает элементы в блоке вправо и ставит новый элемент на освободи