Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Реализация операции селекции с использованием индексов

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

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 12.08.2011
Размер файла 371,1 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

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

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

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

Содержание

  • Введение
  • 1. Постановка задачи
  • 2. Понятие В-дерева
  • 3. Создание В-дерева и вставка ключа
  • 4. Реализация селекции
  • 5. Примеры работы приложения
  • Заключение
  • Список литературы

Введение

Индекс - объект базы данных, создаваемый с целью повышения производительности выполнения запросов. Таблицы в базе данных могут иметь большое количество строк, которые хранятся в произвольном порядке, и их поиск по заданному значению путем последовательного просмотра таблицы строка за строкой может занимать много времени. Индекс формируется из значений одного или нескольких столбцов таблицы и указателей на соответствующие строки таблицы и, таким образом, позволяет находить нужную строку по заданному значению. Ускорение работы с использованием индексов достигается в первую очередь за счёт того, что индекс имеет структуру, оптимизированную под поиск.

В данной курсовой работе индексы реализованы структурой В-дерева.

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

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

Целью данной работы является создание программы, реализующей операцию селекции с помощью индексов. Индекс должен представлять собой В-дерево. Актуальность данной работы заключается в том, что В-деревья значительно ускоряют время выполнения запросов и широко используются в современных СУБД. Задача курсовой работы - создание приложения, позволяющего добавлять записи в отношение, а также осуществлять селекцию по заданному условию.

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

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

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

Наиболее популярным подходом к организации индексов в базах данных является использование техники B-деревьев. С точки зрения внешнего логического представления B-дерево - это сбалансированное сильно ветвистое дерево во внешней памяти.

На рисунке 1 показан пример простого В-дерева порядка n=3.

Размещено на http://www.allbest.ru/

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

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

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

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

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

а) N, количество ключей, хранящихся в настоящий момент в узле X.

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

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

2. Все внутренние узлы X содержат (N + 1) указателей Child1, Child2, …, ChildN+1 на дочерние узлы. Листья не имеют дочерних узлов, так что их поля Childi не определены.

3. Ключи Keyi разделяют поддиапазоны ключей, хранящихся в поддеревьях: если ki - произвольный ключ, хранящийся в поддереве с корнем Childi, то k1 ? Key1 ? k2 ? Key2 ? … ? kN ? KeyN ? kN+1

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

5. Существует нижняя и верхняя границы количества ключей, которые могут содержаться в узле. Эти границы могут быть выражены с помощью одного фиксированного целого числа 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. Реализация селекции

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

Приложение А

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

{$O-}

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Menus;

const

DataFileName = 'datafile. dat';

IndexFileName = 'indexfile. dat';

RootFileName = 'rootfile. dat';

NULL = 0;

MD = 2;

type

TData = record

Key: Integer;

Data: string [100];

end;

TKeyAdr = record

Key, Adr: Integer;

end;

TBTreeNode = record

N: Integer;

IsLeaf: Boolean;

Rec: array [1.2*MD-1] of TKeyAdr;

Child: array [1.2*MD] of Integer;

end;

TForm1 = class (TForm)

GroupBox1: TGroupBox;

Edit1: TEdit;

Edit2: TEdit;

Label1: TLabel;

Label2: TLabel;

Button1: TButton;

Memo1: TMemo;

Label3: TLabel;

Label4: TLabel;

GroupBox2: TGroupBox;

Button6: TButton;

Label5: TLabel;

Edit3: TEdit;

Edit4: TEdit;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N6: TMenuItem;

N7: TMenuItem;

N8: TMenuItem;

Label6: TLabel;

Label7: TLabel;

procedure FormCreate (Sender: TObject);

procedure Button1Click (Sender: TObject);

procedure FormDestroy (Sender: TObject);

procedure Button6Click (Sender: TObject);

procedure N2Click (Sender: TObject);

procedure N6Click (Sender: TObject);

procedure N7Click (Sender: TObject);

procedure N8Click (Sender: TObject);

procedure N4Click (Sender: TObject);

procedure FormClose (Sender: TObject; var Action: TCloseAction);

private

{ Private declarations }

public

{ Public declarations }

end;

var

CountRead, CountWrite,ListSize: Integer;

Form1: TForm1;

DataFile, IndexFile, RootFile: file;

Root: Integer;

ListData: array [1.1000] of Integer;

implementation

{$R *. dfm}

function insert_data (var D: TData): Integer;

begin

ReSet (DataFile, DataFileName, SizeOf (TData));

Result: = FileSize (DataFile);

Seek (DataFile, Result);

BlockWrite (DataFile, D, 1);

end;

function declaration: Integer;

var Node: TBTreeNode;

begin

Result: = FileSize (IndexFile);

Seek (IndexFile, Result);

BlockWrite (IndexFile, Node, 1);

end;

procedure create_tree;

var Node: TBTreeNode;

begin

Node. IsLeaf: = True;

Node. N: = 0;

ReWrite (IndexFile, IndexFileName, SizeOf (TBTreeNode));

Seek (IndexFile, 0);

BlockWrite (IndexFile, Node, 1);

ReWrite (RootFile, RootFileName, SizeOf (Integer));

Root: = 0;

Seek (RootFile, 0);

BlockWrite (RootFile, Root, 1);

end;

procedure read_tree (N: Integer);

var i: integer;

Node: TBTreeNode;

Data: TData;

begin

Seek (IndexFile, N);

BlockRead (IndexFile, Node, 1);

if (Node. IsLeaf) then begin

for i: =1 to Node. N do begin

Seek (DataFile, Node. Rec [i]. Adr);

BlockRead (DataFile, Data, 1);

Form1. Memo1. Lines. Add (IntToStr (Data. Key) +': '+Data. Data);

end;

end else begin

read_tree (Node. Child [1]);

for i: = 1 to Node. N do begin

Seek (DataFile, Node. Rec [i]. Adr);

BlockRead (DataFile, Data, 1);

Form1. Memo1. Lines. Add (IntToStr (Data. Key) +': '+Data. Data);

read_tree (Node. Child [i + 1]);

end;

end;

end;

procedure TForm1. FormCreate (Sender: TObject);

begin

CountRead: =0;

CountWrite: =0;

ReSet (DataFile, DataFileName, SizeOf (TData));

ReSet (IndexFile, IndexFileName, SizeOf (TBTreeNode));

ReSet (RootFile, RootFileName, SizeOf (Integer));

Seek (RootFile, 0);

BlockRead (RootFile, Root, 1);

end;

procedure TForm1. FormClose (Sender: TObject; var Action: TCloseAction);

begin

Release;

end;

procedure TForm1. N2Click (Sender: TObject);

begin

ReWrite (DataFile, DataFileName, SizeOf (TData));

create_tree;

end;

procedure TForm1. N4Click (Sender: TObject);

begin

Application. Terminate;

end;

procedure TForm1. N6Click (Sender: TObject);

var data: TData;

i: integer;

begin

Memo1. Clear;

Seek (DataFile,0);

i: =0;

while (i<FileSize (DataFile)) do begin

i: = i + 1;

BlockRead (DataFile,data,1);

Memo1. Lines. Add (IntToStr (data. Key) +': '+data. Data);

end;

end;

procedure TForm1. N7Click (Sender: TObject);

begin

Memo1. Clear;

read_tree (Root);

end;

procedure TForm1. N8Click (Sender: TObject);

var node: TBTreeNode;

i,j: Integer;

s: string;

begin

Memo1. Clear;

Seek (IndexFile,0);

i: =0;

while (i<FileSize (IndexFile)) do begin

i: =i+1;

BlockRead (IndexFile, node, 1);

Memo1. Lines. Add (' ['+IntToStr (i) +']: N ='+IntToStr (node. N) +''+IntToStr (Integer (node. IsLeaf)));

s: = '';

for j: =1 to node. N do

s: =s+' ('+IntToStr (node. Rec [j]. Key) +': '+IntToStr (node. Rec [j]. Adr) +') ';

Memo1. Lines. Add (s);

end;

end;

procedure spliting (var X: TBTreeNode; XAdr, I: Integer; var Y: TBTreeNode);

var j: Integer;

Z: TBTreeNode;

YAdr, ZAdr: Integer;

begin

YAdr: = X. Child [I];

ZAdr: = declaration;

Z. IsLeaf: = Y. IsLeaf;

Z. N: = MD - 1;

for j: = 1 to MD - 1 do

Z. Rec [j]: = Y. Rec [j + MD];

if (not Y. IsLeaf) then

for j: = 1 to MD do

Z. Child [j]: = Y. Child [j + MD];

Y. N: = MD - 1;

for j: = X. N + 1 downto I + 1 do

X. Child [j + 1]: = X. Child [j];

X. Child [I + 1]: = ZAdr;

for j: = X. N downto I do

X. Rec [j + 1]: = X. Rec [j];

X. Rec [I]: = Y. Rec [MD];

X. N: = X. N + 1;

Seek (IndexFile, XAdr);

BlockWrite (IndexFile, X, 1);

Seek (IndexFile, YAdr);

BlockWrite (IndexFile, Y, 1);

Seek (IndexFile, ZAdr);

BlockWrite (IndexFile, Z, 1);

end;

procedure insert_tree_no (var X: TBTreeNode; XAdr: Integer; KA: TKeyAdr);

var i: Integer;

Node: TBTreeNode;

begin

i: = X. N;

if (X. IsLeaf) then begin

while (i >= 1) and (KA. Key < X. Rec [i]. Key) do begin

X. Rec [i + 1]: = X. Rec [i];

i: = i - 1;

end;

X. Rec [i + 1]: = KA;

X. N: = X. N + 1;

Seek (IndexFile, XAdr);

BlockWrite (IndexFile, X, 1);

end else begin

while (i >= 1) and (KA. Key < X. Rec [i]. Key) do

i: = i - 1;

i: = i + 1;

Seek (IndexFile, X. Child [i]);

BlockRead (IndexFile, Node, 1);

if (Node. N = 2 * MD - 1) then begin

spliting (X, XAdr, i, Node);

if (KA. Key > X. Rec [i]. Key) then begin

i: = i + 1;

Seek (IndexFile, X. Child [i]);

BlockRead (IndexFile, Node, 1);

end;

end;

insert_tree_no (Node, X. Child [i], KA);

end;

end;

procedure insert_tree (KA: TKeyAdr);

var r, s: TBTreeNode;

begin

Seek (IndexFile, Root);

BlockRead (IndexFile, r, 1);

if (r. N =2*MD-1) then begin

s. IsLeaf: =False;

s. N: = 0;

s. Child [1]: =Root;

Root: = declaration;

spliting (s, Root, 1, r);

insert_tree_no (s, Root, KA);

end else

insert_tree_no (r, Root, KA);

end;

procedure read_data (Adr: integer);

begin

ListSize: =ListSize + 1;

ListData [ListSize]: =Adr;

end;

procedure selection (const Node: TBTreeNode; Left, Right: Integer);

var i: Integer;

N: TBTreeNode;

begin

i: =1;

while (i <= Node. N) and (Node. Rec [i]. Key < Left) do

i: = i + 1;

if (not Node. IsLeaf) then begin

Seek (IndexFile, Node. Child [i]);

BlockRead (IndexFile, N, 1);

selection (N,Left,Right);

end;

while (i<=Node. N) and (Node. Rec [i]. Key <= Right) do begin

read_data (Node. Rec [i]. Adr);

i: =i+1;

if (not Node. IsLeaf) then begin

Seek (IndexFile, Node. Child [i]);

BlockRead (IndexFile, N, 1);

selection (N,Left,Right);

end;

end;

end;

procedure TForm1. FormDestroy (Sender: TObject);

begin

Seek (RootFile, 0);

BlockWrite (RootFile, Root, 1);

end;

procedure TForm1. Button1Click (Sender: TObject);

var D: TData;

KA: TKeyAdr;

begin

D. Key: =StrToInt (Edit1. Text);

D. Data: =Edit2. Text;

KA. Key: =D. Key;

KA. Adr: =insert_data (D);

insert_tree (KA);

end;

procedure TForm1. Button6Click (Sender: TObject);

var i, Left, Right: Integer;

Node: TBTreeNode;

Data: TData;

s: string;

begin

Memo1. Clear;

ListSize: = 0;

Left: = StrToInt (Edit3. Text);

Right: = StrToInt (Edit4. Text);

Seek (IndexFile, Root);

BlockRead (IndexFile, Node, 1);

selection (Node, Left, Right);

for i: = 1 to ListSize do begin

Seek (DataFile, ListData [i]);

BlockRead (DataFile, Data, 1);

s: = IntToStr (i) +': '+IntToStr (Data. Key) + ' ';

Memo1. Lines. Add (s+Data. Data);

end;

end;

end.

Размещено на Allbest.ru


Подобные документы

  • Создание и реализация стека

    Создание стека с помощью языка программирования C#. Блок-схема работы алгоритма программы, ее интерфейс. Добавление, удаление и вывод элементов в стеке. Реализация методов "Начало-конец" (переприсвоение индексов) и "Приоритет" (сортировка по возрастанию).

    лабораторная работа [924,7 K], добавлен 26.12.2014

  • Графическая и программная реализация алгоритмов обработки сложных структур данных

    Разработка блок-схемы и программы обработки одномерного массива с доступом к элементам с помощью индексов и с помощью указателей. Словесное описание алгоритма и пользовательского интерфейса, листинг программы обработки матрицы и результат её выполнения.

    курсовая работа [391,1 K], добавлен 30.09.2013

  • Базы данных

    Понятие базы данных, ее архитектура. Классификация баз данных. Основные модели данных. Примеры структурированных и неструктурированных данных. Достоинства и недостатки архитектуры файл-сервер. Иерархическая модель данных. Виды индексов, нормализация.

    презентация [1,4 M], добавлен 06.08.2014

  • Оптимизация запросов в SQL

    Определение архитектуры реляционных СУБД. Рассмотрение кластеризации как основного способа минимизации числа дисковых операций ввода-вывода данных. Применение индексов для повышения производительности SQL-запросов. Процесс кэширования в базах данных.

    курсовая работа [61,1 K], добавлен 15.07.2012

  • Создание и индексирование однотабличной базы данных

    Создание однотабличных баз данных и ключей, индексирование однотабличной БД с помощью конструктора таблиц Table Designer в SQL Server Management Studio. Понятие и назначение индексов кластерного и некластерного типов, инструкция по их созданию в БД.

    лабораторная работа [684,9 K], добавлен 01.12.2011

  • Визуальный построитель запросов на извлечение

    Создание визуального построителя запросов на извлечение данных с помощью оператора SELECT и его разделов. Постановка задачи; язык запросов SQL, общие сведения; агрегатные функции и результаты запросов. Программная реализация и алгоритм работы приложения.

    курсовая работа [152,8 K], добавлен 12.08.2011

  • Создание базы данных учета деятельности промоутеров в компании "Чистая вода"

    Методы проектирования базы данных по заданной предметной области с использованием CASE-средств ER/Studio и СУБД MS Access. Формирование и связывание таблиц, ввод данных. Создание экранных форм, запросов, отчетов, меню приложения. Генерация приложения.

    курсовая работа [884,0 K], добавлен 08.09.2010

  • Приложение для маскировки нежелательных звуковых эффектов

    Выбор и реализация модели базы данных. Концептуальная модель базы данных. Описание логической модели базы данных, SQL-запросов, приложения маскировки эффектов, контрольного примера, программных средств работы. Инструкция по эксплуатации программы.

    курсовая работа [693,4 K], добавлен 19.05.2014

  • Создание защищенного приложения для ведения учета продаж и закупок, ориентированного на малый бизнес

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

    дипломная работа [2,5 M], добавлен 05.02.2017

  • Автоматизация деятельности института селекции растений

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

    контрольная работа [1,7 M], добавлен 16.12.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены