Обобщенные деревья поиска: от теории к практике

Постановка задачи

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

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

Реализация

В качестве алгоритма для решения описанной задачи было предложено построение R-Tree дерева. Хорошее представление об алгоритмах, можно получить, познакомившись с такими структурами, как R-Tree, RD-Tree, KD-Tree (¹, ², ³, Wikipedia).

Обобщенное дерево поиска, Generalized Search Tree (GiST), обеспечивает унифицированный подход для реализации алгоритмов ⁴
(В частности, посредством GiST может быть реализовано R-Tree дерево.)

Для детального практического изучения индексирования, важно иметь свободную СУБД, с реализацией GiST. Также желательна хорошая расширяемость и документация. Примером такой СУБД может служить СУБД PostgreSQL, обладающая всеми перечисленными свойствами. PostgreSQL предоставляет семь интерфейсных функций, для работы со структурой GiST. Они, в свою очередь, манипулируют тремя базовыми методами дерева: search, insert, delete.

Пользователь может контролировать само построение дерева поиска
с помощью функций union и picksplit, отвечающих за объединение и разделение узлов дерева. Функцией penalty определяется метод оценки сложности вставки новых данных. Минимизация ``пенальти’’ является показателем эффективности индексации и учитывается при перестроении дерева.

Пользователь может контролировать поиск по дереву. Решение о переходе в один из дочерних узлов принимается с помощью функции consistent.

Реализация и примеры использования GiST в PostgreSQL подробно изложены в ⁵. Наряду с GIST, в PostgreSQL реализованы и другие обобщенные структуры, такие как SP-GIST (Space-Partitioned GIST). Техническая документация также является хорошим и легко читаемым источником информации ⁶.

Литература

¹ Гектор Гарсиа-Молина, Джеффри Ульман, Дженнифер Уидом, ``Системы Баз Данных’’, изд. ``Вильямс’’ 2002; в частности, гл.14 ``Многомерные и точечные индексы’’

² Antonin Guttman, ``R-Trees: A Dynamic Index Structure for Spatial Searching’’

³ Joseph M. Hellerstein, Avi Pfeffer, ``The RD-Tree: An Index Structure for Sets’’

⁴ Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer, ``Generalized Search Trees for Database Systems’’, In Proceedings of the 21st International Conference on Very Large Data Bases, Zurich, Switzerland, 1995.

⁵ Олег Бартунов, Федор Сигаев, ``Написание расширений для PostgreSQL с использованием GiST’’, http://citforum.ru/database/postgres/gist/

⁶ PostgreSQL Documentation, https://www.postgresql.org/docs/