Демонстрационная программа «Б-деревья»

Министерство образования и науки Российской Федерации

Юго-Западный государственный университет


Кафедра Вычислительной Техники















Демонстрационная программа «Б-деревья»































Выполнил: студент группы ВМ-91

Шарковский В.В.



Проверил д.т.н. Зотов И.В.

Содержание

1. Задание

2.Краткая теория

3. Алгоритм главных функций

4. Интерфейс программы

5. Результаты тестирования

6. Краткий исходный код программы

































































Задание

Разработать демонстрационную программу «Б-деревья».
Осуществить возможность добавления, поиска и удаленияэлемента из Б-дерева.
Вывод дерева на экран.
Тип данных: выбирается пользователем.
Параметр t≥2: вводится с клавиатуры (должен быть в диапазоне 2..9)




















































Краткая теория
[pic] Б-деревья — это один из видов сбалансированных деревьев, обеспечивающих эффективное хранение информации на магнитных дисках идругих устройствах с прямым доступом. Б-деревья похожи на красно-черные, разница в том, что в Б-дереве узел может иметь много детей, на практике до тысячи, в зависимости от характеристик используемого диска. Благодаря этому константа в оценке O(log n) для высоты дерева существенно меньше, чем для красно-черных деревьев. Как и красно-черные деревья, Б-деревья позволяют реализовать многие операции смножествами размера n за время O(log n).
Узел x, хранящий n[x] ключей, имеет n[x] + 1 детей. Хранящиеся в x ключи служат границами, разделяющими всех его потомков на n[x] + 1 групп; за каждую группу отвечает один из потомков x. При поиске в Б-дереве мы сравниваем искомый ключ с n[x] ключами, хранящимися в x, и по результатам сравнения выбираем одного из n[x] + 1 потомков.
Особенности работы с информацией,размещаемой на диске

Алгоритмы, работающие с Б-деревьями, хранят в оперативной памяти лишь небольшую часть всей информации (фиксированное число секторов).
Б-дерево устроено следующим образом. Каждый узел x содержит следующие поля:

* n[x] — количество ключей, хранящихся в узле x ;
* key_1[x],key_2[x],…, key n[x]_ [x] — сами ключи в неубывающем порядке;
* leaf[x] — булевскоезначение, истинное, когда узел x является листом.

Если x — внутренний узел, то он содержит указатели c_1[x], c_2[x],…, cn[x]+1_[x] на его детей в количестве n[x] + 1.

* У листьев детей нет, и эти поля для них не определены.
* Все листья находятся на одной и той же глубине, равной высоте дерева.
* Возможное число ключей, хранящихся в одном узле, определяется параметром t ≥2, которое называетсяминимальной степенью Б-дерева.
* Для каждого некорневого узла x выполняется неравенство (t- 1) ≤ n[x]≤(2t - 1). Таким образом, число детей у любого внутреннего узла (кроме корня) находится в пределах от t до 2t.
* Если дерево не пусто, то в корне должен храниться хотя бы один ключ. Узел, хранящий ровно 2t - 1 ключей, будет называться полным.

Ключи key_i[x] служат границами,разделяющими значения ключей в поддеревьях. Точнее,

* c_1[x] ссылается на поддерево, ключи в котором меньше, чем key_1[x] ;
* c_i[x] при i = 2, 3,…,n ссылается на поддерево, ключи в котором находятся в пределах от key i-1_ [x] до key_i[x] ;
* cn[x]+1_[x] ссылается на поддерево, ключи в котором больше, чем key_{n[x]}[x].

В случае, когда t = 2, у каждого внутреннего узла 2, 3 или 4 потомка,получается так называемое 2 - 3 - 4 -дерево. Для эффективной работы с диском на практике t выбирают достаточно большим. Число обращений к диску для большинства операций пропорционально высоте Б-дерева.

Поиск в Б-дереве похож на поиск в двоичном дереве. Разница в том, что в каждом узле x выбирается один вариант из (n[x] +1), а не из двух. При поиске...