GiST

GiST (англ. Generalized Search Tree, Обобщенное поисковое дерево) — структура индекса, которая является обобщенной разновидностью R-tree и предоставляет стандартные методы навигации по дереву и его обновления (расщепление и удаление узлов). GiST представляет собой сбалансированное (по высоте) дерево, концевые узлы (листья) которого содержат пары (key, rid), где key — ключ, а rid — указатель на соответствующую запись на странице данных. Внутренние узлы содержат пары (p, ptr), где p — это некий предикат (используется как поисковый ключ), выполняющийся для *всех* наследных узлов, а ptr — указатель на другой узел в дереве. Для этого дерева определены базовые методы SEARCH, INSERT, DELETE, и интерфейс для написания пользовательских методов, которыми можно управлять работой этих (базовых) методов.

Метод SEARCH управляется функцией Consistent, возвращающая 'true', если узел удовлетворяет предикату, метод INSERT — функциями penalty, picksplit и union, которые позволяют оценить сложность операции вставки в узел, разделить узел при переполнении и перестроить дерево при необходимости, метод DELETE находит лист дерева, содержащий ключ, удаляет пару (key, rid) и, если нужно, с помощью функции union перестраивает родительские узлы.

GiST является прямым индексом, используемым полнотекстовым поиском СУБД PostgreSQL. Это означает, что для каждого вектора tsvector, описывающего все лексемы документа, создаётся сигнатура, описывающая, какие из лексем входят в данный tsvector. Принцип работы схож с битовыми индексами, однако есть и различия.

Продемонстрируем на примере: пусть лексеме w1 сопоставлена сигнатура 001000, лексеме w2 — 000010. Тогда документу, содержащему только лексемы w1 и w2, будет сопоставлена сигнатура 001010 (001000 | 000010). В отличие от битовых индексов, отображение лексем в сигнатуры не однозначно, то есть возможно существование лексемы w3 с сигнатурой 001000. Это позволяет значительно экономить на размере индекса, но требует вторичной проверки на полное совпадение лексем запроса и документа.

Стоит также обратить внимание, что в случае, если лексема запроса имеет сигнатуру, к примеру, 000001, то документ с сигнатурой 001010 однозначно её не содержит, несмотря на неоднозначность отображения лексем.

Преимущество GiST в его скорости создания и размере индекса в сравнении с GiN (в 3 раза), потому он предпочтительнее для динамически постоянно обновляемых данных. Для статических данных или которые редко обновляются предпочтительнее GiN индекс (он в 3 раза быстрее производит поиск).

Источники

1. Введение в полнотекстовый поиск в PostgreSQL  (неопр.). Дата обращения: 23 мая 2010. Архивировано из оригинала 19 июня 2012 года.
2. Написание расширений для PostgreSQL с использованием GiST  (неопр.).