Реализация операции селекции с использованием индексов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Курсовая работа
по диiиплине "Базы данных"
тема: "Реализация операции селекции с использованием индексов"
Содержание
Введение
1. Постановка задачи
2. Понятие В-дерева
3. Создание В-дерева и вставка ключа
4. Реализация селекции
5. Примеры работы приложения
Заключение
Список литературы
Введение
Индекс - объект базы данных , создаваемый iелью повышения производительности выполнения запросов. Таблицы в базе данных могут иметь большое количество строк, которые хранятся в произвольном порядке, и их поиск по заданному значению путем последовательного просмотра таблицы строка за строкой может занимать много времени. Индекс формируется из значений одного или нескольких столбцов таблицы и указателей на соответствующие строки таблицы и, таким образом, позволяет находить нужную строку по заданному значению. Ускорение работы с использованием индексов достигается в первую очередь за счёт того, что индекс имеет структуру, оптимизированную под поиск.
В данной курсовой работе индексы реализованы структурой В-дерева.
B-деревья - это сбалансированное сильно ветвистое дерево во внешней памяти, обеспечивающих эффективное хранение информации на магнитных дисках и других устройствах с прямым доступом. Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же. Ветвистость дерева - это свойство каждого узла дерева ссылаться на большое число узлов-потомков.
Выбранная для курсовой работы структура данных используются при построении индексов отношений, которые в свою очередь применяются в различных операциях языка запросов, в частности - операции селекции.
Целью данной работы является создание программы, реализующей операцию селекции с помощью индексов. Индекс должен представлять собой В-дерево. Актуальность данной работы заключается в том, что В-деревья значительно ускоряют время выполнения запросов и широко используются в современных СУБД. Задача курсовой работы - создание приложения, позволяющего добавлять записи в отношение, а также осуществлять селекцию по заданному условию.
1. Постановка задачи
Необходимо разработать приложение, позволяющую реализовывать операцию селекции с использованием индекса, представляющего собой В-дерево.
2. Понятие В-дерева
Наиболее популярным подходом к организации индексов в базах данных является использование техники 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 предназначен для хранения ключа и адреса записи в основном файле.
3. Создание В-дерева и вставка ключа
Пустое дерево создается с помощью процедуры create_tree. Для внесения в дерево новых ключей предназначена процедура insert_tree.
Алгоритм вставки ключей в В-дерево представляет собой следующее:
Поиск листовой страницы. Фактически, производится обычный поиск по ключу. Если в B-дереве не содержится ключ с заданны