Программная реализация B+-дерева

1. Стандарты

Программное изделие выполнено  согласно стандартам, указанным в  техническом задании в пункте 1.4.1.

2. Требования к составу и параметрам технических средств

Программное изделие работает на компьютере под управлением операционной системы  Windows XP. Рекомендуемый объем оперативной памяти – 1024 Мбайт или более.

3. Требования к информационной и программной совместимости

Программное изделие написано на языке  C++ в среде разработки C++ Builder 6  и работает под управлением операционной системы Windows XP.

4. Результирующие компоненты изделия

Согласно пункту 1.4.6. технического задания все файлы программы  предоставляются на компакт-диске.

5. Безопасность и секретность

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

6. Рестарт

В случае, когда программа по внешним  причинам перестает отвечать на запросы  пользователя, необходимо нажать комбинацию клавиш «CTRL+ALT+DEL» и средствами операционной системы прервать программу.

4. Описание модулей Form.h и Form.cpp

1. Диаграммы классов

 

Рисунок 3.1

2. Описание структуры Bank

В структуре имеется 4 поля: номер  счета, ФИО, сумма вклада, длительность (мес - %). В структуру также входят конструктор по умолчанию, конструктор копирования и конструктор с инициализирующими значениями.

3. Описание класса TFormMain

Класс TFormMain – основа для графической части данного программного продукта. На рис. 3.1 представлены все члены класса. Переменные X0,Y0 указывают смещение левого верхнего угла компоненты PaintBox, нужны для прокрутки вверх-вниз. Переменные X_max и Y_max задают границы рабочей области. X_Selected и Y_Selected – координаты выделенного ключа. Count – количество ключей в дереве. Selected – флаг, сигнализирующий о том, что имеется выделенный ключ. Changed – флаг, определяющий необходимость перестраивания дерева.

4. Описание констант и макроопределений

В модулях 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 - цвет текста.

5. Описание подпрограмм

Подпрограмма TFormMain::TFormMain(TComponent* Owner)

Входные данные: по умолчанию.

Выходные данные: нет.

Процессы обработки: инициализация  переменных, вызов функции чтения данных из файла.

Подпрограмма void TFormMain::ReadFromFile(char* filename)

Входные данные: полный путь к файлу

Выходные данные: данные из файла.

Процессы обработки: чтение данных из файла и добавление их в дерево.

Подпрограмма void __fastcall TFormMain::BtnAddClick(TObject *Sender)

Входные данные: по умолчанию.

Выходные данные: нет.

Процессы обработки: чтение данных из компонент, расположенных  в графическом интерфейсе и добавление их в дерево.

Подпрограмма void __fastcall TFormMain::BtnDeleteClick(TObject *Sender)

Входные данные: по умолчанию.

Выходные данные: нет.

Процессы обработки: чтение значения ключа из компоненты и удаление из дерева.

Подпрограмма void __fastcall TFormMain::BtnSearchClick(TObject *Sender)

Входные данные: по умолчанию.

Выходные данные: нет.

Процессы обработки: чтение значения ключа из компоненты и поиск записи в дереве.

Подпрограмма void __fastcall TFormMain::BtnSearchClick(TObject *Sender)

Входные данные: по умолчанию.

Выходные данные: нет.

Процессы обработки: чтение значения ключа из компоненты и поиск записи в дереве.

Подпрограмма void __fastcall TFormMain::PaintBoxPaint(TObject *Sender)

Входные данные: дерево.

Выходные данные: прорисованное в компоненте дерево.

Процессы обработки: рассчитывает при необходимости параметры узлов дерева и запускает функцию рисования дерева.

Подпрограмма void TFormMain::DrawTree(CB_PLUS_Tree <Data>::Node* node)

Входные данные: указатель на текущий  узел.

Выходные данные: рисование дерева.

Процессы обработки: осуществляется рекурсивный обход дерева, в ходе которого для каждого узла запускается функция отрисовки.

Подпрограмма void TFormMain::DrawNode(CB_PLUS_Tree <Data>::Node* node)

Входные данные: указатель на текущий  узел.

Выходные данные: рисование узла.

Процессы обработки: отрисовка узла дерева с учетом флага selected.

Подпрограмма void __fastcall TFormMain::PaintBoxMouseDown(TObject *Sender,TMouseButton Button, TShiftState Shift, int X, int Y)

Входные данные: дерево.

Выходные данные: запись, хранящаяся в выделенном узле.

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

Подпрограмма void TFormMain::FindKey(CB_PLUS_Tree<Bank>::Node* node, int x, int y, Bank & data)

Входные данные: указатель на текущий  узел, координаты ключа.

Выходные данные: data – найденная запись.

Процессы обработки: поиск  записи по координатам ключа в ходе рекурсивного неполного обхода дерева.

Подпрограммы void __fastcall TFormMain::ScrollBarHorScroll(TObject *Sender,TScrollCode ScrollCode, int &ScrollPos) и void __fastcall TFormMain::ScrollBarVertScroll(TObject *Sender,TScrollCode ScrollCode, int &ScrollPos)

Входные данные: по умолчанию.

Выходные данные: нет.

Процессы обработки: смещение начала координат при прокрутке.

 

Текст подпрограмм

См. Приложение А.

5. Описание модуля Bstar.h

1. Диаграммы классов

Рисунок 3.2

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 различных  конструктора и деструктор.

3. Описание класса template <class Data> class CB_PLUS_Tree

Класс CBTree является шаблонным, Data определяет данные, которые будут содержаться в записи, в классе Data обязательно наличие поля int key и конструктора копирования. В классе содержится переменная: Node* root – корень.

4. Описание констант и макроопределений

В модуле BTree.h описывается перечисляемый тип RESULT со следующими значениями:

• SUCCESS  -  успешное выполнение операции;
• NOT_FOUND – элемент не найден;
• NO_FREE_SPACE – нет свободного места в узле;
• KEY_ALREADY_EXISTS – ключ уже содержится в дереве;
• NOT_ENOUGH_KEYS – недостаточно ключей для перемещения.

5. Описание подпрограмм

Подпрограмма 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.

Краткая блок-схема алгоритма приведена  на рис. 3.3.

Подпрограмма CB_PLUS_Tree<Data>::Node*CB_PLUSTree<Data>::SearchKey(const Data & d, Node* Node, short & index)

Входные данные: запись с данными, текущий узел, переменная для хранения индекса записи (номер записи в узле).

Выходные данные: функция возвращает указатель на узел, в котором завершился поиск. В случае удачного поиска значение переменной index отличается от -1.

Процессы обработки: рекурсивный поиск записи в дереве (поддереве), начинающийся в узле CurrentNode.

Подпрограмма RESULT CB_PLUS_Tree<Data>::DeleteKey(Data d)

Входные данные: запись с данными.

Выходные данные: SUCCESS в случае успеха, NOT_FOUND – если записи с ключом d.key нет в дереве.

Процессы обработки: поиск записи в узле, удаление либо замена записи d, вызов функции Balancing, которая перераспределяет ключи для сохранения структуры B+-дерева

Подпрограмма void CB_PLUS_Tree<Data>::SplitNode(Node* node)

Входные данные: узел, в котором произошло переполнение.

Выходные данные: 2 узла, созданных при разделении.

Процессы обработки: расщепление узла node на 2. Если процесс достигает корня, то он расщипляется на 2 узла и создается новый корень, тем самым высота дерева увеличивается на 1.

Подпрограмма void CBTree<Data,T>::EraseKeys(Node* node,short start, short count)

Входные данные: узел, из которого нужно  удалить 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>::TransferFromLeftNode(Node* dest) и RESULT CB_PLUS_Tree<Data>::TransferFromRightNode(Node* dest)

Входные данные: узел, в который  нужно переместить запись.

Выходные данные: SUCCESS – успешное перемещение, NOT_FOUND – если соседнего левого/правого узла не существует, NOT_ENOUGH_KEYS – если в соседних узлах недостаточно ключей для перемещения.

Процессы обработки: рекурсивный  проход вправо(влево) в поисках «свободного» ключа и перемещение его влево (вправо).

Подпрограмма CB_PLUS_Tree<Data>::Node*CB_PLUS_Tree<Data>::ReplaceKey(Node* node, short & index)

Входные данные: узел, из которого нужно  удалить запись. index – номер записи в листовом узле, которую нужно удалить.

Выходные данные: листовой узел, из которого произошло удаление.

Процессы обработки: если node – нелистовой узел, то в  нем нужно заменить запись с номером index на запись из потомка. Затем функция применяется рекурсивно к потомку. Если node – листовой узел, то возвращаем указатель на него, а index становится равным номеру перемещенной записи, которую теперь нужно удалить.

Подпрограмма void CB_PLUS_Tree<Data>::Balancing(Node* node)

Входные данные: узел, из которого произошло  удаление.

Выходные данные: перемещенные ключи из соседнего узла.

Процессы обработки: в случае нехватки ключей в узле node вызываются функции перемещения ключей из соседних узлов (TransferFromLeftNode и TransferFromRightNode). Если они не дают нужного результата, вызывается функция ConcatNodes, собирающая 2 в 1. Далее весь процесс повторяется для узла-родителя.

.

Подпрограмма void CB_PLUS_Tree<Data>::ConcatNodes(Node* node)

Входные данные: самый левый из узлов, которые нужно «склеить».

Выходные данные: узел, созданный при лбъединении.

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

Подпрограмма void CB_PLUS_Tree<Data>::AssignLevels(Node* node)

Входные данные: текущий узел.