Реализация операции селекции с использованием индексов

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

по дисциплине "Базы данных"

тема: "Реализация операции селекции с использованием индексов"

Содержание

Введение

1. Постановка задачи

2. Понятие В-дерева

3. Создание В-дерева и вставка ключа

4. Реализация селекции

5. Примеры работы приложения

Заключение

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

Введение

Индекс - объект базы данных <#"522328.files/image001.gif">

Рисунок 1 - В-дерево порядка n=3

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

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

В-дерево обладает следующими свойствами:

. Все узлы X содержат поля:

б) Ключи, количество которых равно N.

в) Логическое значение IsLeaf, равное True, если X является листом, и FALSE, если X - внутренний узел.

. Все внутренние узлы X содержат (N + 1) указателей Child₁, Child₂, …, Child_N+1 на дочерние узлы. Листья не имеют дочерних узлов, так что их поля Child_i не определены.

. Ключи Key_i разделяют поддиапазоны ключей, хранящихся в поддеревьях: если k_i - произвольный ключ, хранящийся в поддереве с корнем Child_i, то k₁ ≤ Key₁ ≤ k₂ ≤ Key₂ ≤ … ≤ k_N ≤ Key_N ≤ k_N+1

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

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

а) Все узлы, кроме корневого, должен содержать как минимум (t-1) ключей. Каждый внутренний узел, не являющийся корневым, имеет, таким образом, как минимум t дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ.

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

Простейшее В-дерево получается при t = 2. При этом каждый внутренний узел может иметь 2, 3 или 4 дочерних узла, и мы получаем так называемое 2-3-4-дерево (2-3-4 tree). Однако обычно на практике используются гораздо большие значения t.

Таким образом, файл В-дерева, так же как и файл данных, представляет собой набор записей типа TBTreeNode.

Тип TKeyAdr предназначен для хранения ключа и адреса записи в основном файле.

3. Создание В-дерева и вставка ключа

Пустое дерево создается с помощью процедуры create_tree. Для внесения в дерево новых ключей предназначена процедура insert_tree.

Алгоритм вставки ключей в В-дерево представляет собой следующее:

Поиск листовой страницы. Фактически, производится обычный поиск по ключу. Если в B-дереве не содержится ключ с заданным значением, то будет получен номер страницы, в которой ему надлежит содержаться, и соответствующие координаты внутри страницы.

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

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

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

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

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

4. Реализация селекции

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

Блок-схема процедуры обработки события нажатия клавиши "Выбрать записи" представлена на рисунке 2.

индекс программа селекция операция

Рисунок 2 - Блок-схема обработки события нажатия клавиши "Выбрать записи"

Блок-схема процедуры селекции представлена на рисунке 3.

Рисунок 3 - Блок-схема алгоритма селекции

5. Примеры работы приложения

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

С помощью пункта меню "открыть" можно просматривать данные, хранящиеся в файле.

Пример работы приложения представлен на рисунке 4.

Рисунок 4 - Пример работы приложения

Пример выполненной селекции представлен на рисунке 5.

Рисунок 5 - Пример выполненной операции селекции

Заключение

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

)        Во всех случаях полезное использование пространства вторичной памяти занимает свыше 50%. С ростом степени полезного использования памяти не происходит снижения качества обслуживания.

2)      Произвольный доступ к записи реализуется посредством малого количества подопераций (обращения к физическим блокам).

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

)        Неизменная упорядоченность по ключу обеспечивает возможность эффективной пакетной обработки.

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

1.      Конноли Т., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. [Текст]: Пер. с. англ. - М.: Издательство Вильямс, 2003. - 296 с.

2.      Рыженков, Д.В. Курс лекций по дисциплине "Базы данных", 2009.

.        Швецов, В.И., Визгунов, А.Н., Мееров, И.Б. Базы данных [Текст]. - Учебное пособие. - Нижний Новгород: Издательство ННГУ, 2004. - 217 с.

Приложение А

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

{$O-}Unit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, Menus;= 'datafile. dat';= 'indexfile. dat';= 'rootfile. dat';= 0;= 2;= record: Integer;: string [100];;= record, Adr: Integer;;= record: Integer;: Boolean;: array [1.2*MD-1] of TKeyAdr;: array [1.2*MD] of Integer;;= class (TForm): TGroupBox;: TEdit;: TEdit;: TLabel;: TLabel;: TButton;: TMemo;: TLabel;: TLabel;: TGroupBox;: TButton;: TLabel;: TEdit;: TEdit;: TMainMenu;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TLabel;: TLabel;FormCreate (Sender: TObject);Button1Click (Sender: TObject);FormDestroy (Sender: TObject);Button6Click (Sender: TObject);N2Click (Sender: TObject);N6Click (Sender: TObject);N7Click (Sender: TObject);N8Click (Sender: TObject);N4Click (Sender: TObject);FormClose (Sender: TObject; var Action: TCloseAction);

{ Private declarations }

{ Public declarations };, CountWrite,ListSize: Integer;: TForm1;, IndexFile, RootFile: file;: Integer;: array [1.1000] of Integer;

{$R *. dfm}insert_data (var D: TData): Integer;(DataFile, DataFileName, SizeOf (TData));: = FileSize (DataFile);(DataFile, Result);(DataFile, D, 1);;declaration: Integer;Node: TBTreeNode;: = FileSize (IndexFile);(IndexFile, Result);(IndexFile, Node, 1);;create_tree;Node: TBTreeNode;. IsLeaf: = True;. N: = 0;(IndexFile, IndexFileName, SizeOf (TBTreeNode));(IndexFile, 0);(IndexFile, Node, 1);(RootFile, RootFileName, SizeOf (Integer));: = 0;(RootFile, 0);(RootFile, Root, 1);;read_tree (N: Integer);i: integer;: TBTreeNode;: TData;(IndexFile, N);(IndexFile, Node, 1);(Node. IsLeaf) then begini: =1 to Node. N do begin(DataFile, Node. Rec [i]. Adr);(DataFile, Data, 1);. Memo1. Lines. Add (IntToStr (Data. Key) +': '+Data. Data);;else begin_tree (Node. Child [1]);i: = 1 to Node. N do begin(DataFile, Node. Rec [i]. Adr);(DataFile, Data, 1);. Memo1. Lines. Add (IntToStr (Data. Key) +': '+Data. Data);_tree (Node. Child [i + 1]);;;;TForm1. FormCreate (Sender: TObject);: =0;: =0;(DataFile, DataFileName, SizeOf (TData));(IndexFile, IndexFileName, SizeOf (TBTreeNode));(RootFile, RootFileName, SizeOf (Integer));(RootFile, 0);(RootFile, Root, 1);;TForm1. FormClose (Sender: TObject; var Action: TCloseAction);;;TForm1. N2Click (Sender: TObject);(DataFile, DataFileName, SizeOf (TData));_tree;;TForm1. N4Click (Sender: TObject);. Terminate;;TForm1. N6Click (Sender: TObject);data: TData;: integer;. Clear;(DataFile,0);: =0;(i<FileSize (DataFile)) do begin: = i + 1;(DataFile,data,1);. Lines. Add (IntToStr (data. Key) +': '+data. Data);;;TForm1. N7Click (Sender: TObject);. Clear;_tree (Root);;TForm1. N8Click (Sender: TObject);node: TBTreeNode;,j: Integer;: string;. Clear;(IndexFile,0);: =0;(i<FileSize (IndexFile)) do begin: =i+1;(IndexFile, node, 1);. Lines. Add (' ['+IntToStr (i) +']: N ='+IntToStr (node. N) +''+IntToStr (Integer (node. IsLeaf)));: = '';j: =1 to node. N do: =s+' ('+IntToStr (node. Rec [j]. Key) +': '+IntToStr (node. Rec [j]. Adr) +') ';. Lines. Add (s);;;spliting (var X: TBTreeNode; XAdr, I: Integer; var Y: TBTreeNode);j: Integer;: TBTreeNode;, ZAdr: Integer;: = X. Child [I];: = declaration;. IsLeaf: = Y. IsLeaf;. N: = MD - 1;j: = 1 to MD - 1 do. Rec [j]: = Y. Rec [j + MD];(not Y. IsLeaf) thenj: = 1 to MD do. Child [j]: = Y. Child [j + MD];. N: = MD - 1;j: = X. N + 1 downto I + 1 do. Child [j + 1]: = X. Child [j];. Child [I + 1]: = ZAdr;j: = X. N downto I do. Rec [j + 1]: = X. Rec [j];. Rec [I]: = Y. Rec [MD];. N: = X. N + 1;(IndexFile, XAdr);(IndexFile, X, 1);(IndexFile, YAdr);(IndexFile, Y, 1);(IndexFile, ZAdr);(IndexFile, Z, 1);;insert_tree_no (var X: TBTreeNode; XAdr: Integer; KA: TKeyAdr);i: Integer;: TBTreeNode;: = X. N;(X. IsLeaf) then begin(i >= 1) and (KA. Key < X. Rec [i]. Key) do begin. Rec [i + 1]: = X. Rec [i];: = i - 1;;. Rec [i + 1]: = KA;. N: = X. N + 1;(IndexFile, XAdr);(IndexFile, X, 1);else begin(i >= 1) and (KA. Key < X. Rec [i]. Key) do: = i - 1;: = i + 1;(IndexFile, X. Child [i]);(IndexFile, Node, 1);(Node. N = 2 * MD - 1) then begin(X, XAdr, i, Node);(KA. Key > X. Rec [i]. Key) then begin: = i + 1;(IndexFile, X. Child [i]);(IndexFile, Node, 1);;;_tree_no (Node, X. Child [i], KA);;;insert_tree (KA: TKeyAdr);r, s: TBTreeNode;(IndexFile, Root);(IndexFile, r, 1);(r. N =2*MD-1) then begin. IsLeaf: =False;. N: = 0;. Child [1]: =Root;: = declaration;(s, Root, 1, r);_tree_no (s, Root, KA);else_tree_no (r, Root, KA);;read_data (Adr: integer);: =ListSize + 1;[ListSize]: =Adr;;selection (const Node: TBTreeNode; Left, Right: Integer);i: Integer;: TBTreeNode;: =1;(i <= Node. N) and (Node. Rec [i]. Key < Left) do: = i + 1;(not Node. IsLeaf) then begin(IndexFile, Node. Child [i]);(IndexFile, N, 1);(N,Left,Right);;(i<=Node. N) and (Node. Rec [i]. Key <= Right) do begin_data (Node. Rec [i]. Adr);: =i+1;(not Node. IsLeaf) then begin(IndexFile, Node. Child [i]);(IndexFile, N, 1);(N,Left,Right);;;;TForm1. FormDestroy (Sender: TObject);(RootFile, 0);(RootFile, Root, 1);;TForm1. Button1Click (Sender: TObject);D: TData;: TKeyAdr;. Key: =StrToInt (Edit1. Text);. Data: =Edit2. Text;. Key: =D. Key;. Adr: =insert_data (D);_tree (KA);;TForm1. Button6Click (Sender: TObject);i, Left, Right: Integer;: TBTreeNode;: TData;: string;. Clear;: = 0;: = StrToInt (Edit3. Text);: = StrToInt (Edit4. Text);(IndexFile, Root);(IndexFile, Node, 1);(Node, Left, Right);i: = 1 to ListSize do begin(DataFile, ListData [i]);(DataFile, Data, 1);: = IntToStr (i) +': '+IntToStr (Data. Key) + ' ';. Lines. Add (s+Data. Data);

end;;.