Содержание к диссертации
Введение
Глава 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
- Анализ экономичности предложенной структуры размещения справочников на физических носителях
- Граничный интерполяционный поиск
- Анализ эксплуатационных характеристик предлагаемой структуры организации многомерных данных
- Оценка эффективности разработанного программного обеспечения на примере хранения биллинговой информации учета пользовательского трафика
Введение к работе
Актуальность темы. В настоящее время не существует таких областей науки, техники и образования, в которых не использовались бы базы данных (БД) [74, 92, 94, 104, 108, 121]. Применение баз данных позволяет осуществлять централизованное хранение информации, оптимизировать доступ к данным и осуществить их компактное хранение [90, 128, 132, 133, 134, 143].
Любая система управления БД (СУБД) состоит из двух достаточно автономных модулей: модуль логического представления данных и модуль физического хранения данных [22,23,74, 75, 81, 90, 99].
Модуль логического представления данных обеспечивает диалог пользователя с БД, предоставляя графическую среду и высокоуровневый язык манипулирования данными, независимый от используемого аппаратного обеспечения. В его задачи также входит обеспечение многопользовательской работы, управление правами доступа к данным, генерация отчетов и т.д. [77, 80, 81,90,112].
Модуль физического хранения данных размещает информацию во внутренней и внешней памяти компьютера (в оперативной памяти (ОЗУ), на жестких дисках и иных носителях), манипулируя низкоуровневым, аппаратно-зависимым языком. От данного модуля зависят быстродействие СУБД и-экономичность использования аппаратных ресурсов, таких как внутренняя и внешняя память, вычислительная мощность процессора и т.д.. [4, 6, 10, 50, 90, 138, 144].
В настоящей работе будут рассмотрены модели физического хранения данных, так как без них невозможно построение быстродеиственных и экономичных СУБД, необходимых в таких областях как открытое или дистанционное образование, здравоохранение, экология и т.д.
Для сравнения различных моделей физического хранения данных обычно используют следующие критерии: коэффициент избыточности, т.е. отношение общего объема используемой памяти к объему, используемому непосредственно хранимыми данными [6, 9, 12,24, 29, 51, 109], время поиска, добавления и удаления данных (скорость работы) [6, 9, 14, 55, 65].
Следует отметить, что сравнение коэффициента избыточности принято проводить раздельно для внутренней памяти (ОЗУ) и внешней памяти (жестких дисков, CD-ROM'о в, магнитных лент и т.п.) [2, 5, 9,10, 50; 56]. Также самостоятельно оцениваются время работы с «атомарными» единицами информации и с их большими массивами. Это связано с тем, что существуют структуры, обеспечивающие медленную работу с единичными данными, но большую скорость работы с их пакетами, что может быть актуально для аналитических систем [22, 35, 37,48, 82, 99].
Как известно, большинство современных аналитических систем ориентированны на операции поиска в массивах статических или слабо меняющихся данных [19, 22, 82, 99, 104, 118, 121]. Для таких систем актуальна высокая скорость поиска больших массивов информации. С другой стороны, для систем реального времени наиболее необходимы высокая скорость добавления информации в потоковом режиме, т.е. небольшими, «атомарными» порциями. Не существует на данный момент модели физического хранения данных, обеспечивающей как высокую скорость обработки потоковых запросов, так и анализа больших массивов данных. Поэтому для каждого класса систем - аналитических либо потоковых - используются различные модели физического хранения данных [19,22, 28, 72, 137],
Однако в существующих информационных системах все чаще появляется необходимость совмещать потоковое поступление информации с ее глубоким анализом. Это особенно актуально для систем оперативного реагирования, таких как производственно-добывающие отрасли, системы экологического мониторинга, дистанционного контроля и обучения и т.д. Используемые в данном случае модели физического хранения данных должны обеспечивать добавление «атомарных» данных в режиме реального времени, оперативный поиск больших массивов информации и экономное использование памяти, в связи с большими объемами хранимых данных (100 Гбайт и выше).
В настоящее время существующие модели хранения данных на физических носителях делятся на два типа: модели поиска по первичному ключу, они необходимы для добавления «атомарных» данных в режиме реального времени [24, 32, 88, 117, 121, 122], и модели поиска по вторичным ключам, которые предоставляют возможность поиска больших массивов информации [76,93, 100, 109, 121, 138, 143].
Проанализируем основные виды данных моделей физического хранения данных.
В качестве моделей поиска по первичному ключу, как правило, используются следующие модели: связный список,
В+-дерервья, список пропусков.
Связный список представляет собой простейшую структуру, предназначенную для хранения небольших последовательностей редко обновляющихся данных. Время выполнения поиска в связном списке наибольшее среди всех моделей поиска по первичному ключу, а коэффициент избыточности примерно равен коэффициенту избыточности В+-деревьев и меньший, нежели у хеша [88].
Хеш представляет собой эффективную структуру поиска по статичным данным. В сбалансированном состоянии его коэффициент избыточности стремится к 1, время же поиска данных наименьшее среди всех известных структур. Однако, в связи с тем, что подбор хеш-функции зачастую является нетривиальной задачей, данную структуру невозможно использовать для
7 хранения часто обновляющихся данных, тем более при их поступлении в режиме реального времени [13, 27, 32, 47, 88].
В+-деревья являются структурой, ориентированной на хранение часто обновляющихся данных и способна оперировать данными, находящимися как во внутренней, так и во внешней памяти. Время поиска данных в В+-дереве в 100-1000 раз меньше времени поиска в связном списке, однако в 1.2 -1.5 раза больше времени поиска в хеше. Коэффициент избыточности В-Ь-дерева находится в пределах 1.2-1.5. На данный момент именно эта структура наиболее широко используется в СУБД в качестве модели поиска по первичному ключу. Это связано еще и с тем, что для В+-деревьев наибольшее время поиска лишь незначительно отличается от среднего [88, 90, 109, 126, 128, 129].
Список пропусков является вероятностной структурой основанной на связном списке. Он также как и В+-деревья ориентирован на работу с часто обновляющимися данными. Время поиска данных в списке пропусков примерно в 1.5 раза меньше, нежели у В+-деревьев, а коэффициент избыточности чуть выше. Основной отличительной особенностью списка пропусков является его вероятностная природа: отклонения реальных значений времени поиска элемента от среднего гораздо более значительны, нежели у В+-деревьев. В отличие от последних, максимальное время поиска данных в списке пропусков: ограничено лишь длиной структуры (что на несколько порядков больше, чем у В+-деревьев). Именно эта причина является основным препятствием использования списка пропусков в системах реального времени [129].
Ниже, в таблице 1, представлены основные характеристики перечисленных моделей поиска по первичному ключу (N - количество хранимых элементов):
Таблица 1 Характеристики основных моделей поиска по первичному ключу
Далее рассмотрим основные модели поиска по вторичным ключам: многомерные массивы, реляционные схемы «звезда» и «снежинка», многомерное хеширование, k-d —деревья.
Многомерные массивы (ММ) на данный момент являются одним из наиболее распространенных методов организации поиска по вторичным ключам. Они наиболее широко используются в многомерных БД (МВД). Хотя скорость поиска данных в многомерных массивах высока, однако она находится в зависимости от того, по какой оси многомерного массива ведется поиск. Кроме того, многомерные массивы имеют высокий коэффициент избыточности (3-100), что ограничивает их использование в БД большого объема (более 100-500 Мбайт) [76, 83, 111, 122, 142, 143, 147].
Реляционные схемы «звезда» и «снежинка» являются проекцией многомерного массива на плоскость реляционной таблицы, и не могут рассматриваться как самостоятельная модель поиска по вторичным ключам, т.к. они базируются на В+-деревьях. Однако их широкое использование в
9 OLAP-приложениях делает необходимым их рассмотрение. Коэффициенты избыточности для схем «звезда» и «снежинка» отличаются незначительно и превышают многомерные массивы, а скорость поиска данных отличается от последних крайне незначительно. Все это делает невозможным применение данных моделей для поиска по вторичным ключам в больших БД [76, 83, 103, 112, 122, 125,133,134].
Многомерное хеширование состоит из множества различных методов организации вторичных ключей в хеш. Они имеют незначительные отличия в способах организации оглавления хеша ив эксплуатационных характеристиках. Наиболее удачной реализацией многомерного хеша является «файл с двойной сеткой». Его коэффициент избыточности составляет около 1.3-2, что много меньше, нежели у многомерного массива. Время поиска данных меньше, нежели в многомерных массивах, к тому же многомерное хеширование в отличие от массивов изначально ориентированно на хранение больших объемов данных и приспособлено для операций с внешними накопителями [27, 47, 53, 56,64, 129]. k-d - деревья являются модификацией балансированных деревьев (В-деревьев), ориентированными на работу с многомерными данными. Алгоритмы их работы не имеют значительных отличий от работы В-деревьев, поэтому им присущи все их недостатки: существует вероятность такого поступления данных, при котором будет построено вырожденное дерево. Процедура балансировки k-d-дерева не может происходить в режиме реального времени. Коэффициент избыточности k-d-дерева составляет около 1.2-1.5, это наименьшее значений среди всех существующих моделей, k-d-деревья также ориентированны на работу с внешней памятью и скорость поиска данных у них в 1.5-2 раза выше, нежели у многомерного хеша. Однако вставка и удаление элементов могут выполняться в десятки раз дольше, в связи с необходимостью балансировки дерева. Существует модификация k-d-дерева, балансируемая
10 автоматически. Однако коэффициент избыточности данной структуры составляет 2-4 [2, 8, 12, 24, 26,29,34, 35, 37, 40, 50, 51, 55, 69].
Ниже, в таблице 2, представлены основные характеристики перечисленных моделей поиска по вторичным ключам (У - количество измерений):
Таблица 2
Характеристики основных моделей поиска по вторичным ключам
Из проведенного анализа видно, что ни одна из вышеперечисленных моделей поиска по первичным и вторичным ключам не обеспечивает высокой скорости поиска данных одновременно с низки коэффициентом избыточности. Это затрудняет их использование в целом ряде практических областей, для которых характерны частые запросы на получение больших объемов информации при потоковом режиме ее поступления.
Одним из возможных направлений преодоления указанных выше недостатков известных моделей физического хранения данных является: разработка новой модификации В+-деревьев, имеющий меньший коэффициент избыточности и более высокую скорость поиска элемента, разработка новой модификации k-d-деревьев, имеющей низкий коэффициент избыточности и растущей «снизу-вверх», что обеспечивает постоянную поддержку дерева в сбалансированном состоянии.
Следовательно, целью данной работы является создание новой быстродействующей и экономичной модели размещения данных на физических носителях, работающей при обновлении данных в режиме реального времени.
Задачи исследования:
Разработать способ уменьшения коэффициента избыточности В+-дерева.
Разработать новый алгоритм поиска данных в упорядоченном массиве (в узле В+-дерева).
Разработать алгоритмы балансировки k-d-дерева, не увеличивающий его коэффициент избыточности.
Создание программного обеспечения, реализующее разработанные модели хранения данных.
Проверка эффективности разработанного программного обеспечения на примере организации хранения и обработки информации в биллинговой системе анализа и учета пользовательского трафика.
Методы исследования. Результаты исследований,, выполненных в работе, базируются на методах математической статистики, теории информации и теории графов. На защиту выносятся:
Структура размещения данных на физических носителях по первичным ключам - Вр-дерево.
Алгоритм поиска данных в упорядоченном массиве.
Структура размещения данных на физических носителях по вторичным ключам - к-с1-В+-дерево.
12 Научная новизна работы заключается в следующем:
Разработана структура размещения данных на физических носителях по первичным ключам. Предложенная структура в отличие от В+-деревьев использует хранение ключей только на младшем уровне иерархии, что позволяет в значительной мере уменьшить объем внутренней памяти, занимаемый данной структурой.
Разработан новый алгоритм поиска данных в упорядоченном массиве, основанный на комбинации интерполяционного и линейного поисков. Использование данного алгоритма позволяет добиться более высокой скорости поиска данных в структуре.
Разработана структура размещения данных на физических носителях по вторичным ключам — d-k-d-дерево. Предложенная структура в отличие от k-d-дерева автоматически поддерживается в сбалансированном состоянии, занимая при этом небольшую часть внутренней памяти ЭВМ.
Практическая значимость работы:
Разработанный метод индексации данных при помощи хеш-ключей обеспечивает возможность выполнения поиска в справочнике на основе единой индексной структуры, что в значительной мере уменьшает объем используемой справочником оперативной памяти.
Предложенная структура хранения данных по первичным ключам, основанная на использовании Вр-деревьев, позволяет повысить скорость поиска элемента на треть, занимая на 20% меньше памяти, нежели В+-деревья.
Предложенная структура хранения разреженных многомерных данных, основанная на использовании d-k-d-деревьев, позволяет уменьшить общий объем памяти, занимаемый данными в 1.5 раза при значительном увеличении скорости их поиска.
Экспериментальная проверка эффективности предложенных методик и структур на примере их использования в системе сбора и анализа данных пользовательского трафика ЗАО «Деловая сеть» — крупнейшего
13 сетевого провайдера в Уфе показала высокую эффективность предложенных алгоритмов и структур.
Объем и структура работы
Диссертационная работа состоит из введения, трех глав, заключения, библиографии и 2 приложений. Основная часть содержит 128 страниц и включает в себя 60 рисунков и 21 таблицу. Список литературы содержит 152 наименования. В Приложениях приведены: фрагменты исходных кодов и акт внедрения.
Во введении производится анализ основных известных алгоритмов и структур хранения информации по первичным и вторичным ключам. Структуры сравниваются по различным параметрам, таким как: коэффициент избыточности, среднее время поиска и т.д. Среди рассмотренных структур производится выбор тех, которые будут использованы в данной работе в качестве базовых и с которыми будут производится дальнейшие сравнения.
В первой главе рассматривается задача построение структуры хранения данных по первичным ключам. Для решения поставленной задачи, предложена структура, разработанная на основе В+-дерева и алгоритма интерполяционного поиска в узле дерева.
Во второй главе рассматривается задача построение структуры хранения данных по вторичным ключам. Для решения поставленной задачи, предложена структура, разработанная на основе k-d-дерева и алгоритма интерполяционного поиска в узле дерева.
В третьей главе рассмотрены вопросы практической реализации предложенных структур и алгоритмов поиска и хранения данных по первичным и вторичным ключам.
Заключение содержит основные результаты и выводы по диссертационной работе.
Апробация работы и публикации. Основные положения диссертации докладывались и обсуждались на всероссийской молодежной научно-
14 технической конференции «Информационные и кибернетические системы управления и их элементы», г.Уфа 1997 г., на 2-й международной конференции «CSIT» 2000 г., а также на 4-й международной конференции «CSIT» 2002 г.
Основные материалы, представленные в диссертационной работе, . опубликованы в 13 работах (из них 11 статей и 2 материала конференций).
Основные результаты диссертационной работы внедрены в ЗАО «Деловая сеть» в виде модуля хранения данных, что подтверждается соответствующим актом.
Анализ экономичности предложенной структуры размещения справочников на физических носителях
Как известно, одним из компонентов быстродействия системы, наиболее влияющим на итоговое быстродействие, является алгоритм поиска данных в узле дерева, т.е. в упорядоченном массиве [88, 129, 149].
Как отмечено в [88] у Кнута, на данный момент наиболее распространены следующие два алгоритма поиска: 1. Последовательный поиск, иначе - поиск перебором. Наиболее легок в программировании, показывает хорошее быстродействие при малом количестве элементов в массиве (не более 10), однако крайне медлен при большом количестве элементов. 2. Бинарный поиск. Его алгоритм более сложен, но при большом количестве элементов в массиве он на порядок быстрее последовательного поиска.
Однако существует третий, еще более быстрый алгоритм поиска данных - интерполяционный. Он давно и успешно применяется для поиска в лингвистических и языковых системах, но практически не используется для цифровых систем. Это связано с тем, что для применения данного метода необходимы знания о законе распределения элементов в массиве. Если для лингвистических данных эти законы известны и могут быть выражены явным образом, то для набора цифровых данных в В+-дереве эти законы постоянно меняются. Затраты на обнаружение закономерностей и их изменений с вставкой новых или удалением старых данных во много раз превосходят увеличение быстродействия, предлагаемое интерполяционным алгоритмами [15,88,149].
Для использования интерполяционного поиска в условиях, когда невозможно определить закон распределения, автором предлагается алгоритм граничного интерполяционного поиска. Его суть заключается в использовании интерполяционного алгоритма на первом шаге поиска элемента при известной погрешности (dint). Погрешность для каждого узла определяется как максимальное отклонение реальных положений ключей в массиве, от интерполируемых (-dint; +dlnt).
Используя данный параметр можно легко, по формуле, предложенной в [88, 149] Дальнейший поиск целесообразно производить либо по алгоритму бинарного, либо линейного поиска. Величина отклонения реальных значений от интерполированных зависит от хеш-функции и от длинны массива: чем он больше, тем относительно уже данная область. Как показали исследования, в среднем, для реальных данных в больших аналитических системах, при большом количестве интервалов разбиения, ширина области неопределенности составляет около 1-10% от длины массива [15, 53]. Таким образом, применение граничного интерполяционного поиска позволяет значительно увеличить количество элементов в массиве без потери быстродействия, что приводит к уменьшению объема памяти, занимаемого индексной структурой справочников, либо значительно увеличить скорость поиска элемента в массиве, что приводит к значительному ускорению поиска атрибутов и индексов в справочнике. В первую очередь проведем исследование скорости поиска элементов. Как отмечено у в [5, 6, 88], скорость поиска в структурах, подобных В+-деревьям зависит от двух факторов: 1. От длины пути до искомого элемента, измеряющейся в пройденных узлах. 2. От алгоритмов поиска необходимых данных в массивах, содержащихся внутри узлов. Следует также отметить, что многое зависит от способа размещения структуры на физических носителях. Так для структуры, работающей в ОЗУ, предпочтительнее перебор большого количества вершин (длинный путь) при простых и быстрых алгоритмах поиска внутри массива, тогда как для структур, хранящихся на жестком диске, предпочтительнее использовать медленные алгоритмы поиска в массиве при обращении к меньшему количеству узлов (т.е. кластеров на жестком диске). Т.к. Вр-деревья расположены и в ОЗУ и на жестком диске, необходимо исследовать как длину пути поиска, так и алгоритм поиска в массиве, проведя их интегральную оценку. Далее, опишем используемые алгоритмы поиска элементов внутри упорядоченного массива. Таких способов можно выделить четыре: линейный поиск (поиск перебором), бинарный поиск, интерполяционный поиск, граничный интерполяционный поиск В свою очередь, существует две разновидности граничного интерполяционного поиска, в зависимости от того, какой алгоритм используется для поиска внутри области, определенной по интерполяционному алгоритму.
Граничный интерполяционный поиск
Для выбора способов балансировки k-d-деревьев в режиме реального времени без- значительного увеличения коэффициента" избыточности, рассмотрим структуру их организации.
Рис. 2.1. 2-d-дерево k-d-деревом является бинарное дерево, имеющее к координат, ветвление на каждом уровне которого базируется на сравнении одной из координат [34]. В простейшем случае, I-d-дерево представляет собой обыкновенное бинарное дерево. 2 -дерево содержит две координаты - х и у - при ветвлении на нечетных уровнях дерева сравнивается координата х, на четных - у. Пример В общем случае, при к координатах на уровне / происходит ветвление по координате (к mod /) Итоговая структура k-d-дерева зависит от порядка поступления данных. Ниже, на рис, 2.2, представлено 2-d-flepeBo, полученное вставкой 12-ти случайных ключей.
Как можно видеть из рисунка, данное дерево далеко не только от оптимального, но и от сбалансированного. К сожалению, балансировка k-d-деревьев AVL-алгоритмом невозможна, для к \. Это связанно с невозможностью «перетекания» узлов с одного уровня, на другой при к \: на каждом уровне сравнение происходит только по одной координате. Следовательно, при попытке переместить вершину с ветвлением координаты х на уровень с координатами у, дерево будет разрушено.
Для балансировки дерева при любых к Робинсоном было предложено к-d-B-дерево [50]. Данное дерево аналогично В-деревьям всегда находилось в сбалансированном состоянии, однако для данной модификации не существовало возможности установить границу для максимального коэффициента избыточности. Зачастую, для хранения каждой записи оказывался выделен целый кластер на жестком диске. В этом случае коэффициент избыточности k-d-B-деревьев приближался к коэффициенту избыточности многомерных массивов.
Для поддержки k-d-дерева в сбалансированном состоянии при ограниченном коэффициенте избыточности автором предлагается его модификация - динамическое k-d-дерево (d-k-d-дерево), автоматически балансируемое в режиме реального времени. Следует отметить все структурные особенности d-k-d-дерева: 1. Каждый узел имеет не более т потомков. 2. Каждый узел, за исключением листьев, имеет не менее п потомков. 3. Координата ветвления определяется самостоятельно для каждого узла. 4. Каждый лист заполнен не менее чем на долю s. 5. Все листья находятся на одном уровне. Ниже, на рис. 2.3, представлен общий вид k-d-B-ь-дерева, для к=2 при коэффициенте насыщенности = 5. Следует обратить внимание, что ветвление в вершинах дерева происходит не по условию больше-меньше, как это происходит в В-деревьях, а по вхождению ключа в диапазон, подобно тому, как это происходит в описанных выше Вр-деревьях. Такой подход позволяет использовать алгоритмы арифметического сжатия, когда ключи дочерних элементов заменяются смещением ключей относительно родительского элемента.
Как правило, все уровни структуры, кроме листового, хранятся в ОЗУ, тогда как листья хранятся на жестком диске.
Именно динамическое определение координаты ветвления для каждой вершины позволяет гарантировать заполненность каждой вершины в пределах от п до т. Это связано с нижеописанными причинами.
Во-первых, при жесткой фиксации определенной координаты ветвления для каждого уровня, возможна тупиковая ситуация, при которой ветвление по одной из координаты будет невозможным. Такая ситуация возникает, если большинство многомерных данных в какой-то части дерева имеют одинаковое значение данной координаты. В таком случае ветвление по данной координате невозможно, т.к. она одинакова для всех хранимых элементов. В k-d-B-дереве, предложенном Робинсоном, в данном случае происходило формирование пустого поддерева, незаполненного данными [55]. Количество таких поддеревьев в динамически растущей структуре было достаточно велико, что не позволяло эффективно использовать внутреннюю и внешнюю память.
Во-вторых, даже когда ветвление в узле по данной координате возможно,, не существует уверенности в том, что ветвление именно по данной координате будет наиболее эффективным. В данном случае в результате жестко заданной координаты ветвления поддеревья узла могут значительно отличаться по мощности (т.е. по количеству хранимых элементов), что приводить к невозможности контроля за количеством памяти, занимаемым k-d-B-деревом [50].
Динамический выбор координаты ветвления в каждом узле позволяет избежать таких проблем, т.к. для ветвления выбирается координата наилучшим образом подходящая для образования равномощных поддеревьев.
В случае, когда количество вторичных ключей в структуре велико, необходим выбор из большого количества координат, обеспечивающих примерно одинаково удачные варианты ветвления. Данный выбор может осуществляться по многим критериям. Основной из них: использование для ветвления той координаты, по которой ранее ветвление происходило реже всего. Это условие позволяет обеспечивать примерно одинаковое время поиска элемента по любой из координат и предотвращает построение дерева меньшей мерности (тот случай, когда для построения d-k-d-дерева могла бы использоваться всего одна координата ветвления).
Следует отметить, что при построении d-k-d-дерева не всегда возможно осуществить ветвление по всем существующим координатам. Это происходит тогда, когда в структуре хранится сравнительно небольшое число записей, состоящих из большого количества вторичных ключей. В этом случае количество уровней в дереве может быть меньшим, нежели количество вторичных ключей.
Анализ эксплуатационных характеристик предлагаемой структуры организации многомерных данных
В- данной главе- будет рассмотрена практическая реализация вышеописанных моделей хранения данных и поиска по первичным и вторичным ключам.
В отличие от большинства программных продуктов, имеющих интерфейс с пользователем, данная программная реализация не имеет визуального интерфейса. Это связано с тем, чтоона не предназначена для непосредственной работы с пользователем, а только с моделью логического представления данных. Интерфейс данной программы реализован на основе проецируемых в память файлов, что позволяет достичь высокой скорости обмена данными с программами окружения. Все взаимодействие с пользователем возлагается на программы окружения и имеет лишь косвенный характер: никакие параметры реализованной структуры не задаются пользователем напрямую, а вычисляются самой программой на основе характеристик аппаратного обеспечения, специфики хранимых данных, желаемого пользователем соотношения экономичности-быстродействия и т.д. В качестве программы окружения в данной работе использовалась многомерная база данных (МБД), обеспечивающей анализ данных в биллинговой системе учета пользовательского трафика.
Конечный пользователь взаимодействует с гиперкубом (или с их множеством в поликубической модели). Гиперкуб представляет собой уровень абстракции, на котором производится визуализация данных. Измерения (размерности) гиперкуба проиндексированы и все их значения (атрибуты) хранятся в справочниках. Тело гиперкуба представляет собой разреженные многомерные данные.
Каждый справочник представляет собой два В+-дерева (в MOLAP-системах Microsoft и Oracle), где первое предназначено для выполнения прямого, а второе - обратного поиска, т.е. поиска индексов по атрибутам и атрибутов по индексам соответственно. Как известно, количество справочников даже для небольшой МБД достигает десятков и сотен [19, 74, 111, 122, 133, 146], а для проведения аналитического запроса требуется обращение к большинству из них. В случае, когда гиперкуб содержит более 5 размерностей (или количество кубов, участвующих в запросе велико), время, затрачиваемое на поиск информации в справочниках, более чем в два раза превышает время поиска данных в теле гиперкуба. В данных условиях, быстродействие В+-деревьев оказывается недостаточным. Кроме того, при вставке данных в; справочники значительное время отнимают операции перестроения самого В+-дерева: переливание индексов (атрибутов в случае прямого поиска) с уровня на уровень, расщепление вершин дерева и т.д.
Недостатки использования MOLAP-систем заключаются, в неэффективном использовании памяти (коэффициент избыточности может достигать 10-100) [19, 138]. Хотя при их сжатии (как правило, по zip-алгоритму) память используется почти также экономно, как и в РБД, но данный метод значительно замедляет работу МБД, в связи с необходимостью распаковки данных при любых операциях с ними. При использовании же ROLAP-систем применяются схемы «звезда» и «снежинка». Они основаны на хранении декартова произведения всех справочников на плоскость реляционной таблицы. В такой структуре присутствует множество «шумовых» атрибутов, не вносившихся в БД. К примеру, для построения МБД на основе реляционной таблицы, содержащей записи, приведенные в таблице 7, строятся два справочника, приведенные в таблице 8:
Данная таблица на 2/3 состоит из несуществующих данных. При большом количестве справочников, доля «шумовых» данных может составлять более 90% от объема всей БД.
Указанные выше обстоятельства обуславливают актуальность применения в данной области предложенных моделей поиска по первичному ключу в качестве справочников МБД и модели поиска по вторичным ключам в качестве среды для хранения разреженных многомерных данных.
С целью экономии памяти и повышению скорости поиска в справочниках, автором предлагается использовать предложенные выше Вр-деревья в комбинации с собственным алгоритмом присваивания индексов атрибутам, основанным на применении хеш-функций.
Стандартным видомсправочника, используемым-в OLAP-системах-Oracle-и Microsoft, является таблица с двумя столбцами: атрибутом и индексом, как это показано ниже на таблице 10. Индекс является первичным ключом для данной таблицы.
Для оперативного доступа к данной таблице используются два В+-дерева, одно для прямого доступа по первичным ключам, второе, фактически, является инвертированным списком по таблице и обеспечивает быстрый поиск индексов по атрибутам.
В данном случае, каждой новой фамилии присваивается следующий порядковый номер по возрастанию. Однако простота данного метода приводит к тому, что атрибут «Фамилия» не связан никакой зависимостью с определяющим его индексом. Именно из-за этого приходится строить два В+-дерева.
Автор предлагает решить эту проблему заданием зависимости между атрибутом и его индексом. Реализация этой зависимости наиболее легко и естественно выражается в использовании идеи хеширования, т.е. вычислении хеш-функций для атрибутов (элементарным примером хеш-функции может служить остаток от деления атрибута на некоторое заранее заданное число). Однако, как известно из практики использования хеширования, невозможно подобрать такую хеш-функцию, которая выдавала бы несовпадающие хеш-ключи для всех возможных атрибутов, т.е. значения хеш-функции для двух разных атрибутов могут совпасть.
В качестве решения данных коллизий, автором предлагается использовать индекс, состоящий из двух частей - «префикса» и «суффикса». В первой части («префиксе») хранится хеш-ключ, который с высокой степенью вероятности уникален, а во второй («суффиксе») - номер записи в массиве атрибутов с данным хеш-ключом. К примеру, предположим, что на фамилии «Петров», «Иванов» и «Сидоров» хеш-функция выдает один и тот же хеш-ключ «1438402». В этом случае формируется следующий массив:
Оценка эффективности разработанного программного обеспечения на примере хранения биллинговой информации учета пользовательского трафика
В данных условиях, быстродействие В+-деревьев оказывается недостаточным. Кроме того, при вставке данных в; справочники значительное время отнимают операции перестроения самого В+-дерева: переливание индексов (атрибутов в случае прямого поиска) с уровня на уровень, расщепление вершин дерева и т.д.
Недостатки использования MOLAP-систем заключаются, в неэффективном использовании памяти (коэффициент избыточности может достигать 10-100) [19, 138]. Хотя при их сжатии (как правило, по zip-алгоритму) память используется почти также экономно, как и в РБД, но данный метод значительно замедляет работу МБД, в связи с необходимостью распаковки данных при любых операциях с ними. При использовании же ROLAP-систем применяются схемы «звезда» и «снежинка». Они основаны на хранении декартова произведения всех справочников на плоскость реляционной таблицы. В такой структуре присутствует множество «шумовых» атрибутов, не вносившихся в БД. К примеру, для построения МБД на основе реляционной таблицы, содержащей записи, приведенные в таблице 7, строятся два справочника, приведенные в таблице 8:
Данная таблица на 2/3 состоит из несуществующих данных. При большом количестве справочников, доля «шумовых» данных может составлять более 90% от объема всей БД.
Указанные выше обстоятельства обуславливают актуальность применения в данной области предложенных моделей поиска по первичному ключу в качестве справочников МБД и модели поиска по вторичным ключам в качестве среды для хранения разреженных многомерных данных.
С целью экономии памяти и повышению скорости поиска в справочниках, автором предлагается использовать предложенные выше Вр-деревья в комбинации с собственным алгоритмом присваивания индексов атрибутам, основанным на применении хеш-функций. Стандартным видомсправочника, используемым-в OLAP-системах-Oracle-и Microsoft, является таблица с двумя столбцами: атрибутом и индексом, как это показано ниже на таблице 10. Индекс является первичным ключом для данной таблицы. Таблица 10 Для оперативного доступа к данной таблице используются два В+-дерева, одно для прямого доступа по первичным ключам, второе, фактически, является инвертированным списком по таблице и обеспечивает быстрый поиск индексов по атрибутам. В данном случае, каждой новой фамилии присваивается следующий порядковый номер по возрастанию. Однако простота данного метода приводит к тому, что атрибут «Фамилия» не связан никакой зависимостью с определяющим его индексом. Именно из-за этого приходится строить два В+-дерева. Автор предлагает решить эту проблему заданием зависимости между атрибутом и его индексом. Реализация этой зависимости наиболее легко и естественно выражается в использовании идеи хеширования, т.е. вычислении хеш-функций для атрибутов (элементарным примером хеш-функции может служить остаток от деления атрибута на некоторое заранее заданное число). Однако, как известно из практики использования хеширования, невозможно подобрать такую хеш-функцию, которая выдавала бы несовпадающие хеш-ключи для всех возможных атрибутов, т.е. значения хеш-функции для двух разных атрибутов могут совпасть. В качестве решения данных коллизий, автором предлагается использовать индекс, состоящий из двух частей - «префикса» и «суффикса». В первой части («префиксе») хранится хеш-ключ, который с высокой степенью вероятности уникален, а во второй («суффиксе») - номер записи в массиве атрибутов с данным хеш-ключом. К примеру, предположим, что на фамилии «Петров», «Иванов» и «Сидоров» хеш-функция выдает один и тот же хеш-ключ «1438402». В этом случае формируется следующий массив: Результирующий индекс фамилии «Петров» в данном случае «143S402-I», «Иванов» - «1438402-2» и «Сидоров» - «1438402-3». Данный способ присваивания индексов делает возможным проведение двунаправленного поиска по единой структуре Вр-дерева, представляющей собой дерево поиска по «префиксам», хранимыми элементами которого (листьями) являются массивы с атрибутами и «суффиксами», так, как это показано на рис. 3.2. В данном случае при известном индексе поиск атрибута осуществляется следующим образом: по «префиксу» осуществляется поиск в дереве необходимого массива, который просматривается до нахождения нужного «суффикса». Атрибут, сопоставленный в массиве этому «суффиксу», и есть искомый.
Обратный поиск практически идентичен прямому: по атрибуту при помощи хеш-функции вычисляется хеш-ключ - «префикс». Далее происходит поиск по дереву «префиксов» нужного массива. Далее, в массиве просматриваются все атрибуты до нахождения искомого. Сопоставленный атрибуту «суффикс» и формирует окончательный индекс атрибута.
Однако в данном случае возникает опасность переполнения массива «суффиксов». Предположим, под «суффиксы» был отведен один байт, т.е. максимальное количество элементов в массиве равно 256. В.процессе работы системы, все 256 значений оказались заполнены, и потребовалось добавление 257-ого элемента. В данном случае следующий элемент добавляется в массив соседнего «префикса», если он не заполнен, а если заполнен, то в массив следующего «соседа». В целом же, возникновение такой ситуации говорит о неверном выборе размеров «префикса» и «суффикса» или неверном подборе хеш-функции.
Таким образом, предложенная модель индексации данных позволяет производить прямой и обратный поиск в единой структуре хранения индексов и атрибутов. Размеры «префикса», «суффикса» и вид хеш-функции, необходимые для однозначного формирования индекса, зависят от индексируемого атрибута. Применение же идеи открытой адресации легко позволяет разрешить ситуацию переполнения массива «суффиксов».
