Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l дерево

 

Курсовая работа

по дисциплине

Базы данных

тема:

Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l дерево

Содержание

Введение

. Представление файлов в виде В-дерева

. Программная реализация

.1 Типы данных

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

.3 Поиск элемента

.3 Удаление элемента

. Пример работы программы

Заключение

Список литературы

Приложение А Листинг программы

Введение

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

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

В этом плане очень удобно использовать так называемые В-деревья, так как эти деревья сбалансированы и упорядочены, следовательно и доступ к необходимому узлу получается довольно быстро.

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

написание процедуры, реализующей добавление записи в базу данных;

написание процедуры, производящей разбиение блоков записей;

написание процедуры поиска и удаления элементов по ключу;

написание процедуры, производящей балансировку и слияние записей в блоке;

создание приложения, способного производить вышеперечисленные действия.

1. Представление файлов в виде В-дерева

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

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

Однако использование таких структур для организации индексов во внешней памяти оказывается крайне неэффективным из-за больших затрат на ввод вывод. Действительно, поскольку теперь вершины располагаются не в оперативной памяти, а на внешних устройствах, то каждое обращение к вершине (при поиске или в ходе балансировки) требует отдельной операции чтения или записи. Таким образом, если дерево содержит, например 1000000 вершин, то в среднем может потребоваться около 20 операций обращения к внешней памяти. Количество таких обращений будет больше, если происходит балансировка.

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

Весьма распространенный в настоящее время подход к организации упорядоченных индексов был предложен в 1970г. Р. Бэйером и Э. Мак-Kрейтом. Предложенные ими структуры получили название В-деревьев. В-дерево представляет собой сильно ветвящееся дерево, обладающее следующими свойствами:

Каждая вершина может содержать не более 2n ключей.

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

Каждая вершина либо представляет собой лист и не имеет потомков, либо имеет в точности m+1 потомка, где m - количество ключей в вершине.

Все листовые вершины располагаются на одном уровне.

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

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

Каждая нелистовая вершина Б-дерева имеет вид:

<p0, k1, p1, k2, p2, . . ., pm-1, km, pm>

Здесь 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 при необходимости сдвигает элементы в блоке вправо и ставит новый элемент на освободившееся место.

.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 для подсчета количества сегментов в В-дереве, так как визуально мы не можем их рассмотреть. За это количество следить переменная NodesAllocated.

Порядок В-дерева определен как ORDER=2, соответственно ключей в сегменте может быть от 2 до 4, а ключей от 3 до 5.

Испытание начинается с добавления. Первоначально, количество сегментов равно 0. При добавлении ключа 3 появился один сегмент (рисунок 4).

Рисунок 4 - Добавление элемента

После добавления ключей со значениями 2, 5, 7 - количество сегментов не изменилось. Теперь количество ключей максимально, следовательно при добавления любого ключа произойдет дробление сегмента. Добавили ключ со значением 4, количество сегментов стало равным 3. Ввели значение ключа равное 3 и нажали кнопку «Поиск». Программа выдала сообщение «Узел с таким элементом есть в базу» (рисунок 5).

Рисунок 5 - Поиск записи по ключу

Тут же удалили запись под 5 ключом - количество сегментов вновь уменьшилось до 1. При удалении остальных элементов количество сегментов достигло 0 (рисунок 6).

Рисунок 6 - Результат после удаления всех элементов

При постоянном добавлении ключей наблюдалось следующее количество сегментов: 1, 3, 4, 5, 6, 9, 10, 11, 12, 14, 15, 16, 17. При другой попытке заполнения после 15 затем сразу следовало 17 сегментов. Можно сделать вывод, что от значения ключа зависит все, как уже говорилось ранее, в самом худшем случае может получиться наравне с рекурсивным объединением, рекурсивное дробление.

Заключение

В ходе данной курсовой работы были подробно рассмотрены варианты работы с организацией базы данных с помощью сбалансированных деревьев, а именно с помощью В-деревьев. Были рассмотрены только принципы такой организации, методы добавления, поиска и удаления элементов из нашей структуры. При подготовке к реализации поставленной задачи были изучены и рассмотрены материалы Всемирной сети Интернет и Научной библиотеки ОрелГТУ.

Кроме того, была реализована программа, осуществляющая добавление, поиск и удаление записей из В-дерева.

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

Таким образом, все поставленные задачи были успешно выполнены.

Список литературы

1.Род Стивенс, Delphi. Готовые алгоритмы: Переводс англ.- М.: ДМК Пресс, 2001.-384с: ил.

2.Карпатов Д.С. Базы данных в Delphi 7.Самоучитель . СПб.-Наука и техника, 2006.

Приложение А (обязательное)

Листинг программы

unit BTree;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, BTreeClass;

= class(TForm): TEdit;: TButton;: TButton;: TButton;: TLabel;: TLabel;: TMemo;: TEdit;AddButtonClick(Sender: TObject);FormCreate(Sender: TObject);FormClose(Sender: TObject; var Action: TCloseAction);Edit1Change(Sender: TObject);RemoveButtonClick(Sender: TObject);SearchButtonClick(Sender: TObject);

{ Private declarations }

{ Public declarations };

: TForm1;:TBTree;

{$R *.dfm}

TForm1.AddButtonClick(Sender: TObject);.Add(StrToInt(Edit1.Text){,Edit2.Text});.Lines.Add(Edit1.Text);.Caption:=IntToStr(TBTreeNode.NumAllocated);.Text:='';;

TForm1.FormCreate(Sender: TObject);.Clear;:=TBTree.Create;;

TForm1.FormClose(Sender: TObject; var Action: TCloseAction);.Free;;TForm1.Edit1Change(Sender: TObject);.Enabled:=(Edit1.Text<>'');.Enabled:=(AddButton.Enabled and Tree.NotEmty);.Enabled:=(AddButton.Enabled and Tree.NotEmty);;

TForm1.RemoveButtonClick(Sender: TObject);.Remove(StrToInt(Edit1.Text));.Caption:=IntToStr(TBTreeNode.NumAllocated);.Text:='';;

TForm1.SearchButtonClick(Sender: TObject);.Search(StrToInt(Edit1.Text));.Text:='';;

.

BTreeClass;

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls;= 2; //порядок дерева

KEYS = 2*ORDER; //max кол-во ключей соотв. порядку

type

{ TNode = record:integer;:string[508];; }

= class(TObject) //класс узла дерева

NumKeys:integer; //кол-во ключей в сегменте

Key: array [1..KEYS] of integer; //сегмент: array [0..KEYS] of TBTreeNode; //ссылки на дочерние сегментыCreate;Destroy;override;function NumAllocated:integer;;

= class(TObject):TBTreeNode;Destroy; override;Add(new_key:integer{; new_text:string});AddNode(var node:TBtreeNode; new_key:Integer; var

up_node:TBtreeNode; var up_key:Integer; var

split:Boolean{;new_text,up_text:string});AddWithRoom(node,new_child:TBtreeNode;

spot,new_key:Integer{,new_text:string});SplitNode(node:TBtreeNode; spot:Integer; var up_key:Integer;

var up_node:TBtreeNode);Remove(Value:integer);RemoveFromNode(node:TBTreeNode; value:integer; var

too_small:Boolean);SwapNode(node:TBtreeNode; key_num:Integer;

down_node:TBtreeNode; var too_small:Boolean);TooSmall(parent, child:TBtreeNode; child_num:Integer; var

too_small:Boolean);NotEmty:Boolean;Search(value:integer);SearchFromNode(node:TBTreeNode; value:integer; var

search:Boolean);;

BTree;

:integer;

{ TBTree }

TBTree.Add(new_key: integer{; new_text:string});up_node,old_root:TBTreeNode;_key:integer;:boolean;(Root,new_key,up_node,up_key,split{,new_text,up_text});Split_root:=Root;:=TBtreeNode.Create;.Key[1]:=up_key;

// Root.Key[1].text:=up_text;.Child[0]:=old_root;.Child[1]:=up_node;.NumKeys:=1;;

TBTree.AddNode(var node: TBtreeNode; new_key: Integer;up_node: TBtreeNode; var up_key: Integer; var split: Boolean{;

new_text:string});branch:integer;(node=nil) //если узел пуст, присваиваем ключ_node:=nil;_key:=new_key;

// up_text:=new_text;

split:=true; //теперь мы можем добавить узел

exit;;branch:=0 to node.NumKeys-1 do //смотрим по какой ветке нам идти(node.Key[branch+1]>new_key) then break;(node.Child[branch],new_key,up_node,up_key,split); //идем далее

по ветке

if split(node.NumKeys<KEYS) //если сегмент не полон, хотя бы одна ячейка

пуста

then//добавляем(node,up_node,branch+1,up_key);

split:=False; //это чтобы не создавать корень

end//иначе разбиваем сегмент(node,branch+1,up_key,up_node);;;

TBTree.AddWithRoom(node, new_child: TBtreeNode;

spot,new_key: Integer);i:integer;.NumKeys:=node.NumKeys+1; //добавляем ключ в сегментi:=node.NumKeys downto spot+1 do //сдвигаем элементы сегмента.Key[i]:=node.Key[i-1];

// node.Key[i].text:=node.Key[i-1].text;.Child[i]:=node.Child[i-1];;.Key[spot]:=new_key; //вставляем наш новый элемент

node.Child[spot]:=new_child;;TBTree.Destroy;.Free;;;

TBTree.NotEmty: Boolean;:=(Root<>nil);;

TBTree.Remove(Value: integer);old_root:TBTreeNode;_small:Boolean;(Root,value,too_small);

if Root.NumKeys<1 //если корень пуст - удалить уровень

then_root:=Root;

Root:=Root.Child[0]; //спускаемся по ссылке к сегменту - это новый

корень

old_root.Child[0]:=nil;_root.Free; //удаляем старый корень;;

TBTree.RemoveFromNode(node: TBTreeNode; value: integer;too_small: Boolean);branch,i:integer;:TBTreeNode;:Boolean;(node = nil) //узел пуст - такого ключа нет('Узла с таким ключом в базе нет');

too_small:=False;;;:=False;branch:= 1 to node.NumKeys do //просматриваем сегмент, ищем

ветку(value<=node.Key[branch]) then:=(value=node.Key[branch]); //нашли?;;;:= node.Child[branch - 1]; //(match) then(child = nil) then //элемент в этом узле//удаляем его.NumKeys := node.NumKeys - 1;_small := (node.NumKeys < ORDER); //сегмент маленький?i := branch to node.NumKeys do.Key[i] := node.Key[i + 1];

node.Key[node.NumKeys + 1] := 0;else begin //это не лист, значит надо взять элемент слева из листа

SwapNode(node, branch, child, too_small);

if (too_small) then //если теперь лист оказался маленьким - слить

сегменты

TooSmall(node, child, branch - 1, too_small);

end;else begin //рекурсивно ищем удаляемый ключ для ребенка

RemoveFromNode(child, value, too_small);

if (too_small) then //если сегмент меленький - перестроить его

TooSmall(node, child, branch - 1, too_small);;;

TBTree.Search(value: integer);search:Boolean;(Root,value,search);

{ if (fl<>False)ShowMessage('Узел с ключом '+Form1.Edit1.Text+' есть в базе'); };

TBTree.SearchFromNode(node: TBTreeNode; value: integer; var

search:Boolean);branch,i:integer;:TBTreeNode;,fl:Boolean;(node = nil) //узел пуст - такого ключа нет('Узла с таким ключом в базе нет');

search:=False;;;:=False;:=False;branch:= 1 to node.NumKeys do(value<=node.Key[branch]) then:=(value=node.Key[branch]);;;;(match) then('Узел с ключом '+Form1.Edit1.Text+' есть в базе');:=true;;:= node.Child[branch - 1]; //(match)(child = nil) and (not fl)('Узел с ключом '+Form1.Edit1.Text+' есть в базе');SearchFromNode(child, value, search);;

TBTree.SplitNode(node: TBtreeNode; spot: Integer;up_key: Integer; var up_node: TBtreeNode);i,return_key: integer;_node,right_child0:TBTreeNode;_node:=TBTreeNode.Create; //создаем новый сегмент

if (spot<=ORDER+1) //смотрим куда нам надо вставлять новый ключ//проверяем место вставки по отношению к середине сенмента(spot=ORDER+1) //вставлять надо на место сегмента, где

ключ=середина+1//объявляем тогда новый узел - корнем

return_key:=up_key;_child0:=up_node;

end//иначе нам необходимо добавление в начало старого сегмента_key:=node.Key[ORDER]; //сохраняем ключ последнего эл-та в

первой половине сегмента

right_child0:=node.Child[ORDER]; //сохраняем ссылку.Key[ORDER]:=0; //обнуляем ключ.Child[ORDER]:=nil; //и сбрасываем ссылкуi:=ORDER downto spot+1 do //вставляем нов.узел в сегмент.Key[i]:=node.Key[i-1]; //переписываем.Child[i]:=node.Child[i-1];;.Key[spot]:=up_key;.Child[spot]:=up_node;;i:=1 to ORDER do

begin //заносим вторую половину старого сегмента в первую нового

return_node.Key[i]:=node.Key[i+ORDER];_node.Child[i]:=node.Child[i+ORDER];

node.Key[i+ORDER]:=0; //вторую половину старого сегмента обнуляем

node.Child[i+ORDER]:=nil; //и сбрасываем ссылки;

else //иначе наш новый ключ должен быть самым правым:=spot-ORDER-1; //ставим тогда ветвь для нового сегмента в начало_key:=node.Key[ORDER+1]; //сохраняем ключ и левуюот него

ссылку

right_child0:=node.Child[ORDER+1];.Key[ORDER+1]:=0; //обнуляем ключ и скидываем ссылку.Child[ORDER+1]:=nil;i:=1 to spot-1 do

begin //если надо - переносим узлы второй половины дробимого

сегмента

return_node.Key[i]:=node.Key[i+ORDER+1];_node.Child[i]:=node.Child[i+ORDER+1];.Key[i+ORDER+1]:=0; //обнуляем эти узлы.Child[i+ORDER+1]:=nil;;_node.Key[spot]:=up_key; //вставляем новый ключ_node.Child[spot]:=up_node; //и ссылкуi:=spot+1 to ORDER do

begin //освобождаем вторую половину старого сегмента, переносим в

новый

return_node.Key[i]:=node.Key[i+ORDER];_node.Child[i]:=node.Child[i+ORDER];.Key[i+ORDER]:=0;.Child[i+ORDER]:=nil;

end;;.NumKeys:=ORDER; //задаем для новых сегментов кол-во ключей_node.NumKeys:=ORDER;_node.Child[0]:=right_child0; //определяем ссылку нового

сегмента, как ту что сохранена в буфере

up_node:=return_node;_key:=return_key;;

TBTree.SwapNode(node: TBtreeNode; key_num: Integer;_node: TBtreeNode; var too_small: Boolean);rightmost_child:TBtreeNode;:integer;:= down_node.NumKeys; //проверяем самый правый элемент_child := down_node.Child[num];(rightmost_child = nil)//элемент найден, меняем

node.Key[key_num] := down_node.Key[num]; //ставим последний

элемент на место удаляемого_node.Key[num] := 0; //сам элемент обнуляем_node.NumKeys := num - 1; //кол-во ключей стало меньше_small := (down_node.NumKeys < ORDER); //проверяем кол-во

ключей//иначе мы еще не в листе, продолжаем спускаться

SwapNode(node, key_num, rightmost_child, too_small);

if (too_small) then // если сегмент слишком маленький

TooSmall(down_node,rightmost_child,down_node.NumKeys,too_small);;;

TBTree.TooSmall(parent,child:TBtreeNode; child_num:Integer;

var too_small:Boolean);num_in_parent,num_in_sibling:integer;_to_move,i:integer;:TBtreeNode;_in_parent := parent.NumKeys;

if (child_num < num_in_parent) //смотрим количество ключей у смежных

сегментов//проверяем смежный сегмент справа, хватит ли ему ключей

child_num := child_num + 1;:= parent.Child[child_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) //ключей хватает?i := 1 to num_to_move - 1 do//тогда переносим.Key[i + ORDER] := sibling.Key[i];.Child[i + ORDER] := sibling.Child[i];.Key[i] := 0;.Child[i] := nil;;.Key[child_num] := sibling.Key[num_to_move]; //определяем

родителя.Child[child_num] := sibling;.Child[0] := sibling.Child[num_to_move];//начинаем заполнять

пустое место_in_sibling := num_in_sibling - num_to_move;i := 1 to num_in_sibling do

begin //переносим элементы в смежном сегменте

sibling.Key[i] := sibling.Key[i + num_to_move];.Child[i] := sibling.Child[i + num_to_move];.Key[i + num_to_move] := 0; //те что перенесли обнуляем.Child[i + num_to_move] := nil;;.NumKeys := num_in_sibling; //обновляем кол-во ключей в брате.NumKeys := ORDER - 1 + num_to_move; //в сегменте, где удаляли_small := False; //говорим что здесь уже все в порядке//иначе не хватает ключей для перерасперделения - необходимо

слияние

begini := 1 to ORDER do

begin //переносим из брата в сегмент, из которого удаляли

child.Key[i + ORDER] := sibling.Key[i];.Child[i + ORDER] := sibling.Child[i];.Key[i] := 0;.Child[i] := nil;;i := child_num to num_in_parent - 1 do

begin //аполняем пустое место в родителе

parent.Key[i] := parent.Key[i + 1];.Child[i] := parent.Child[i + 1];;.Key[num_in_parent] := 0; //обнуляемпоследний элемент.Child[num_in_parent] := nil;

child.NumKeys := KEYS; //кол-во ключей обновляем

parent.NumKeys := num_in_parent - 1;.Free; //удаляем брата_small := (parent.NumKeys < ORDER); //проверяем кол-во ключей

родителя

end;else begin //справа правильных смежных нет, проверяем левого

sibling := parent.Child[child_num - 1];_in_sibling := sibling.NumKeys + 1;_to_move := (num_in_sibling - ORDER) div 2;

if (num_to_move > 0) then//подходит, освобождаем место в ребенке

for i := ORDER - 1 downto 1 do//сдвигаем вправо.Key[i + num_to_move] := child.Key[i];.Child[i + num_to_move] := child.Child[i];

end; //забираем элемент из родителя, заполняем

child.Key[num_to_move] := parent.Key[child_num];.Child[num_to_move] := child.Child[0];_in_sibling := num_in_sibling - num_to_move; //смотрим сколько

отдавать ребенку от смежного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]; //обновляем

ссылку от родителя к смежному

sibling.NumKeys := num_in_sibling - 1; //кол-во ключей обновляем.NumKeys := ORDER - 1 + num_to_move;_small := False;else begin //если недостаточно ключей - сливаем.Key[num_in_sibling] := parent.Key[child_num]; //переносим

элемент родителя к смежному.Child[num_in_sibling] := child.Child[0];

child.Child[0] := nil;i := 1 to ORDER - 1 do //перемещаем значения из ребенка в брата

begin.Key[i + num_in_sibling] := child.Key[i];.Child[i + num_in_sibling] := child.Child[i];.Key[i] := 0;.Child[i] := nil;;.NumKeys := KEYS; //обновляем кол-во ключей

parent.NumKeys := num_in_parent - 1;.Key[child_num] := 0;.Child[child_num] := nil;.NumKeys := 0;.Free; //удаляем пустой сегмент

too_small := (parent.NumKeys < ORDER); //проверяем кол-во ключей

родителя

end;;;

{ TBTreeNode }

TBTreeNode.Create;

begin //создание нового сегмента, кол-во узлов +1

inherited Create;:=NodesAllocated+1;;

TBTreeNode.Destroy;:integer;

begin //удаление сегмента, кол-во сегментов -1

NodesAllocated:=NodesAllocated-1;i:=0 to NumKeys do //освобождение ссылок от ключей[i].Free;;;function TBTreeNode.NumAllocated: integer;//получение кол-ва сегментов:=NodesAllocated;;

.

Курсовая работа по дисциплине Базы данных тема: Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l

Больше работ по теме: