reforef.ru 1

Оглавление

Оглавление 4

Введение. 5

1.Разработка приложения, реализующего основные функции работы с Б-деревьями во внешней памяти. 6

1.1.Анализ предметной области. 6

1.2.Анализ требований. 7

1.2.1.Требования к интерфейсу Пользователя 7

1.2.2.Требования к программным средствам. 8

2.Проектирование. 8

2.1.Проектирование интерфейса пользователя. 8

2.2.Проектирование структуры данных. 10

3.Реализация. 12

3.1.Основные операции с деревом. 12

3.1.1.Операция вставки ключа. 12

3.1.2.Операция удаления ключа. 15

3.2.Реализация интерфейса. 19

Заключение. 20

Список использованных источников. 21

Приложение А. Модуль класса «B-дерево». 22

Приложение Б. Модуль класса главной формы. 31

Приложение В. Модуль класса формы для отображения дерева в традиционной форме. 37


Диаграмма вариантов использования!

Введение.


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

Одной из самых эффективных и в то же время сложных структур является B-дерево. Её использование впервые было предложено Р. Бэйером и Е. Маккрейтом в 1970. Вскоре оно стало стандартом де-факто для организации файловых систем и баз данных. Причины такой популярности, особенности структуры и алгоритмы работы с ней будут рассмотрены в этой курсовой работе.

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

  1. Разработка приложения, реализующего основные функции работы с Б-деревьями во внешней памяти.

    1. Анализ предметной области.

В-дерево Т представляет собой корневое дерево, обладающее следующими свойствами:


  1. Каждый узел х содержит следующие поля:

  1. n[х], количество ключей, хранящихся в настоящий момент в узле х.

  2. Собственно ключи, количество которых равно n[х] и которые хранятся в невозрастающем порядке, так что key1[х]? key2[х]?…? keyn[x][х].

  3. Логическое значение leaf[х], равное TRUE, если х является листом, и FALSE, если х — внутренний узел.

  4. Индекс, указывающий на местоположение узла в файле.

  1. Кроме того, каждый внутренний узел х содержит n[х] +1 указателей с1[х], с2[х], с3[х], … , сn[x]+1[х] на дочерние узлы. Листья не имеют дочерних узлов, так что их поля сi не определены.

  2. Ключи keyi[х] разделяют поддиапазоны ключей, хранящихся в поддеревьях: если ki — произвольный ключ, хранящийся в поддереве с корнем сi[х], то

k1 ? key1[х]? k2 ? key2[х]?…? keyn[x][х] ?k n[x]+1

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

  2. Имеются нижняя и верхняя границы количества ключей, которые могут содержаться в узле. Эти границы могут быть выражены с помощью одного фиксированного целого числа t?2, называемого минимальной степенью В-дерева:
  1. Каждый узел, кроме корневого, должен содержать как минимум t -1 ключей. Каждый внутренний узел, не являющийся корневым, имеет, таким образом, как минимум t дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ.


  2. Каждый узел содержит не более 2t-1 ключей. Таким образом, внутренний узел имеет не более 2t дочерних узлов. Мы говорим, что узел заполнен, если он содержит ровно 2t-1 ключей.


Поскольку время выполнения алгоритма, работающего с В-деревьями, зависит в первую очередь от количества выполняемых операций с диском (чтение и запись), желательно минимизировать их количество. При этом надо учесть, что количество обращений к диску для выполнения операций с деревом пропорционально его высоте.
    1. Анализ требований.

      1. Требования к интерфейсу Пользователя


При использовании программы пользователю должны быть предоставлены следующие возможности:

  • Сгенерировать дерево из заданного количества ключей;

  • Добавить ключ;

  • Удалить ключ;

  • Найти ключ;

  • Сохранить дерево в файле;

  • Открыть файл с деревом;

  • Просмотреть дерево в наглядном виде.

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


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

  • Прочитать страницу из файла;

  • Записать страницу в файл;

  • Добавить ключ;

  • Удалить ключ;

  • Найти ключ;

  • Сохранить дерево;

  • Восстановить дерево из файла;

Взаимодействие этих функций отображено на диаграмме вариантов использования.

  1. Проектирование.

    1. Проектирование интерфейса пользователя.



Рис. 1. Главное окно приложения.



Рис. 2. Диалоговое окно для генерации дерев.

Описание элементов интерфейса главного окна:


    1. Имя текущего файла;

    2. Деревья до и после операции;

    3. Вызов диалогового окна для генерации дерева из указанного количества элементов;

    4. Добавление ключа в дерево;

    5. Удаление ключа из дерева;

    6. Поиск ключа в дереве;

    7. Отображение дерева.

Описание элементов интерфейса диалогового окна для генерации дерева:





    1. Количество элементов в новом дереве;

    2. Отменить операцию;

    3. Подтвердить выполнение операции.

Диалоговые окна для добавления, удаления и поиска ключа выглядят аналогично окну «Сгенерировать дерево».