B-tree держится на линейном порядке: для любых двух ключей либо a < b, либо a > b, либо a = b. Это работает для чисел, строк, дат. Но что делать с многомерными или интервальными данными?

• Прямоугольники на карте — не упорядочить линейно.
• Диапазоны [10, 20] и [15, 25] — пересекаются, но ни один не «меньше» другого.
• tsvector с десятками лексем — тоже нет линейного порядка.

PostgreSQL отвечает на это

Дерево с произвольной геометрией ключей

В B-tree узел хранит ключи и разделители «всё что слева ≤ X, всё что справа > X». В GiST узел хранит bounding values — обобщённые «оболочки», покрывающие всё, что лежит в поддереве.

Важное отличие от B-tree: bounding boxes могут перекрываться. Когда мы идём по дереву и запрос пересекается с двумя детьми — мы спускаемся в оба. Это значит, что GiST в худшем случае может сканировать всё дерево; от качества split-стратегии зависит, насколько часто это случается.

Range types: основной use case

Range type — это пара [lo, hi] с булевым флагом «включительно/нет». PostgreSQL умеет int4range, tstzrange, daterange, numrange и т.д. На них работают операторы && (overlaps), <@ (contained), @> (contains), -|- (adjacent). B-tree их не индексирует — нужен GiST.

GiST превращает «найти все бронирования, пересекающиеся с этим окном» из O(N) в O(log N + результат). Это типичный сценарий — резервирование, билеты, расписания.

Exclusion constraints — секретное оружие GiST

GiST позволяет писать EXCLUDE USING gist — констрейнт, гарантирующий, что нет двух строк, у которых одновременно room_id = room_id AND period && period. Это значит: невозможно забронировать один и тот же номер на пересекающееся время. На уровне БД, атомарно, без триггеров и racing-condition.

Чтобы это работало, для = оператора по int (room_id) тоже нужно дерево GiST. По умолчанию int индексируется только B-tree — поэтому ставим расширение btree_gist, которое добавляет GiST-opclass для всех B-tree-типов.

CREATE EXTENSION btree_gist;

ALTER TABLE reservations
ADD CONSTRAINT no_overlap
EXCLUDE USING GIST (
  room_id WITH =,
  period  WITH &&
);

После этого INSERT INTO reservations VALUES (..., 5, tstzrange('2024-06-15 10:00', '2024-06-15 14:00'), ...) упадёт, если уже есть бронирование комнаты 5 на любое пересекающееся окно. В песочнице btree_gist обычно недоступен (pglite не содержит расширений), но в реальном Postgres это рабочая практика.

Geo: PostGIS

PostGIS превращает Postgres в полноценную географическую БД. Тип geometry (плоскость) и geography (сфера WGS84) индексируются через GiST. Базовая идея та же: bounding box каждого объекта (или MBR — minimum bounding rectangle) хранится в дереве. Поиск «всё в радиусе 10 км от точки» становится:

1. Найти MBR радиуса 10 км.
2. По GiST найти кандидатов с пересекающимся MBR (приближение, может включать ложноположительные).
3. Точно посчитать расстояние для кандидатов.

Это двухэтапная фильтрация — типичная для GiST: index narrowing + recheck. Поэтому Index Recheck в EXPLAIN — нормальное явление.

В песочнице PostGIS нет, но можно поиграть с встроенными point и оператором <-> (расстояние KNN):

<-> поддерживается GiST как KNN-индекс: возвращает в правильном порядке, не сортируя весь результат. Это уникальная фишка GiST — B-tree так не умеет.

Полнотекстовый поиск: GIN или GiST

PostgreSQL поставляет два типа индексов для tsvector: GIN и GiST. У них симметричный trade-off:

• GIN для tsvector хранит каждую лексему -> posting list. Чтение в 3-5 раз быстрее, чем GiST. Запись и обновление в 3-10 раз медленнее.
• GiST для tsvector хранит signature bloom-filter каждого документа — фиксированной длины. False positives есть, нужен recheck. Зато insert обходится одной записью в дерево.

Правило для FTS:

• 80%+ нагрузки — поиск, документы редко меняются: GIN.
• Документы пишутся потоком, поиск редок: GiST.
• Сомневаешься: пробуй GIN, мониторь pg_stat_statements; если INSERT в wait_event_type = LWLock — переключайся на GiST.

Сравнение размеров на одной колонке

GiST на range обычно весит 5-10% от heap-таблицы — это в разы меньше B-tree на скалярах и в разы меньше GIN на эквивалентном tsvector.

Когда выбрать GiST

• range types — единственный реалистичный выбор, B-tree их не индексирует на overlap.
• geo — стандарт через PostGIS.
• full-text search — tsvector поддерживает оба, GIN и GiST. GIN быстрее на чтение, GiST быстрее на write — выбирай по нагрузке.
• exclusion constraints — атомарные «не пересекаться» правила.

Цена: GiST обычно медленнее GIN на чтение примерно в 3 раза, потому что bounding-box overlap менее точный, чем точное совпадение токена. Зато GiST дёшев на insert и поддерживает KNN.

Мониторинг GiST

Главный метрик — height (глубина) и bloat. Слишком глубокое дерево означает плохой picksplit (тип данных плохо разбивается); большой bloat — много мёртвых tid после VACUUM не очищены полностью.

SELECT * FROM gist_page_opaque_info(get_raw_page('reservations_period_gist', 0));

Если поиск часто проходит через все верхние уровни (Index Scan показывает много buffer reads на index pages) — стоит проверить, не время ли REINDEX’нуть. GiST хуже справляется с фрагментацией, чем B-tree, и REINDEX иногда сжимает индекс в 2-3 раза.

Расширения, которые превращают GiST в супер-инструмент

• PostGIS — geo, географические объекты, KNN, spatial joins. Стандарт в индустрии.
• btree_gist — добавляет GiST-opclass для скалярных типов; нужен для exclusion constraints.
• intarray — GiST-индекс для массивов int с операторами &&, @>, <@.
• cube — multi-dimensional points (до 100 измерений), полезно для feature-vector search и приближённого ANN.
• pg_trgm — GiST по триграммам (альтернатива GIN-варианту); медленнее на чтение, быстрее на write.
• pgvector — <->/<#>/<=> дистанции на embedding-векторах; поддерживает GiST IVFFlat-вариант для ANN search.

Это не обязательные для понимания самого GiST, но они показывают, насколько фреймворк гибкий — один и тот же index access method обслуживает географию, текст, embeddings, intarray.

Чек-лист

• GiST — фреймворк, не индекс. Тип данных сам определяет, как делить пространство (callbacks consistent, picksplit, union, …).
• Bounding values могут перекрываться — поиск может спускаться в несколько веток.
• Главные use cases: range types (&&, @>), geo (PostGIS), tsvector (FTS).
• btree_gist расширение даёт GiST-opclass для скаляров — нужно для exclusion constraints.
• GiST поддерживает KNN через <-> оператор — single-pass, не нужно сортировать весь результат.
• Trade-off с GIN: GIN быстрее на чтение, GiST быстрее на write и умеет KNN.