Организация эффективного размещения данных в ЭВМ на основе модифицированного метода В-деревьев

• Автор: Левков, Александр Александрович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Уфа
• Количество страниц: 125 с. : ил.

ОГЛАВЛЕНИЕ
Введение

Глава 1. Структура размещения данных по первичным ключам

1.1. Структура организации Врдерева

1.2. Алгоритмы работы Врдерева.

1.2.1. Поиск элемента

1.2.2. Вставка элемента

1.2.3. Удаление элемента.

1.3. Анализ экономичности предложенной структуры размещения

. . справочников на физических носителях

1.4. Алгоритм поиска данных в узлах Врдерева.

1.5. Анализ быстродействия предложенной структуры размещения
справочников на физических носителях.
1.5.1. Линейный поиск
1.5.2. Бинарный поиск
д 1.5.3. Интерполяционный поиск.
, 1.5.4. Граничный интерполяционный поиск.
1.6. Выводы по первой главе.
Глава 2. Структура размещения данных по вторичным ключам
2.1. Описание структуры.
2.2. Алгоритмы работы.
2.2.1. Поиск элемента
2.2.2. Вставка элемента.
2.2.3. Удаление элемента
2.3. Анализ эксплуатационных характеристик предлагаемой структуры организации многомерных данных.
2.4. Выводы по второй главе.
Глава 3. Разработка програмного обеспечения, реализующего предложенные модели хранения данных и оценка их практического
эффекта.
3.1. Предварительные замечания
3.2. Построение справочников на основе Врдеревьев
3.3. Структура программного обеспечения.
3.4. Оценка эффективности разработанного программного обеспечения на примере хранения биллинговой информации учета пользовательского трафика
3.5. Построение хранилища разреженных многомерных данных на
основе скс1деревьев.
3.6. Выводы по третьей главе.
Заключение
Список литературы


В+-деревья являются структурой, ориентированной на хранение часто обновляющихся данных и способна оперировать данными, находящимися как во внутренней, так и во внешней памяти. Время поиска данных в В+-дереве в 0- раз меньше времени поиска в связном списке, однако в 1. Коэффициент избыточности В+-дерева находится в пределах 1. На данный момент именно эта структура наиболее широко используется в СУБД в качестве модели поиска по первичному ключу. Это связано еще и с тем, что для В+-деревьев наибольшее время поиска лишь незначительно отличается от среднего [, , 9, 6, 8, 9]. Список пропусков является вероятностной структурой основанной на связном списке. Он также как и В+-деревья ориентирован на работу с часто обновляющимися данными. Время поиска данных в списке пропусков примерно в 1. В+-деревьев, а коэффициент избыточности чуть выше. Основной отличительной особенностью списка пропусков является его вероятностная природа: отклонения реальных значений времени поиска элемента от среднего гораздо более значительны, нежели у В+-деревьев. В отличие от последних, максимальное время поиска данных в списке пропусков ограничено лишь длиной структуры (что на несколько порядков больше, чем у В+-деревьев). Именно эта причина является основным препятствием использования списка пропусков в системах реального времени [9]. Модель Коэф. В+-деревья 1. Список пропусков 1. Многомерные массивы (ММ) на данный момент являются одним из наиболее распространенных методов организации поиска по вторичным ключам. Они наиболее широко используются в многомерных БД (МБД). Хотя скорость поиска данных в многомерных массивах высока, однако она находится в зависимости от того, по какой оси многомерного массива ведется поиск. Кроме того, многомерные массивы имеют высокий коэффициент избыточности (3-0), что ограничивает их использование в БД большого объема (более 0-0 Мбайт) [, , 1, 2, 2, 3, 7]. Реляционные схемы «звезда» и «снежинка» являются проекцией многомерного массива на плоскость реляционной таблицы, и не могут рассматриваться как самостоятельная модель поиска по вторичным ключам, т. В+-деревьях. ОЬАР-приложениях делает необходимым их рассмотрение. Коэффициенты избыточности для схем «звезда» и «снежинка» отличаются незначительно и превышают многомерные массивы, а скорость поиска данных отличается от последних крайне незначительно. Все это делает невозможным применение данных моделей для поиска по вторичным ключам в больших БД [, , 3, 2, 2, 5, 3, 4]. Многомерное хеширование состоит из множества различных методов организации вторичных ключей в хеш. Они имеют незначительные отличия в способах организации оглавления хеша и в эксплуатационных характеристиках. Наиболее удачной реализацией многомерного хеша является «файл с двойной сеткой». Его коэффициент избыточности составляет около 1. Время поиска данных меньше, нежели в многомерных массивах, к тому же многомерное хеширование в отличие от массивов изначально ориентированно на хранение больших объемов данных и приспособлено для операций с внешними накопителями [, , , , , 9]. В-деревьев), ориентированными на работу с многомерными данными. Алгоритмы их работы не имеют значительных отличий от работы В-деревьев, поэтому им присущи все их недостатки: существует вероятность такого поступления данных, при котором будет построено вырожденное дерево. Процедура балансировки к-с! Коэффициент избыточности к-с! Однако вставка и удаление элементов могут выполняться в десятки раз дольше, в связи с необходимостью балансировки дерева. Существует модификация к-с! Однако коэффициент избыточности данной структуры составляет 2-4 [2, 8, , , ,, , , ,, ,, , ]. Модель Коэф. Из проведенного анализа видно, что ни одна из вышеперечисленных моделей поиска по первичным и вторичным ключам не обеспечивает высокой скорости поиска данных одновременно с низки коэффициентом избыточности. Это затрудняет их использование в целом ряде практических областей, для которых характерны частые запросы на получение больших объемов информации при потоковом режиме ее поступления.