Программная реализация B+-дерева
Министерство образования и науки РФ
Государственное образовательное учреждение высшего профессионального образования
«Юго-западный государственный университет»
Кафедра ПО ВТ
КУРСОВАЯ РАБОТА
по дисциплине «Структуры и алгоритмы обработки данных»
на тему «Программная реализация B+-дерева»
Специальность (направление
подготовки) ПО ВТ
______________________________
Автор работы (проекта) Клыков А.В. ___________________
Группа ПО-92
Руководитель работы (проекта) Белова Т.М. __________________
Работа (проект) защищена ____________________
Оценка ____________________
Председатель комиссии ____________________ ___________________
Члены комиссии: ____________________ ___________________
____________________ ___________________
Курск, 2011 г.
Министерство образования и науки РФ
Государственное образовательное учреждение высшего профессионального образования
«Юго-западный государственный университет»
Кафедра ПО ВТ
ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ
Студент Клыков А.В. шифр 349014 группа ПО-92
1.Тема Программная реализация B+-дерева
2. Срок предоставления работы (проекта) к защите « » 2011 г.
3. Исходные данные (для проектирования, для научного исследования):
Данные, введенные пользователем; файл данных.
4. Содержание пояснительной записки курсовой работы (проекта):
4.1. Содержание
4.3. Техническое задание
4.4. Технический проект
4.5. Рабочий проект
4.6. Список использованных источников
4.7. Приложение
5. Перечень графического материала:
______________________________
______________________________
Руководитель работы (проекта) Белова Т.М.
Задание принял
к исполнению
Содержание
- ТЕХНИЧЕСКОЕ ЗАДАНИЕ
- Введение
Программное обеспечение – это один из самых важных компонентов успешного функционирования всей компьютерной деятельности. В настоящее время существует огромное число прикладных программ, написанных на самых разных языках программирования, как на низкоуровневых, так и на современных, более удобных – высокоуровневых.
Для программного продукта данной курсовой работы операционной средой является система Microsoft Windows XP. Для создания использовалась среда программирования Microsoft Visual Studio 9 и язык программирования C++.
Язык C++ является одним из наиболее мощных современных языков программирования. Он поддерживает большинство перспективных технологий разработки программ, включая структурное программирование, модульное построение программ, объектную декомпозицию. С его использованием разработаны такие программные комплексы, как, например, операционные системы семейства Windows.
Целью создания программного продукта данной курсовой работы является изучение структуры данных B+ - дерево.
В данной курсовой работе реализуется программный комплекс "Информационно-поисковая система банка на основе B+-дерева".
- Основания для разработки
Данный программный продукт разрабатывается как задание на курсовую работу по дисциплине "Структуры и алгоритмы обработки данных".
- Назначение разработки
- Функциональное и эксплуатационное назначение изделия
В соответствии с заданием данное программное изделие должно представлять собой приложение, позволяющее просматривать, искать, удалять и добавлять информацию о банковских клиентах и их вкладах, использующее структуру данных «B+ - дерево».
- Перечень требований пользователя к программному продукту
Данный программный продукт должен представлять собой простой графический интерфейс, состоящий из одного окна, на котором располагаются поля ввода данных, функциональные кнопки («добавить», «найти», «удалить») и компонент, внутри которого отображается структура дерева.
- Рассмотренные альтернативы
При постановке задачи на разработку данного программного изделия в качестве альтернативы рассматривались структуры данных «B – дерево» и «B* - дерево». Была выбрана структура «B+ - дерево» как наиболее экономичная по времени исполнения.
- Требования к программе или про
граммному изделию
- Стандарты
Разработка программной
- Требования к составу и парамет
рам технических средств
Программное изделие должно работать на компьютере под управлением операционной системы Windows XP с частотой процессора не ниже 2 ГГц, ОЗУ не менее 1024Мбайт. Для переноса программы не должны требоваться специальные программные и аппаратные средства.
- Требования к информационной и программной совместимости
Программное изделие должно быть написано на языке C++ и работать под управлением операционной системы Windows XP.
- Требования к функциональным характеристикам
Программное изделие должно выдавать корректную информацию на запросы пользователя, в том числе в случае ввода пользователем неподходящих данных выводить сообщение об ошибке.
- Результирующие компоненты изделия
В комплект поставки программного изделия входит исполняемый файл «B+ Tree.exe», а также файл данных «schedule.txt», содержащий информацию о клиентах банка.
- Носители информации
Программное изделие будет размещено в виде файлов на компакт-диске.
- Безопасность и секретность
Информация, содержащаяся в программном изделии, не является секретной. Программный продукт может свободно копироваться и распространяться и не требует специальных средств защиты от копирования или хранения информации.
- Удобства эксплуатации
Графический интерфейс программы должен быть выполнен таким образом, чтобы обеспечивать простоту и удобство эксплуатации программы.
- Мобильность
Программный продукт не требует наличия дополнительных средств для переноса. Процесс переноса состоит в копировании исполняемых файлов на электронный носитель информации, переносе их на другой компьютер и копирования с носителя в отдельную папку на постоянном внешнем запоминающем устройстве ЭВМ.
- Требования к программной докум
ентации
Программная документация должна включать следующие документы:
- техническое задание;
- технический проект;
- рабочий проект,
- тесты.
В приложении к документу "Рабочий проект" должен быть приведен листинг исходных текстов программного изделия.
- Стадии и этапы разработки
Выполнение разработки должно включать три стадии:
- техническое задание;
- технический проект;
- рабочий проект.
На стадии "Техническое задание" проводится постановка задачи, разработка требований к программному изделию, изучение литературы по задаче и оформление документа "Техническое задание".
На стадии "Технический проект" проводится анализ данной предметной области, выделение основных взаимодействий между пользователем, выяснение структуры программного комплекса. В заключение данного этапа оформляется документ "Технический проект".
На стадии "Рабочий проект" проводится разработка схем алгоритмов для каждого из функциональных модулей, физическое проектирование программного изделия, разработка тестов, тестирование и отладка программных модулей. В заключение данного этапа оформляется документ "Рабочий проект".
- Порядок контроля и приемки
Приемка программного изделия осуществляется
при сдаче документально
- ТЕХНИЧЕСКИЙ ПРОЕКТ
- Анализ области
Стандартное использование программного продукта состоит в следующей последовательности действий пользователя:
- запуск файла «B+ Tree.exe»
- добавление данных к существующему дереву, удаление и поиск посредством использования соответствующих компонент в окне;
- закрытие окна программы;
- Структура программы
Программа состоит из двух модулей: файлы Form.cpp + Form.h, в которых описан класс TFormMain и BTree.h, где содержатся методы, описывающие алгоритмы работы с B+-деревом, а также методы для внешнего взаимодействия с этой структурой данных.
- Класс TFormMain
В этом классе описаны следующие функции:
- Отрисовка дерева;
- Чтение данных из файла;
- Поиск узла дерева, на который нажал пользователь;
- Обработка вводимых пользователем данных для поиска/удаления/добавления записи в дерево.
- Входные данные
При нажатии одной из трех кнопок («добавить», «удалить» или «найти») входными данными являются значения четырех полей: «Номер счета», «ФИО», «Сумма вклада», «Длительность (мес - %) ». При нажатии левой кнопки мыши на области вывода дерева в графическом представлении входными данными являются координаты курсора мыши.
- Выходные данные
При нажатии кнопки «найти» или щелчке мыши на области вывода дерева выходными данными могут являться строки «Номер счета», «ФИО», «Сумма вклада», «Длительность (мес - %) », а также сообщение об ошибке ввода или поиска. При нажатии на другие кнопки происходит перерисовка дерева или вывод сообщения об ошибке в случае неудачи при выполнении операции.
- Процессы обработки модуля
- создание графического интерфейса, запуск приложения;
- отрисовка окна приложения;
- обработка действий пользователя.
- Класс CB_PLUS_Tree
В этом классе описаны следующие функции:
- добавление записи в дерево;
- поиск записи в дереве по первичному ключу;
- удаление записи по первичному ключу.
- Входные данные
Запись, включающая в себя номер счета (первичный ключ), ФИО, сумма вклада и длительность (мес - %).
- Выходные данные
Результат совершения операции. В случае выполнения поиска выходными данными являются переменные, определяющие местоположение записи в дереве.
- Методические ограничения
В модулях не используется методологически сложных операций
- Аппаратные ограничения
Для корректной работы программ необходимо дисковое пространство в размере не менее 1 КБ, свободная оперативная память в размере не менее 15МБ.
- РАБОЧИЙ ПРОЕКТ
- Введение
В данном программном изделии
- Назначение разработки
Данный программный продукт наглядно демонстрирует структуру B+ - дерева.
- Требования к программе или про
граммному изделию
- Стандарты
Программное изделие выполнено согласно стандартам, указанным в техническом задании в пункте 1.4.1.
- Требования к составу и парамет
рам технических средств
Программное изделие работает на компьютере под управлением операционной системы Windows XP. Рекомендуемый объем оперативной памяти – 1024 Мбайт или более.
- Требования к информационной и программной совместимости
Программное изделие написано на языке C++ в среде разработки C++ Builder 6 и работает под управлением операционной системы Windows XP.
- Результирующие компоненты изделия
Согласно пункту 1.4.6. технического задания все файлы программы предоставляются на компакт-диске.
- Безопасность и секретность
Данный программный продукт не является секретным и не требует защиты, поэтому ограничения доступа к нему не предусматриваются.
- Рестарт
В случае, когда программа по внешним причинам перестает отвечать на запросы пользователя, необходимо нажать комбинацию клавиш «CTRL+ALT+DEL» и средствами операционной системы прервать программу.
- Описание модулей Form.h и Form.cpp
- Диаграммы классов
Рисунок 3.1
- Описание структуры Bank
В структуре имеется 4 поля: номер счета, ФИО, сумма вклада, длительность (мес - %). В структуру также входят конструктор по умолчанию, конструктор копирования и конструктор с инициализирующими значениями.
- Описание класса TFormMain
Класс TFormMain – основа для графической части данного программного продукта. На рис. 3.1 представлены все члены класса. Переменные X0,Y0 указывают смещение левого верхнего угла компоненты PaintBox, нужны для прокрутки вверх-вниз. Переменные X_max и Y_max задают границы рабочей области. X_Selected и Y_Selected – координаты выделенного ключа. Count – количество ключей в дереве. Selected – флаг, сигнализирующий о том, что имеется выделенный ключ. Changed – флаг, определяющий необходимость перестраивания дерева.
- Описание констант и макроопределений
В модулях Form.h и Form.cpp описываются следующие константы:
- #define N 3 – порядок дерева;
- #define NODE_HEIGHT 17 - высота рисуемого узла в пикселях;
- #define KEY_WIDTH 27 - ширина ключа;
- #define FONT_SIZE 8 - высота шрифта;
- #define NODE_WIDTH KEY_WIDTH*2*N - ширина узла (2N - макс. кол-во ключей);
- #define X_INTERVAL KEY_WIDTH*2 - расстояние между узлами по горизонтали;
- #define Y_INTERVAL NODE_HEIGHT*N*2 - растояние между узлами по вертикали;
- #define PERIOD (NODE_WIDTH + X_INTERVAL) - период
- #define TEXT_X0 (x1+1) – координата X для текста в клетке ключа;
- #define TEXT_Y0 (y1+1) - координата Y для текста в клетке ключа;
- #define NODE_BORDER_COLOR clBlack - цвет границ узла;
- #define ARC_COLOR clPurple - цвет дуги;
- #define SELECTED_COLOR clRed - цвет выделенного ключа;
- #define NODE_COLOR clNavy - цвет узла;
- #define TEXT_COLOR clLime - цвет текста.
- Описание подпрограмм
Подпрограмма TFormMain::TFormMain(
Входные данные: по умолчанию.
Выходные данные: нет.
Процессы обработки: инициализация переменных, вызов функции чтения данных из файла.
Подпрограмма void TFormMain::ReadFromFile(char* filename)
Входные данные: полный путь к файлу
Выходные данные: данные из файла.
Процессы обработки: чтение данных из файла и добавление их в дерево.
Подпрограмма void __fastcall TFormMain::BtnAddClick(TObject *Sender)
Входные данные: по умолчанию.
Выходные данные: нет.
Процессы обработки: чтение данных из компонент, расположенных в графическом интерфейсе и добавление их в дерево.
Подпрограмма void __fastcall TFormMain::BtnDeleteClick(
Входные данные: по умолчанию.
Выходные данные: нет.
Процессы обработки: чтение значения ключа из компоненты и удаление из дерева.
Подпрограмма void __fastcall TFormMain::BtnSearchClick(
Входные данные: по умолчанию.
Выходные данные: нет.
Процессы обработки: чтение значения ключа из компоненты и поиск записи в дереве.
Подпрограмма void __fastcall TFormMain::BtnSearchClick(
Входные данные: по умолчанию.
Выходные данные: нет.
Процессы обработки: чтение значения ключа из компоненты и поиск записи в дереве.
Подпрограмма void __fastcall TFormMain::PaintBoxPaint(
Входные данные: дерево.
Выходные данные: прорисованное в компоненте дерево.
Процессы обработки: рассчитывает при необходимости параметры узлов дерева и запускает функцию рисования дерева.
Подпрограмма void TFormMain::DrawTree(CB_PLUS_
Входные данные: указатель на текущий узел.
Выходные данные: рисование дерева.
Процессы обработки: осуществляется рекурсивный обход дерева, в ходе которого для каждого узла запускается функция отрисовки.
Подпрограмма void TFormMain::DrawNode(CB_PLUS_
Входные данные: указатель на текущий узел.
Выходные данные: рисование узла.
Процессы обработки: отрисовка узла дерева с учетом флага selected.
Подпрограмма void __fastcall TFormMain::PaintBoxMouseDown(
Входные данные: дерево.
Выходные данные: запись, хранящаяся в выделенном узле.
Процессы обработки: определение факта попадания курсора мыши внутрь какого-либо ключа, вывод сведений об этой записи в компоненты.
Подпрограмма void TFormMain::FindKey(CB_PLUS_
Входные данные: указатель на текущий узел, координаты ключа.
Выходные данные: data – найденная запись.
Процессы обработки: поиск записи по координатам ключа в ходе рекурсивного неполного обхода дерева.
Подпрограммы void __fastcall TFormMain::ScrollBarHorScroll(
Входные данные: по умолчанию.
Выходные данные: нет.
Процессы обработки: смещение начала координат при прокрутке.
Текст подпрограмм
См. Приложение А.
- Описание модуля Bstar.h
- Диаграммы классов
Рисунок 3.2
- Описание структуры CB_PLUS_
Tree <Data>::Node
Структура описана внутри класса-шаблона CBTree, в нее входят следующие переменные:
- Data* item - массив записей. В узле находятся сами записи, а не указатели;
- Node** ptr - массив указателей на другие узлы;
- Node* parent – предшественник (родитель) узла;
- short keys_count - количество занятых мест в узле;
- short index - номер узла в списке детей (от 0 до 2Т-1);
- bool leaf - является ли узел листом;
- short level - уровень в иерархии, глубина. 0 у корня.
- short width - ширина (количество листьев, родственных узлу). Для листьев = 1
- short indent – отступ. Число левых листьев, не родственных узлу
- static short T - порядок дерева
В структуре присутствует 4 различных конструктора и деструктор.
- Описание класса template <class Data> class CB_PLUS_Tree
Класс CBTree является шаблонным, Data определяет данные, которые будут содержаться в записи, в классе Data обязательно наличие поля int key и конструктора копирования. В классе содержится переменная: Node* root – корень.
- Описание констант и макроопределений
В модуле BTree.h описывается перечисляемый тип RESULT со следующими значениями:
- SUCCESS - успешное выполнение операции;
- NOT_FOUND – элемент не найден;
- NO_FREE_SPACE – нет свободного места в узле;
- KEY_ALREADY_EXISTS – ключ уже содержится в дереве;
- NOT_ENOUGH_KEYS – недостаточно ключей для перемещения.
- Описание подпрограмм
Подпрограмма Node::Node(Data data, Node* p, short i, bool l)
Входные данные: запись, указатель на предшествующий узел, индекс (номер узла в списке детей), признак листа.
Выходные данные: нет.
Процессы обработки: конструктор, создающий объект типа Node с единственной записью data, родителем p, индексом I и признаком листа leaf.
Подпрограмма Node:: Node(Data* data, Node** ptrs, short start, short count, Node* p, short ind, bool l)
Входные данные: массив записей, массив указателей, начальная позиция, количество записей в узле, указатель на предшествующий узел, индекс, признак листа.
Выходные данные: нет.
Процессы обработки: конструктор создает объект типа Node с count записями и count+1 указателями, взятыми из массивов data и ptrs. Инициализирует значения полей KeysCount, parent, index, IsLeaf.
Подпрограмма Node:: ~Node(void)
Входные данные: нет.
Выходные данные: нет.
Процессы обработки: деструктор, который освобождает память, выделенную под объект Node и обнуляет значения полей.
Подпрограмма CB_PLUS_Tree <Data>::CBTree(void)
Входные данные: нет.
Выходные данные: нет.
Процессы обработки: конструктор, в котором инициализируются значения полей класса.
Подпрограмма CB_PLUS_Tree <Data>::CBTree(void)
Входные данные: нет.
Выходные данные: нет.
Процессы обработки: деструктор, вызывающий функцию удаления дерева.
Подпрограмма RESULT CB_PLUS_Tree <Data>::AddKey(Data d)
Входные данные: запись с данными.
Выходные данные: SUCCESS в случае успеха, KEY_ALREADY_EXISTS – если запись с таким же ключом содержится в дереве.
Процессы обработки: происходит добавление записи d в дерево, в случае переполнения – вызов функции разбиения SplitNode.
Краткая блок-схема алгоритма
Подпрограмма CB_PLUS_Tree<Data>::Node*CB_
Входные данные: запись с данными, текущий узел, переменная для хранения индекса записи (номер записи в узле).
Выходные данные: функция возвращает указатель на узел, в котором завершился поиск. В случае удачного поиска значение переменной index отличается от -1.
Процессы обработки: рекурсивный поиск записи в дереве (поддереве), начинающийся в узле CurrentNode.
Подпрограмма RESULT CB_PLUS_Tree<Data>::DeleteKey(
Входные данные: запись с данными.
Выходные данные: SUCCESS в случае успеха, NOT_FOUND – если записи с ключом d.key нет в дереве.
Процессы обработки: поиск записи в узле, удаление либо замена записи d, вызов функции Balancing, которая перераспределяет ключи для сохранения структуры B+-дерева
Подпрограмма void CB_PLUS_Tree<Data>::SplitNode(
Входные данные: узел, в котором произошло переполнение.
Выходные данные: 2 узла, созданных при разделении.
Процессы обработки: расщепление узла node на 2. Если процесс достигает корня, то он расщипляется на 2 узла и создается новый корень, тем самым высота дерева увеличивается на 1.
Подпрограмма void CBTree<Data,T>::EraseKeys(
Входные данные: узел, из которого нужно удалить count ключей с позиции start.
Выходные данные: удаленные ключи.
Процессы обработки: удаляется count ключей с позиции start из узла node. В результате этой операции ненулевые записи в узле остаются упорядоченными, а нулевые записи остаются справа.
Подпрограмма void CB_PLUS_Tree<Data>:: ErasePointers(Node* node,short start, short count)
Входные данные: узел, из которого нужно удалить count указателей с позиции start.
Выходные данные: удаленные указатели.
Процессы обработки: удаляется count указателей с позиции start из узла node. В результате этой операции ненулевые указатели в узле остаются упорядоченными, а нулевые остаются справа.
Подпрограммы RESULT CB_PLUS_Tree<Data>::
Входные данные: узел, в который нужно переместить запись.
Выходные данные: SUCCESS – успешное перемещение, NOT_FOUND – если соседнего левого/правого узла не существует, NOT_ENOUGH_KEYS – если в соседних узлах недостаточно ключей для перемещения.
Процессы обработки: рекурсивный проход вправо(влево) в поисках «свободного» ключа и перемещение его влево (вправо).
Подпрограмма CB_PLUS_Tree<Data>::Node*CB_
Входные данные: узел, из которого нужно удалить запись. index – номер записи в листовом узле, которую нужно удалить.
Выходные данные: листовой узел, из которого произошло удаление.
Процессы обработки: если node – нелистовой узел, то в нем нужно заменить запись с номером index на запись из потомка. Затем функция применяется рекурсивно к потомку. Если node – листовой узел, то возвращаем указатель на него, а index становится равным номеру перемещенной записи, которую теперь нужно удалить.
Подпрограмма void CB_PLUS_Tree<Data>::Balancing(
Входные данные: узел, из которого произошло удаление.
Выходные данные: перемещенные ключи из соседнего узла.
Процессы обработки: в случае нехватки ключей в узле node вызываются функции перемещения ключей из соседних узлов (TransferFromLeftNode и TransferFromRightNode). Если они не дают нужного результата, вызывается функция ConcatNodes, собирающая 2 в 1. Далее весь процесс повторяется для узла-родителя.
.
Подпрограмма void CB_PLUS_Tree<Data>::
Входные данные: самый левый из узлов, которые нужно «склеить».
Выходные данные: узел, созданный при лбъединении.
Процессы обработки: в общем случае собираются массив записей из ключей склеиваемых узлов и ключей-разделителей родителя и массив указателей. Потом из этих массивов выбирается средний ключ, который перемещается в узел верхнего уровня, замещая два старых ключа-разделителя, далее создается два узла из первой и второй половин массивов записей и указателей. Если. node – прямой потомок корня, который содержит 1 ключ, то корень удаляется и создается новый корень, включающий записи двух узлов и ключ-разделитель из удаленного корня. Таким образом высота дерева уменьшается на 1.
Подпрограмма void CB_PLUS_Tree<Data>::
Входные данные: текущий узел.
