Программные продукты и системы

Индексные методы доступа к данным прошли большой путь развития и совершенствования. Существует множество подходов к построению поисковых индексов, таких как использование битовых карт, структур B-деревьев, B+-деревьев, R-деревьев и др. Подходы объединяет метод доступа к БД, а именно: дополнительно строятся специальные структуры данных, использование которых ускоряет поиск. Однако ни один индексный метод доступа к данным не является универсальным: для различных, особенно сложных и специфических, типов данных необходимо выбирать или даже реализовывать новые методы быстрого доступа – этим и обусловлена актуальность проблемы.

В настоящее время уже существуют обобщенные методы доступа к данным различных типов. Как правило, они базируются на аппарате R-де­ревьев, обладающем наибольшей гибкостью. Например, структура GIST-индекса, предложенная Джозефом Хеллерстейном, используется в СУБД PostgreSQL (открытая СУБД с большой функциональностью и возможностями расширения).

При постоянно увеличивающихся в размере БД возрастает и нагрузка на методы доступа к данным. Таким образом, индексный метод доступа должен обладать не только универсальностью, но и высокой эффективностью, удовлетворяющей современным требованиям. На повышение производительности обобщенного метода доступа на основе R-деревьев и направлена предложенная автором модернизация. Индексы на основе R-деревьев применяются для специфических, сложных типов данных, таких как пространственные объекты (например географические), биометрические (отпечаток пальца и др.), массивы (в том числе строки как массивы символов). Для индексации линейных данных (числа, символы, даты и т.д.), как правило, используются B-деревья, то есть R-деревья успешно применяются для данных, которые нельзя отсортировать вдоль одной оси [1]. Для индексирования таких типов данных необходимо в качестве поискового ключа использовать вспомогательную информацию.

Подобно B-деревьям R-дерево представляет собой ветвистую сбалансированную древовидную структуру, но с разной организацией внутренних и листовых страниц. В листовых узлах R-деревьев хранятся указатели на индексируемые объекты, а во внутренних – дополнительная информация об объектах [2]. Эту дополнительную информацию далее будем называть сигнатурой.

В данной работе описывается модернизация сигнатур на примере индексирования текстовых данных. Пример R-дерева для индексации текстовых данных приведен на рисунке 1.

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

Особенность построенных таким образом индексов на основе R-деревьев в том, что поиск по дереву может приводить к ложным попаданиям, так называемым FalseDrop. Это обусловлено тем, что информация об индексируемых объектах, хранящаяся в сигнатурах, не является исчерпывающей. Так, в рассмотренном примере в сигнатурах хранится информация только о наличии отдельных символов в индексируемом объекте, но не учитываются ни порядок их расположения, ни их количество. Поэтому найденные по индексу объекты необходимо сравнивать с оригиналом, прочитанным из БД, отсеивая ложные попадания. Для этого требуются дополнительные чтения страниц БД, что на больших объемах данных значительно замедляет работу [3].

Таким образом, для увеличения производительности поиска по индексу на основе R-дерева за счет уменьшения количества ложных попаданий необходимо хранить в сигнатуре информацию о количестве и порядке расположения символов в объекте. Модернизацию сигнатур R-дерева выполним в два этапа, а именно путем добавления в сигнатуры информации о количестве символов в объекте и о порядке их расположения в объекте (нахождение символов на границе слов).

Этап 1. Добавление в сигнатуры информации о количестве символов в объекте. При этом для каждого уникального символа текстового фрагмента в сигнатурах будет храниться информация о количестве таких символов, а не признак наличия. Физически это будет представлять собой байт информации (структура данных сигнатуры каждого уникального символа индексируемого объекта изображена на рис. 2). То есть максимально учитываемое количество одинаковых символов в объекте будет равно 28=256, что для текстовых фрагментов среднего размера вполне достаточно.

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

Таблица 1

Пример R-дерева для индексации текстовых данных из таблицы 1 приведен на рисунке 3.

Производительность при такой модификации увеличивается при поиске объектов, содержащих несколько одинаковых символов (например, «ссуда» или «мама»). Причина ускорения в том, что при проходе по дереву во время поиска отбрасываются поддеревья, в сигнатурах которых количество какого-либо уникального символа меньше, чем в объекте текущего поиска.

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

Наиболее успешно такое решение реализуется для данных, представляющих собой наборы элементов (массивы, строки как массивы символов и т.п.).

Проверка эффективности этого решения проводилась на программе, эмулирующей работу СУБД PostgreSQL в плане использования индексов на основе R-деревьев. Программа написана с достаточно точной аналогией, включая внутреннюю структуру R-дерева, интерфейсные функции для работы с деревом и постраничное обращение к БД.

Текстовые данные в БД были сгенерированы со следующими параметрами: хранимые объекты – текстовые строки, размер объектов – от 1 до 40, элементы строк – случайные символы (154 различных символа с учетом регистра). Тестирование выполнялось на трех наполнениях БД: 10 тысяч записей, 100 тысяч записей и 1 миллион записей.

На сгенерированной БД выполнялся поиск строк «свет», «ссуда» и «мама» с использованием индекса на основе R-деревьев. Результаты проверки эффективности приведены в таблице 2.

Этап 2. Добавление в сигнатуры информации о нахождении символов на границе слов. Для этого используем разбиение индексируемого объекта на части и хранение в сигнатурах информации о границах данных частей. Такие части индексируемых объектов назовем фреймами. В случае с текстовыми данными в качестве фреймов, естественно, удобно использовать слова. Технически добавим в сигнатуры по 1 биту информации для каждого уникального символа как признак того, что данный символ в текстовом фрагменте хотя бы раз находился на границе фрейма. Данным флагом будем пользоваться при поиске по дереву. В результате структура данных сигнатуры для каждого уникального символа примет вид, изображенный на рисунке 4.

Как видно из рисунка, бит граничного символа берется из того же байта, где хранится количество символов. Таким образом, максимально учитываемое количество одинаковых символов уменьшится до 27=128. Этого достаточно для текстовых фрагментов среднего размера. При превышении данного количества одинаковых символов ничего страшного не произойдет, оно все равно будет интерпретироваться как 128, что не сделает производительность эффективнее.

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

Таблица 3

Пример R-дерева для индексации текстовых данных из таблицы 3 приведен на рисунке 5.

Производительность поиска после добавления признака граничного символа в сигнатуры увеличивается, когда ищутся объекты, состоящие из нескольких слов (например «в лес»). Причина ускорения в том, что при проходе по дереву во время поиска отбрасываются поддеревья, сигнатуры которых, хотя и содержат все символы из искомой фразы, но удовлетворяют следующему условию: хотя бы один из символов сигнатуры поддерева не является граничным, в то время как этот же символ в сигнатуре искомой фразы граничным является.

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

Наиболее успешно это решение реализуется для данных, представляющих собой наборы элементов (массивы, строки как массивы символов и т.п.). Однако признак граничного элемента можно успешно применять для индексирования, например, пространственных данных.

Проверка эффективности данного решения производилась аналогично этапу 1, но выполнялся поиск строки «в лес». Результаты проверки эффективности приведены в таблице 2.

Проверка производительности показала увеличение скорости поиска после реализации каждого из этапов модернизации.

1. После реализации этапа 1 существенно увеличилась скорость поиска слов с несколькими одинаковыми символами:

–      поиск слова «ссуда» на миллионе записей ускорился более чем в 2 раза;

–      производительность поиска слова «мама» увеличилась более чем на порядок.

2. После реализации этапа 2 существенно увеличилась скорость поиска текстовых фрагментов, состоящих из нескольких слов:

–      поиск фразы «в лес» на миллионе записей ускорился в 3 раза.

Кроме того, из полученных замеров производительности видно, что положительный эффект от модернизации при поиске по индексу на основе R-деревьев растет с увеличением количества записей в БД. Это является достоинством выполненной доработки, учитывая постоянно увеличивающийся объем современных БД.

Следует отметить, что наблюдается некоторое снижение производительности при поиске строк, не затронутых изменениями в индексе. То есть строк, состоящих из одного слова, в которых каждый символ фигурирует только один раз (среди протестированных – слово «свет»). Это объясняется выполнением дополнительных проверок при проходе по дереву индекса во время поиска. Однако данный негативный эффект снижается при увеличении количества записей в БД и на миллионе записей составляет всего 4 %, что свидетельствует об увеличении общего времени поиска.

Выполненная модернизация сигнатур R-де­ревьев станет эффективной не только для текстовых данных, но и для

–      числовых массивов (реализация будет практически неизменна, так как массивы, как и строки, представляют собой набор элементов);

–      пространственных данных (точки, линии, полигоны и т.д.). Для таких данных можно аналогично использовать признак граничного символа в сигнатурах R-деревьев. Объектами-разделителями будут выбраны те, которые удобно использовать в этом качестве (например, имеющие максимальное количество соседних объектов). Граничными при этом будут объекты, находящиеся на определенном расстоянии от объектов-разделителей. Данное расстояние зависит от плотности расположения объектов на индексируемой карте: чем плотнее расположены объекты, тем меньше используемое расстояние. Таким образом, при достаточно плотной карте с большим количеством объектов (например, карте мегаполиса) использование признака граничного символа будет давать эффект, как и при его использовании в текстовых данных и массивах.

В дальнейшем планируется оптимизировать использование информации о границах фрейма при поиске по индексу, основанному на R-де­ревьях (этап 2), и реализовать динамический список разделителей фреймов, а не только статический, как было сделано выше. Разделителем сможет стать любой символ, который удобно использовать для конкретного текущего наполнения БД. Обновлять информацию о разделителях планируется периодически, запуская анализ БД. К примеру, в СУБД PostgreSQL для таких целей существует специальная команда VACUUM ANALYZE, периодически выполняемая администратором БД. При этом ожидается повышение производительности поиска в результате увеличения вероятности нахождения в искомой фразе граничных символов, что является результатом грамотного выбора разделителей при анализе наполнения БД. Для этого необходимо сформулировать критерии выбора символа в качестве разделителя. Таким образом, в результате такой модификации возрастет универсальность использования информации о границах фреймов.

На данном этапе можно выделить единственный критерий выбора символа в качестве разделителя – количество порожденных граничных символов, если бы разделителем был только данный символ. Алгоритм формирования динамического списка разделителей для конкретного наполнения БД представляется следующим:

–      рассчитывается числовое значение данного критерия для каждого уникального символа, встречающегося в индексируемом тексте;

–      символы сортируются по убыванию данного значения;

–      в динамический список разделителей из вершины списка отбирается такое количество символов, при котором общее количество граничных символов в индексируемом тексте будет максимальным; наличие максимума обязательно и объясняется тем, что сами символы-разделители граничными не являются.

Таким образом, построенный по данному алгоритму набор символов-разделителей для конкретного содержимого БД станет оптимальным и даст максимальный эффект, так как вероятность нахождения граничных символов в искомой фразе будет максимальной. В целом данный алгоритм необходимо тщательно проанализировать и проверить на индексировании различных реальных данных, чтобы убедиться в его универсальности.

Кроме того, данную модернизацию индексов на основе R-деревьев планируется выполнить c использованием реальной СУБД – PostgreSQL, поскольку у нее открытая лицензия (BSD), внедрено использование индексов на основе R-де­ревьев с большими возможностями для расширений (база для модернизации), существует удобный интерфейс API для программ на C/C++ (будет использоваться для наполнения БД).

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

Следует отметить, что описанная в данной работе модернизация индексов на основе R-деревьев оправдала ожидания специалистов.

Литература

1. Руководство пользователя PostGIS. URL: http://post­gresql. ru.net/postgis/index.html (дата обращения: 10.02.2011).

2. Методы сортировки и поиска: обзор методов поиска на основе деревьев. URL: http://megalib.com/books/134/index2.htm (дата обращения: 18.08.2009).

3. Бартунов О.С., Сигаев Ф.Г. Специализированные типы данных для цифровых библиотек / Электронные библиотеки: перспективные методы и технологии, электронные коллекции: матер. Всеросс. науч. конф. Переславль-Залесский, 2007.