Тезисы

При построении современных информационных систем приходится решать разнообразные технологические задачи, связанные с хранением, доступом и поиском информации. Учитывая современные требования к производительности, надежности и шкалированию таких систем, такие задачи требуют использования достаточно сложных алгоритмов и специализированных структур данных (abstract data type, ADT).

Эффективный доступ к данным является одной из важнейшей задачей базы данных. Мы рассматриваем большие базы данных, которые не помещаются в оперативную память. Для таких БД эффективность доступа к данным определяется, в основном, количеством обращений к диску, поэтому основной задачей СУБД является минимизация этих обращений. Обычно, это достигается использованием индекса, который представляет собой вспомогательную структуру данных, предназначенную для ускорения получения данных удовлетворяющих определенным поисковым критериям. Индекс позволяет уменьшить количество дисковых операций необходимых для считывания данных с диска. Обычно, индекс представляет собой файл на диске, и, если этот файл становится очень большим, то может потребоваться дополнительный индекс для ускорения работы самого индекса. Методами доступа (access methods,AM), обычно, называют организацию (структуру) индексного файла и методы работы с ней. В традиционных реляционных СУБД для работы с одномерными данными, такими как строки, цифры, используются B+-tree и хэш, для которых разработаны очень эффективные алгоритмы работы. Однако, современные приложения, такие как ГИС (GIS), мультимедийные системы, CAD, цифровые библиотеки, которые по-сути используют многомерные данные, требуют других, более эффективных AM.

Для эффективной работы с такими многомерными данными PostgreSQL предлагает два типа индекса: GiST (Generalized Search Tree) и GIN (Generalized Inverted Index).

GiST был предложен Hellerstein et al. [HNP95] как обобщение нескольких классов индексов (такие как B-Tree, R-Tree, Similarity Tree, RD-Tree) и позволяет создавать индексы на базе произвольной метрики типа данных. Для использования GiST разработчик должен создать метрику и функции-адаптеры, используя API. Как классический индекс, в котором храниться одна и только одна пара ключ-ссылка, индексы GiST имеют хорошею производительность при вставке нового ключа, но производительность при поиске может сильно зависеть от метрики проиндексированного типа данных и собственно типа поискового запроса.

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

В докладе представлены сравнение производительности и потребного дискового пространства для GIN и GiST индексов на примере полнотекстового поиска с использованием модуля раширения tsearch2, а также практические советы по их использованию в высоконагруженных приложениях.