МНОГОМЕРНЫЕ ИНДЕКСЫ В СОВРЕМЕННЫХ СУБД

Фролов К.М.¹, Князев В.Н.²

¹ Магистр,  ² кандидат технических наук, доцент, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Пензенский государственный университет»

МНОГОМЕРНЫЕ ИНДЕКСЫ В СОВРЕМЕННЫХ СУБД

Аннотация

В статье рассмотрены вопросы оптимизации запросов к многомерным данным. Также приведены виды многомерных индексов и рассмотрены современные системы управления базами данных (СУБД), в которых они применяются.

Ключевые слова: индекс, R-дерево, пространственная сетка.

Frolow K.M.¹, Knyazev V.N.²

¹ Master, ² PhD in Engineering, associate professor;  

The Federal State Educational Government-Financed Institution of Higher Professional Education "Penza State University"

MULTIDIMENSIONAL INDEXES IN MODERN DBMS

Abstract

In the article the questions of optimization of queries to multidimensional data are considered. Also the article shows the types of multidimensional indexes and describes the modern database management system (DBMS) to which they apply.

Keywords: index, R-tree, spatial grid

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

В современных СУБД чаще всего применяются 2 вида индексов:

• пространственная сетка;
• R-дерево.

Пространственная сетка представляет собой аналог В-дерева, применимый к многомерным данным. Узлами дерева в таком случае являются ячейки пространства. Таким образом, каждый следующий уровень пространственной сетки представляет собой уточнение пространства, охватываемого текущим уровнем. При этом пространственная сетка способна разбиваться либо до полного покрытия всего множества значений, либо по достижении установленной максимальной глубины вложенности.[1]

R-деревья используются практически во всех современных СУБД. Такая популярность этого типа пространственных индексов обусловлена широким кругом задач, которые решаются с их помощью. R-деревья перенимают много положительных качеств в применении к многомерным данным от В-деревьев. В качестве корневой вершины R-дерева используется описание n-мерной области. Все промежуточные вершины являются подобластями корневой вершины. На листовом уровне находятся уже непосредственно объекты, которые принадлежат выделенным подобластям.[2]

Для исследования применимости пространственных индексов в современных СУБД рассмотрим коммерческий продукт Microsoft SQL Server и Open Source проект PostgreSQL. В PostgreSQL пространственные индексы традиционно используются для полнотекстового поиска. Полнотекстовый индекс GiST имеет в своей основе R-дерево с линейным разбиением. Алгоритм линейного разбиения предполагает прохождение следующих шагов:

• вычисление разницы между максимальной нижней и минимальной верхней границей прямоугольника по данной координате;
• нормализация полученного значения;
• поиск максимума среди нормализованных значений всех координат;
• нахождение всех вершин, которым соответствует полученное максимальное значение, удаление их и корректировка границы прямоугольной области.[3]

Также в СУБД PostgreSQL реализованы индексы, основанные на битовых картах. Однако этот тип индексов применяется в данной СУБД исключительно для хеширования системных данных.

В Microsoft SQL Server также используются R-деревья. Однако в данной СУБД R-деревья реализованы в варианте с квадратичным разбиением и в основном применяются для хранения геолокационных данных. В отличие от алгоритма линейного разбиения квадратичное разбиение узлов предполагает дополнительную оптимизацию пространства всего дерева, производя параллельную кластеризацию значений. [1]

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

На основе проведенного анализа возможностей оптимизации  запросов современных СУБД в отношении многомерных данных  в настоящее время проводится  работа по учету и использованию полученной информации  в разработке СУБД специального назначения с целью повышения производительности данной СУБД.

Литература

1. Вийера, Р. Программирование баз данных Microsoft SQL Server 2005: базовый курс / Роберт Вийера; пер. с англ.– М. : Издательский дом «Вильямс», 2010.
2. Гарсия-Молина, Г., Ульман, Д. Д., Уидом, Д. Системы баз данных : Полный курс/ Гектор Гарсия-Молина, Джефри Д. Ульман, Дженифер Уидом ; пер. с англ. – М. : Издательский дом «Вильямс», 2012.
3. Ахо, А.В., Хопкрофт, Д., Ульман, Д.Д. Структуры данных и алгоритмы/Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман ; пер. с англ. – М. : Издательский дом «Вильямс», 2013.

References

1. Vieira, R. Programming databases Microsoft SQL Server 2005: basic course / Robert Vieira ; translated from English – M. : Publishing house "Williams", 2010.
2. Garcia-Molina, H., Ullman, J. D., Widom, J. database Systems : the Complete course/ Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom ; translated from English – M. : Publishing house "Williams", 2012.
3. Aho, A.V., Hopcroft, J., Ullman, J. D. data Structures and algorithms/Alfred V. Aho, John Hopcroft, Jeffrey D. Ullman, translated from English. – M. : Publishing house "Williams", 2013.