Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Курсовая работа
по дисциплине "Базы данных"
тема: "Реализация операции селекции с использованием индексов"
Содержание
Введение
1. Постановка задачи
2. Понятие В-дерева
3. Создание В-дерева и вставка ключа
4. Реализация селекции
5. Примеры работы приложения
Заключение
Список литературы
Введение
Индекс - объект базы данных <http://ru.wikipedia.org/wiki/%D0%91%D0%B0%D0%B7%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85>, создаваемый с целью повышения производительности выполнения запросов. Таблицы в базе данных могут иметь большое количество строк, которые хранятся в произвольном порядке, и их поиск по заданному значению путем последовательного просмотра таблицы строка за строкой может занимать много времени. Индекс формируется из значений одного или нескольких столбцов таблицы и указателей на соответствующие строки таблицы и, таким образом, позволяет находить нужную строку по заданному значению. Ускорение работы с использованием индексов достигается в первую очередь за счёт того, что индекс имеет структуру, оптимизированную под поиск.
В данной курсовой работе индексы реализованы структурой В-дерева.
B-деревья - это сбалансированное сильно ветвистое дерево <http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%28%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2%29> во внешней памяти, обеспечивающих эффективное хранение информации на магнитных дисках и других устройствах с прямым доступом. Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же. Ветвистость дерева - это свойство каждого узла дерева ссылаться на большое число узлов-потомков.
Выбранная для курсовой работы структура данных используются при построении индексов отношений, которые в свою очередь применяются в различных операциях языка запросов, в частности - операции селекции.
Целью данной работы является создание программы, реализующей операцию селекции с помощью индексов. Индекс должен представлять собой В-дерево. Актуальность данной работы заключается в том, что В-деревья значительно ускоряют время выполнения запросов и широко используются в современных СУБД. Задача курсовой работы - создание приложения, позволяющего добавлять записи в отношение, а также осуществлять селекцию по заданному условию.
Необходимо разработать приложение, позволяющую реализовывать операцию селекции с использованием индекса, представляющего собой В-дерево.
Наиболее популярным подходом к организации индексов в базах данных является использование техники B-деревьев. С точки зрения внешнего логического представления B-дерево - это сбалансированное сильно ветвистое дерево во внешней памяти.
На рисунке 1 показан пример простого В-дерева порядка n=3.
Рисунок 1 - В-дерево порядка n=3
В разработанной программе индекс строится для файла, представляющего собой набор записей типа TData.
Для удобства В-дерево строится в отдельном файле и содержит в своих узлах значения ключей, а также адреса записей в основном файле, что обеспечивает возможность доступа к данным записи.
В-дерево обладает следующими свойствами:
. Все узлы X содержат поля:
а) N, количество ключей, хранящихся в настоящий момент в узле X.
б) Ключи, количество которых равно N.
в) Логическое значение IsLeaf, равное True, если X является листом, и FALSE, если X - внутренний узел.
. Все внутренние узлы X содержат (N + 1) указателей Child1, Child2, …, ChildN+1 на дочерние узлы. Листья не имеют дочерних узлов, так что их поля Childi не определены.
. Ключи Keyi разделяют поддиапазоны ключей, хранящихся в поддеревьях: если ki - произвольный ключ, хранящийся в поддереве с корнем Childi, то k1 ≤ Key1 ≤ k2 ≤ Key2 ≤ … ≤ kN ≤ KeyN ≤ kN+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 предназначен для хранения ключа и адреса записи в основном файле.
Пустое дерево создается с помощью процедуры create_tree. Для внесения в дерево новых ключей предназначена процедура insert_tree.
Алгоритм вставки ключей в В-дерево представляет собой следующее:
Поиск листовой страницы. Фактически, производится обычный поиск по ключу. Если в B-дереве не содержится ключ с заданным значением, то будет получен номер страницы, в которой ему надлежит содержаться, и соответствующие координаты внутри страницы.
Помещение записи на место. Естественно, что вся работа производится в буферах оперативной памяти. Листовая страница, в которую требуется занести запись, считывается в буфер, и в нем выполняется операция вставки. Размер буфера должен превышать размер страницы внешней памяти.
Если после выполнения вставки новой записи размер используемой части буфера не превосходит размера страницы, то на этом выполнение операции занесения записи заканчивается. Буфер может быть немедленно вытолкнут во внешнюю память, или временно сохранен в оперативной памяти в зависимости от политики управления буферами.
Если же возникло переполнение буфера (т.е. размер его используемой части превосходит размер страницы), то выполняется расщепление страницы. Для этого запрашивается новая страница внешней памяти, используемая часть буфера разбивается грубо говоря пополам (так, чтобы вторая половина также начиналась с ключа), и вторая половина записывается во вновь выделенную страницу, а в старой странице модифицируется значение размера свободной памяти. Естественно, модифицируются ссылки по списку листовых страниц.
Чтобы обеспечить доступ от корня дерева к заново заведенной страницы, необходимо соответствующим образом модифицировать внутреннюю страницу, являющуюся предком ранее существовавшей листовой страницы, т.е. вставить в нее соответствующее значение ключа и ссылку на новую страницу. При выполнении этого действия может снова произойти переполнение теперь уже внутренней страницы, и она будет расщеплена на две. В результате потребуется вставить значение ключа и ссылку на новую страницу во внутреннюю страницу-предка выше по иерархии и т.д.
Предельным случаем является переполнение корневой страницы B-дерева. В этом случае она тоже расщепляется на две, и заводится новая корневая страница дерева, т.е. его глубина увеличивается на единицу.
Для выполнения операции селекции необходимо задать интервал выборки, в диапазоне которого будут выбраны необходимые записи.
Далее, по нажатию кнопки "Выбрать записи" происходит выбор необходимых значений, хранение которых было реализовано с использованием структуры B-дерева.
Блок-схема процедуры обработки события нажатия клавиши "Выбрать записи" представлена на рисунке 2.
индекс программа селекция операция
Рисунок 2 - Блок-схема обработки события нажатия клавиши "Выбрать записи"
Блок-схема процедуры селекции представлена на рисунке 3.
Рисунок 3 - Блок-схема алгоритма селекции
При запуске приложения, пользователь может добавлять запись, задавать размер выборки данных. Если требуется найти записи с каким-либо конкретным значением ключа, то достаточно задать одинаковые значения правой и левой границ отбора.
С помощью пункта меню "открыть" можно просматривать данные, хранящиеся в файле.
Пример работы приложения представлен на рисунке 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;;.