Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l дерево
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
вшееся место.
.NumKeys:=node.NumKeys+1; //добавляем ключ в сегмент
for i:=node.NumKeys downto spot+1 do //сдвигаем элементы сегмента.Key[i]:=node.Key[i-1];.Child[i]:=node.Child[i-1];
end;.Key[spot]:=new_key; //вставляем наш новый элемент
node.Child[spot]:=new_child;
SplitNode сначала создает новый сегмент и проверяет в какой части сегмента должен находится новый ключ. Если он должен быть первым из второй половины, то этот элемент будет предком по отношению к ним, а элементы второй половины переносятся в новый сегмент. Если же в первой половине должна произойти вставка, то последний элемент первой половины становиться предком, остальные элементы сдвигаются вправо в освободившееся место ставится новый ключ. Если же требуется вставка в сегмент, начиная от (порядок дерева+2), то ключ на месте (порядок+1) будет предком, а остальные элементы переходят в новый сегмент. В конце определяем количество ключей каждого сегмента, указываем новые ссылки.
.3 Поиск элемента
Для поиска элемента в В-дереве используются процедуры Search(value:integer) и SearchFromNode(node:TBTreeNode; value:integer, var search:Boolean). Поиск ведется от корня к листьям. Проверяеться корень, если элемент найден, то выводим сообщение что такой элемент найден, иначе смотрим по какой ссылке нам идти. Вызываем рекурсивно SearchFromNode для потомка. Если ссылка равно nil, то такого элемента нет, иначе проверяем далее (рисунок 2).
Рисунок 2 - Алгоритм выполнения поиска
.3 Удаление элемента
В теории удалить элемент так же, как и добавить, но на практике это оказалось намного сложнее. Все из-за того, что при удалении у нас может оказаться, что количество ключей в сегменте меньше половины, тогда приходиться либо перераспределять элементы, любо объединять сегменты.
Удаление начинается также с поиска необходимого элемента. Если мы дошли до листа и дальше идти некуда, то значит такого элемента в дереве нет. Если элемент найден в сегменте, но этот сегмент не является листом, значит нам надо взять последний элемент из левого потомка.
if (rightmost_child = nil)//элемент найден, меняем
node.Key[key_num] := down_node.Key[num]; //ставим последний элемент на место удаляемого_node.Key[num] := 0; //сам элемент обнуляем_node.NumKeys := num - 1; //кол-во ключей стало меньше_small := (down_node.NumKeys < ORDER); //проверяем кол-во ключей.
Количество ключей не меньше половины - это одно из основополагающих сбалансированности, а распределение элементов между сегментами пополам - это для того, что бы не каждый раз при вставке/удалении производить дробление/слияние.
После того как мы взяли элемент из потомка, необходимо проверить количество ключей, если больше половины - удаление закончилось, если нет - проверяем смежный сегмент справа.
num_in_sibling := sibling.NumKeys;_to_move := (num_in_sibling - ORDER + 1) div 2;.Key[ORDER] := parent.Key[child_num];.Child[ORDER] := sibling.Child[0];.Child[0] := nil;(num_to_move > 0) //ключей хватает?
Если у него хватает элементов для перераспределения, то выполняем, если нет - сливаем эти сегменты. Если же этого выполнить не может - проверяем смежный сегмент слева. Если есть элементы, которые можем забрать, то смотрим, сколько есть таких элементов (рисунок 3). После переноса определяем ссылки для ребенка и для родителя:
_in_sibling := num_in_sibling - num_to_move; //смотрим сколько отдавать ребенку от смежного
for i := num_to_move - 1 downto 1 do//переносим элементы.Key[i] := sibling.Key[i + num_in_sibling];.Child[i] := sibling.Child[i + num_in_sibling];.Key[i + num_in_sibling] := 0;.Child[i + num_in_sibling] := nil;;.Child[0] := sibling.Child[num_in_sibling]; //определяем ссылки на детей от ребенка.Child[num_in_sibling] := nil;.Key[child_num] := sibling.Key[num_in_sibling]; //обновляем ссылку от родителя к смежному.NumKeys := num_in_sibling - 1; //кол-во ключей обновляем.NumKeys := ORDER - 1 + num_to_move;
Затем проверяем количество ключей, которое получилось в родителе. В самом худшем случае удаление элемента вызовет рекурсивно слияние вплоть до корня, также как и при добавлении будет происходить дробление.
Рисунок 3 - Алгоритм удаления элемента
3. Пример работы программы
Разработанное приложение имеет удобный интерфейс. На форме имеются следующие объекты:
Edit - для ввода ключа, с которым следует произвести операции добавления/поиска/удаления;
3 кнопки для соответствующих операций добавления/поиска/удаления;
Memo - для отображения ключей, которые были введены в базу (что бы не забыть какие ключи мы добавляли, а какие нет);
Объекты Label для подiета количества сегментов в В-дереве, так как визуально мы не можем их рассмотреть. За это количество следить переменная NodesAllocated.
Порядок В-дерева определен как ORDER=2, соответственно ключей в сегменте может быть от 2 до 4, а ключей от 3 до 5.
Испытание начинается с добавления. Первоначально, количество сегментов равно 0. При добавлении ключа 3 появился один сегмент (рисунок 4).
Рисунок 4 - Добавление элемента
После добавления ключей со значениями 2, 5, 7 - количество сегментов не изменилось. Теперь количество ключей максимально, следовательно при добавления любого ключа произойдет дробление сегмента. Добавили ключ со значением 4, количество сегментов стало равным 3. Ввели значение ключа равное 3 и нажали кнопку Поиск. Программа выдала сообщение Узел с таким элементом есть в базу (рисунок 5).
Рисунок 5 - Поиск записи по ключу
Тут же удалили запись под 5 ключом - количество сегментов вновь уменьшилось до 1. При удалении остальных элементов количество сегментов достигло 0 (рисунок 6).
Рисунок 6 - Результат после удаления всех элементов
При постоянном добавлении ключей наблюдалось следующее количество сегментов