Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l дерево
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Курсовая работа
по диiиплине
Базы данных
тема:
Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l дерево
Содержание
Введение
. Представление файлов в виде В-дерева
. Программная реализация
.1 Типы данных
.2 Добавление элемента в В-дерево
.3 Поиск элемента
.3 Удаление элемента
. Пример работы программы
Заключение
Список литературы
Приложение А Листинг программы
Введение
В наше время люди повсюду работают с данными. Естественно, возникает необходимость управления этими данными: запись, хранение, обработка и удаление являются инструментами в наших руках. А в условиях нашей жизни при рыночной экономике мы тем более задумываемся над надежностью, целесообразностью и скоростью работы выбранных методов. Все данные, в большинстве случаев, располагаются в базах данных. Здесь вопрос заключается лишь в том, как будет организована эта самая база данных.
Перед реализацией какой-либо операции над записями базы данных необходимо учитывать, что нам все-таки будет нужно, ведь от этого и надо отталкиваться. Но базы данных создаются для того, чтобы впоследствии эти данные можно было найти и использовать. Поэтому основной задачей ставиться эффективная реализация поиска записей в базе данных, который также потребуется и при вставке, и при удалении записей.
В этом плане очень удобно использовать так называемые В-деревья, так как эти деревья сбалансированы и упорядочены, следовательно и доступ к необходимому узлу получается довольно быстро.
Целью данной курсовой работы является организация файла в виде В-дерева, с возможностями вставки, поиска и удаления записи. Для достижения этой цели были поставлены следующие задачи:
написание процедуры, реализующей добавление записи в базу данных;
написание процедуры, производящей разбиение блоков записей;
написание процедуры поиска и удаления элементов по ключу;
написание процедуры, производящей балансировку и слияние записей в блоке;
создание приложения, способного производить вышеперечисленные действия.
1. Представление файлов в виде В-дерева
<ическое упорядочение самих записей основного файла: необходимость реорганизации файла при операциях вставки, удаления, модификации. Следовательно, для организации индекса должен использоваться некоторый вариант кучи. Однако при этом недостаточно иметь простую структуру типа двунаправленного списка, поскольку придется при каждой модификации индекса выполнять сортировку. При этом также следует иметь ввиду, что количество записей в индексе может быть очень велико (размеры файла могут во много раз превышать доступную оперативную память), таким образом, применение обычных методов сортировки, которые ориентируются на размещение всех сортируемых элементов, может быть невозможно.В оперативной памяти упорядоченные структуры, допускающие эффективную вставку, удаление и модификацию данных обычно организуются в виде сбалансированных деревьев (AVL-деревьев). Сбалансированные деревья - это двоичные деревья, для которых постоянно поддерживается равномерное распределение вершин между поддеревьями. При этом достР располагаются не в оперативной памяти, а на внешних устройствах, то каждое обращение к вершине (при поиске или в ходе балансировки) требует отдельной операции чтения или записи. Таким образом, если дерево содержит, например 1000000 вершин, то в среднем может потребоваться около 20 операций обращения к внешней памяти. Количество таких обращений будет больше, если происходит балансировка.
Естественным подходом к преодолению данной проблемы является группировка нескольких вершин дерева в один блок ввода-вывода. При этом в древовидную структуру организуются блоки, а не отдельные вершины. Несмотря на то, что возникает необходимость производить поиск внутри блока, количество обращений к устройству внешней памяти сокращается.
Весьма распространенный в настоящее время подход к организации упорядоченных индексов был предложен в 1970г. Р. Бэйером и Э. Мак-Kрейтом. Предложенные ими структуры получили название В-деревьев. В-дерево представляет собой сильно ветвящееся дерево, обладающее следующими свойствами:
Каждая вершина может содержать не более 2n ключей.
Каждая вершина за исключением, может быть, корневой содержит не менее n ключей (корневая вершина, если она не является листом, содержит не менее двух потомков).
Каждая вершина либо представляет собой лист и не имеет потомков, либо имеет в точности m+1 потомка, где m - количество ключей в вершине.
Все листовые вершины располагаются на одном уровне.
В-дерево может быть построено следующим образом. Последовательность записей, соответствующая записям исходной таблицы, упорядочивается по значениям первичного ключа. Логические записи объединяются в блоки. Значением ключа блока является м