Введение
Глава 1. Структура размещения данных по первичным ключам 15
1.1. Структура организации Вр-дерева 15
1.2. Алгоритмы работы Вр-дерева 24
1.2.1. Поиск элемента 24
1.2.2. Вставка элемента 26
1.2.3. Удаление элемента 30
1.3. Анализ экономичности предложенной структуры размещения справочников на физических носителях 34
1.4. Алгоритм поиска данных в узлах Вр-дерева 37
1.5. Анализ быстродействия предложенной структуры размещения справочников на физических носителях 39
1.5.1. Линейный поиск 40
1.5.2. Бинарный поиск 41
1.5.3. Интерполяционный поиск 43
1.5.4. Граничный интерполяционный поиск 44
1.6. Выводы по первой главе 52
Глава 2. Структура размещения данных по вторичным ключам 54
2.1. Описание структуры 54
2.2. Алгоритмы работы 60
2.2.1. Поиск элемента , 61
2.2.2. Вставка элемента 65
2.2.3. Удаление элемента 69
2.3. Анализ эксплуатационных характеристик предлагаемой структуры организации многомерных данных 74
2.4. Выводы по второй главе 83
Глава 3. Разработка програмного обеспечения, реализующего предложенные модели хранения данных и оценка их практического эффекта 84
3.1. Предварительные замечания 84
3.2. Построение справочников на основе Вр-деревьев 88
3.3. Структура программного обеспечения 92
3.4 Оценка эффективности разработанного программного обеспечения на примере хранения биллинговой информации учета пользовательского трафика 93
3.5. Построение хранилища разреженных многомерных данных на основе d-k-d-деревьев 98
3.6. Выводы по третьей главе 105
Заключение 107
Список литературы 109
Приложение 1 123
Приложение 2 126
