Курсовая работа - Б-деревья во внешней памяти

Подождите немного. Документ загружается.

Оглавление

Введение...............................................................................................................................................................5

1. Разработка приложения, реализующего основные функции работы с Б-деревьями во внешней

памяти................................................................................................................................................................... 6

1.1. Анализ предметной области...................................................................................................................6

1.2. Анализ требований..................................................................................................................................7

1.2.1. Требования к интерфейсу Пользователя...........................................................................................7

1.2.2. Требования к программным средствам.............................................................................................7

2. Проектирование...........................................................................................................................................8

2.1. Проектирование интерфейса пользователя...........................................................................................8

2.2. Проектирование структуры данных.......................................................................................................9

3. Реализация..................................................................................................................................................11

3.1. Основные операции с деревом.............................................................................................................11

3.1.1. Операция вставки ключа...................................................................................................................11

3.1.2. Операция удаления ключа.................................................................................................................15

3.2. Реализация интерфейса.........................................................................................................................18

Заключение........................................................................................................................................................19

Список использованных источников...............................................................................................................20

Приложение А. Модуль класса «B-дерево»....................................................................................................21

Приложение Б. Модуль класса главной формы..............................................................................................33

Приложение В. Модуль класса формы для отображения дерева в традиционной форме...........................39

Диаграмма вариантов использования!

Введение.

С увеличением объемов хранимой и обрабатываемой информации все

важней становится вопрос о выборе структур данных, поскольку именно от них

зависит производительность программ и систем где они используются.

Одной из самых эффективных и в то же время сложных структур является B-

дерево. Её использование впервые было предложено Р. Бэйером и Е. Маккрейтом

в 1970. Вскоре оно стало стандартом де-факто для организации файловых систем

и баз данных. Причины такой популярности, особенности структуры и алгоритмы

работы с ней будут рассмотрены в этой курсовой работе.

Целью работы является разработка функций для работы с B-деревом. Для

достижения цели работы была использована популярная среда разработки Borland

Delphi, которая предоставляет все средства для решения подобных задач.

1. Разработка приложения, реализующего основные функции работы с Б-

деревьями во внешней памяти.

1.1. Анализ предметной области.

В-дерево Т представляет собой корневое дерево, обладающее следующими

свойствами:

1. Каждый узел х содержит следующие поля:

1) n[х], количество ключей, хранящихся в настоящий момент в узле х.

2) Собственно ключи, количество которых равно n[х] и которые хранятся в

невозрастающем порядке, так что key

[х]≤ key

[х]≤…≤ key

n[x]

[х].

3) Логическое значение leaf[х], равное TRUE, если х является листом, и

FALSE, если х — внутренний узел.

4) Индекс, указывающий на местоположение узла в файле.

2. Кроме того, каждый внутренний узел х содержит n[х] +1 указателей с

[х],

[х], с

[х], … , с

n[x]+1

[х] на дочерние узлы. Листья не имеют дочерних узлов,

так что их поля с

не определены.

3. Ключи key

[х] разделяют поддиапазоны ключей, хранящихся в поддеревьях:

если k

— произвольный ключ, хранящийся в поддереве с корнем с

[х], то

≤ key

[х]≤ k

≤ key

[х]≤…≤ key

n[x]

[х] ≤k

n[x]+1

4. Все листья расположены на одной и той же глубине, которая равна высоте

дерева h.

5. Имеются нижняя и верхняя границы количества ключей, которые могут

содержаться в узле. Эти границы могут быть выражены с помощью одного

фиксированного целого числа t≥2, называемого минимальной степенью В-

дерева:

1) Каждый узел, кроме корневого, должен содержать как минимум t -1 ключей.

Каждый внутренний узел, не являющийся корневым, имеет, таким образом,

как минимум t дочерних узлов. Если дерево не является пустым, корень

должен содержать как минимум один ключ.

2) Каждый узел содержит не более 2t-1 ключей. Таким образом, внутренний

узел имеет не более 2t дочерних узлов. Мы говорим, что узел заполнен, если

он содержит ровно 2t-1 ключей.

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

зависит в первую очередь от количества выполняемых операций с диском (чтение

и запись), желательно минимизировать их количество. При этом надо учесть, что

количество обращений к диску для выполнения операций с деревом

пропорционально его высоте.

1.2. Анализ требований.

1.2.1. Требования к интерфейсу Пользователя

При использовании программы пользователю должны быть предоставлены

следующие возможности:

 Сгенерировать дерево из заданного количества ключей;

 Добавить ключ;

 Удалить ключ;

 Найти ключ;

 Сохранить дерево в файле;

 Открыть файл с деревом;

 Просмотреть дерево в наглядном виде.

Для более удобной работы необходимо изображать два дерева: до операции и

после нее.

1.2.2. .Требования к программным средствам

Для выполнения всех требований к интерфейсу пользователя, в реализации

программы необходимо включить функции:

 Прочитать страницу из файла;

 Записать страницу в файл;

 Добавить ключ;

 Удалить ключ;

 Найти ключ;

 Сохранить дерево;

 Восстановить дерево из файла;

Взаимодействие этих функций отображено на диаграмме вариантов

использования.

2. Проектирование.

2.1. Проектирование интерфейса пользователя.

Рис. 1. Главное окно приложения.

1.2.

1.3.

1.4.

1.5.

1.6.

1.7.

1.9.

1.8.

1.1.

Рис. 2. Диалоговое окно для генерации дерев.

Описание элементов интерфейса главного окна:

1.1. Имя текущего файла;

1.2. Деревья до и после операции;

1.3. Вызов диалогового окна для генерации дерева из указанного количества

элементов;

1.4. Добавление ключа в дерево;

1.5. Удаление ключа из дерева;

1.6. Поиск ключа в дереве;

1.7. Отображение дерева.

Описание элементов интерфейса диалогового окна для генерации дерева:

2.1. Количество элементов в новом дереве;

2.2. Отменить операцию;

2.3. Подтвердить выполнение операции.

Диалоговые окна для добавления, удаления и поиска ключа выглядят

аналогично окну «Сгенерировать дерево».

2.2. Проектирование структуры данных.

Поскольку деревья состоят из вершин, необходимо создать структуру,

описывающую эти вершины. При этом надо учесть, что они будут храниться в

2.1.

2.2. 2.3.

файле, т.е. использовать для этого класс, который содержит много «лишней»

информации не рационально.

Исходя из особенностей B-дерева, эта структура может быть представлена в

виде следующей записи:

BTreeNode = record

n: integer; //количество ключей, хранящихся в настоящий момент в узле х.

pos: integer; //позиция текущего узла в файле

key: array[1..2 * t - 1] of integer;

c: array[1..2 * t] of integer;

leaf: boolean; //TRUE, если х является листом, и false, если х — внутренний

узел.

end;

Для работы с этими вершинами необходимо реализовать класс «Дерево».

Именно этот класс должен содержать основные функции для работы с деревом во

внешней памяти.

TBTree = class(TObject)

private

RemMas: array of integer; //массив удаленных записей

RemMasChange: boolean; //изменен ли массив удаленных записей

procedure AddToRemMas(var r: integer); //добавление позиции (в файле) удаленной записи

function GetFreePos(DefaultPos: integer): integer;

function GetCount(): integer; //возврат количества страниц

function AllocateNode(): BTreeNode; //создание пустой страницы

procedure SplitChild(var x, y: BTreeNode; i: integer);

procedure InsertNonFull(var x: BTreeNode; k: integer);

function MaxInSubTree(var pos: integer): integer;

function MinInSubTree(var pos: integer): integer;

public

RootPos: integer; //позиция корневой страницы в файле

RemCount: integer; // размер RemMas в файле

FileName: string; //имя файла, в котором хранится дерево

constructor Create(BTreeFileName: string);

property Count: integer read GetCount;

function DiskRead(var pos: integer): BTreeNode;

procedure DiskWrite(var x: BTreeNode);

procedure Open(SrcFileName: string);

procedure SaveAs(DstFileName: string);

function Search(var pos, k: Integer): boolean;

procedure Insert(var k: integer); // встака влюча

function Remove(var x_num: integer; k: integer): boolean;

procedure UpdateFile();

end;

При проектировании класса «Дерево», учтено, что удаление страницы из

файла напрямую вызовет смещение всех индексов в файле, что приведет к

нарушению структуры дерева. Поэтому рационально сделать массив, содержащий

«свободные» позиции в файле. Как только понадобится создать новую страницу,

она запишется в одну из этих «свободных» позиций, иначе – в конец файла. Для

уменьшения обращений к диску этот массив можно считывать и записывать в

файл только один раз за сеанс работы, а поскольку количество страниц, которые

будут удалены, трудно предугадать, его необходимо сделать динамическим.

Таким образом, структура файла будет выглядеть следующим образом:

Позиция

корня

дерева

(RootPos)

Количество

свободных

позиций

(RemCount)

Свободная

позиция № 1

…

Свободная

позиция №

RemCount

Страница

№1

…

Страница

№ Count

3. Реализация.

3.1. Основные операции с деревом.

3.1.1. Операция вставки ключа.

Общие сведения об вставке ключа в B-дерево.

При работе с В-деревом мы не можем просто создать новый лист и вставить в

него ключ (как в бинарном дереве), поскольку такое дерево не будет являться

корректным В-деревом. Вместо этого мы вставляем новый ключ в существующий

лист. Поскольку вставить новый ключ в заполненный лист невозможно, мы

вводим новую операцию — разбиение заполненного (т.е. содержащего 2t — 1

ключей) узла на два, каждый из которых содержит по t-1 ключей. Медиана, или

средний ключ, — y.key[i] — при этом перемещается в родительский узел, где

становится разделительной точкой для двух вновь образовавшихся поддеревьев.

Однако если родительский узел тоже заполнен, перед вставкой нового ключа его

также следует разбить, и такой процесс разбиения может идти по восходящей до

самого корня. Как и в случае бинарного дерева поиска, в В-дереве мы вполне

можем осуществить вставку за один нисходящий проход от корня к листу. Для

этого нам не надо выяснять, требуется ли разбить узел, в который должен

вставляться новый ключ. Вместо этого при проходе от корня к листьям в поисках

позиции для нового ключа мы разбиваем все заполненные узлы, через которые

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

какой-то узел, то его родительский узел не будет заполнен.

Разбиение узла.

Рассмотрим функцию разбиения узла.

procedure TBTree.SplitChild(var x, y: BTreeNode; i: integer);

1 var z: BTreeNode;

2 j: integer;

3 begin

4 z := AllocateNode();

5 z.leaf := y.leaf;

6 z.n := t - 1;

7 z.pos := GetFreePos(Count + 1);

8 for j := 1 to t - 1 do

9 z.key[j] := y.key[j + t];

10 if not y.leaf then

11 for j := 1 to t do

12 z.c[j] := y.c[j + t];

13 y.n := t - 1;

14 for j := x.n + 1 downto i + 1 do

15 x.c[j + 1] := x.c[j];

16 x.c[i + 1] := z.pos;

17 for j := x.n downto i do

18 x.key[j + 1] := x.key[j];

19 x.key[i] := y.key[t];

20 x.n := x.n + 1;

21 DiskWrite(x);

22 DiskWrite(y);

23 DiskWrite(z);

24 end;

Процедура TBTree.SplitChild получает в качестве входного параметра

незаполненный внутренний узел х (находящийся в оперативной памяти), индекс i

и узел у (также находящийся в оперативной памяти), такой что у = с

[х] является

заполненным дочерним узлом х.

Рис. 3. Разбиение узла с t=4

В строках 4-7 инициализируется новый узел z. В строках 8-12 копируются

ключи и ссылки (если y не лист) второй половины узла y. В строках 14-15 и 17-18

смещаются все ключи и ссылки, начиная с индекса i, в узле x на одну позицию

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

медиана записывается в освободившееся место, а в 21-23 сохраняются все узлы.

Главная процедура вставки ключа.

procedure TBTree.Insert(var k: integer);

1 var s, r: BTreeNode;

2 begin

3 r := DiskRead(RootPos);

4 if r.n = 2 * t - 1 then

5 begin

6 s := AllocateNode();

7 s.leaf := false;

8 s.n := 0;

9 s.pos := GetFreePos(Count);

10 s.c[1] := r.pos; // -

11 RootPos := s.pos;

12 SplitChild(s, r, 1);

13 InsertNonFull(s, k);

14 end

15 else InsertNonFull(r, k);

16 end;

В строке 4 проверяется корневая страница на заполненность. Если она не

заполнена то вызывается функция вставки ключа, иначе корень разбивается, как

описано выше, и вызывается та же функция вставки. При этом гарантировано, что

корень не заполнен.

Процедура вставки ключа в дерево с незаполненным корнем.

procedure TBTree.InsertNonFull(var x: BTreeNode; k: integer);

1 var i: integer;