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

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

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

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

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

Подробное описание дается в статье «Ускорение поиска в индексах на основе R-деревьев», автор Чернов А.Ф. (Вологодский государственный технический университет).