GiST и SP-GiST

B-tree упорядочивает ключи в одну линию. Для двумерных и интервальных данных линии нет: у прямоугольника или временно́го интервала нет естественного «меньше». Зато есть операции пересечения (&&), содержания (@>), расстояния (<->).

GiST (Generalized Search Tree) - дерево, узлы которого хранят не разделители-значения, а предикаты, описывающие всё поддерево: «здесь лежат объекты внутри такого прямоугольника» или «диапазоны внутри такого интервала». Спуск идёт по тем поддеревьям, чей предикат не противоречит запросу. Какой оператор поддержан, как всегда, решает operator class (см. operator-classes) - для GiST это &&, @>, <@, <-> и подобные.

Самый наглядный случай GiST - R-дерево для прямоугольников и диапазонов. Каждый внутренний узел хранит минимальный ограничивающий бокс (bounding box), покрывающий все его дочерние объекты.

[ bbox: весь регион ]

  ├── [ bbox: северо-запад ] → точки/боксы

  └── [ bbox: юго-восток ]   → точки/боксы

Поиск «что пересекается с X» спускается только в те узлы, чей бокс пересекается с X, отсекая остальные. Для диапазонов то же самое: узел хранит интервал, покрывающий дочерние интервалы, и запрос «пересекается с [a,b]» идёт лишь в подходящие ветви. Так GiST ускоряет geo-поиск и работу с range-типами.

GiST - каркас: чтобы он заработал на новом типе, автор типа реализует набор support-функций. Две из них определяют качество дерева:

• penalty - насколько «дорого» вставить объект в данное поддерево (как сильно придётся расширить его bounding box). Вставка идёт туда, где penalty минимальна, - чтобы боксы росли как можно меньше и меньше перекрывались.
• picksplit - как разделить переполненную страницу на две, чтобы получившиеся боксы были компактными и мало пересекались.

От качества этих функций зависит, насколько эффективно дерево отсекает ветви при поиске. Плохой picksplit даёт сильно перекрывающиеся боксы - и спуск вынужден заходить во многие ветви, теряя смысл индекса.

Одно из самых полезных применений GiST - запрет пересечений на уровне ограничения целостности. Обычный UNIQUE запрещает одинаковые значения; exclusion constraint запрещает пересекающиеся.

CREATE TABLE room_booking (

  room int,

  during tstzrange,

  EXCLUDE USING gist (room WITH =, during WITH &&)

);

Читается так: «не должно быть двух строк, где room одинаковый (=) И интервалы during пересекаются (&&)». Это декларативный запрет двойного бронирования одной комнаты - база сама не пустит пересекающуюся вставку. Под капотом ограничение опирается на GiST-индекс, потому что только он умеет оператор &&. Подробнее - в gist-spgist.

GiST может быть приблизительным (lossy): индекс по bounding box говорит «этот объект, возможно, подходит», но окончательно проверить должен сам кортеж. Поэтому в плане появляется Recheck Cond - повторная проверка условия на странице таблицы.

Это не баг, а природа пространственных индексов: bounding box огрубляет реальную геометрию (круг внутри прямоугольника), и точную принадлежность определяет recheck. Практическое следствие - GiST отсекает большинство непод­ходящих строк, но за финальной правдой всё равно идёт в таблицу, поэтому Index-Only Scan для него обычно невозможен.

SP-GiST (Space-Partitioned GiST) решает похожие задачи, но другим приёмом. Вместо перекрывающихся боксов он делит пространство на непересекающиеся, неравные части - как quadtree для точек или radix-дерево для строк.

Ключевое отличие от GiST: разбиения не пересекаются, поэтому при поиске спуск идёт ровно в одну ветвь на каждом шаге, без захода в соседние. Это выгодно для данных, у которых есть естественное непересекающееся разбиение: точки на плоскости (каждая в своём квадранте), IP-адреса, текст по префиксу.

CREATE INDEX ON places USING spgist (location);

CREATE INDEX ON hosts  USING spgist (addr inet_ops);

SP-GiST-деревья несбалансированные (глубина зависит от распределения данных), и это нормально для их задач. Выбор между GiST и SP-GiST - про природу данных: перекрываются ли объекты естественно (GiST) или делятся на непересекающиеся области (SP-GiST).

Короткая карта применений, чтобы не путать AM этой главы:

• геометрия, диапазоны, exclusion constraint, поиск ближайших (<->, KNN) - GiST;
• точки с естественным квадрантным делением, IP-сети, префиксы строк
  • SP-GiST;
• равенство и порядок - B-tree;
• содержание элементов в массивах/JSONB/полнотексте - GIN (следующая глава).

Оба, GiST и SP-GiST, lossy и требуют recheck, оба расширяемы через support-функции. Для большинства прикладных задач с диапазонами и геометрией стартовая точка - GiST; SP-GiST берут, когда данные явно просятся в непересекающееся разбиение.