GiST держит дерево бounding-boxes, которые могут перекрываться. Это компромисс: можно складывать любые объекты, но поиск иногда спускается в несколько веток. Для многих типов данных это нормально (range types, geo).

Но есть категория данных, где перекрытие — фундаментальная проблема:

• Иерархические строки: URL https://a.example.com/users/123 — естественно разбивается по префиксу. Если делать GiST с overlap, дерево будет деградировать.
• Точки в плоскости с фрактальным распределением: 90% точек в Москве, 10% размазаны по миру. Балансированное дерево не вырастет.
• Сети IP (inet, cidr): тоже префиксное.

Для них в Postgres есть

Главное отличие: непересекающееся разбиение

В SP-GiST каждое значение принадлежит ровно одному поддереву. Это значит:

• Дерево может быть несбалансированным.
• При поиске мы спускаемся по строго одной ветке, без ветвления.
• Узлы дерева могут иметь разный fanout (число детей): в зависимости от того, как тип данных решит разбить пространство в этой точке.

В GiST все эти слова попали бы в bounding boxes по символьному диапазону [a-z], перекрывающиеся в большой степени. В SP-GiST разбиение детерминировано: каждый символ — отдельная ветка.

Operator classes из коробки

PostgreSQL поставляет несколько SP-GiST opclass:

• text_ops — prefix tree для текста. Хорошо ищет LIKE 'foo%', text_pattern_ops.
• inet_ops — для IP-сетей (inet, cidr). Идеально подходит для WHERE ip <<= '10.0.0.0/8' (subnet contains).
• point_ops — quadtree для точек в плоскости. Альтернатива GiST point_ops.
• box_ops / range_ops — другие geometric и range типы.
• kd_point_ops — k-d tree для точек, обычно эффективнее quadtree при равномерном распределении.

Пример: префиксный поиск по строкам

На реалистично «префиксных» данных SP-GiST часто компактнее B-tree, потому что общий префикс хранится один раз, а в B-tree повторяется в каждом ключе (хотя deduplication в B-tree сильно сглаживает эту разницу с Postgres 13+).

Пример: IP-префиксы

Один из самых сильных кейсов SP-GiST — inet с inet_ops. Запросы вида «какая подсеть содержит этот IP» обслуживаются мгновенно.

Оператор >>= означает «содержит или равен». SP-GiST использует структуру CIDR (каждый бит — узел) и спускается строго к нужной ветке.

SP-GiST vs GiST: когда что

Практическое правило: если у тебя естественно префиксные или естественно иерархические данные (URL, путь к файлу, телефонный номер, CIDR) — SP-GiST скорее всего выиграет. Если данные равномерные и многомерные (координаты домов) — GiST.

Подводные камни

1. Глубина без баланса. В худшем случае (вырожденные данные — например, 10K строк, каждая длиной 1000 символов, отличающиеся последним байтом) SP-GiST trie вырастает в очень глубокое дерево. Поиск становится медленным, page reads растут. Обычно это решается префиксным сжатием внутри узла (Patricia trie вместо обычного trie), что SP-GiST для text_ops умеет.

2. Высокая стоимость split. При концентрированных вставках в одну ветку приходится часто перестраивать локальную часть дерева. Это написано в коде менее эффективно, чем split в B-tree.

3. Меньше распространён. У SP-GiST меньшее покрытие opclass, чем у B-tree или GiST. Если твой тип данных не имеет встроенного SP-GiST opclass — реализовать его руками возможно, но это серьёзная инженерная работа.

Quadtree для точек: альтернатива GiST point_ops

Для типа point доступны и gist_point_ops (GiST с R-tree-подобной структурой), и spgist_point_ops / spgist_kd_point_ops (SP-GiST quadtree / k-d tree). Какой выбрать?

• На равномерных данных (плотность ~постоянная по плоскости): GiST R-tree обычно выигрывает на 5-10% — bounding boxes складываются хорошо.
• На кластерных/фрактальных (90% точек в одной зоне): SP-GiST quadtree выигрывает существенно, потому что плотная зона раскладывается в глубокое поддерево, а пустые зоны не занимают ничего.
• На равномерных с KNN-запросом (find nearest 10 points): GiST поддерживает <-> оператор изначально, SP-GiST — да, но с Postgres 12+; проверь версию.

Пишем свой opclass: что внутри

Если у тебя есть кастомный тип данных (например, телефонный номер с иерархией код страны / код города / номер) и хочется индекса — SP-GiST даёт пять callback-функций:

1. config — параметры (тип ключа узла, тип листа).
2. choose — куда добавить новое значение при insert (в какое поддерево, нужно ли split-нуть узел).
3. picksplit — как разделить переполненный узел: какие значения куда.
4. inner_consistent — при поиске, в какие дочерние узлы спускаться.
5. leaf_consistent — проверка финального совпадения на листе.

Это меньше, чем у GiST (там 7 callbacks), и более «декларативно». Если ты пишешь расширение и думаешь про индекс — SP-GiST часто проще.

Multi-column через SP-GiST

Из коробки SP-GiST не поддерживает multi-column ключи — это известное ограничение. Workaround: сделай expression index на конкатенацию или составить кастомный тип. Альтернатива — построить два отдельных индекса и положиться на bitmap AND в EXPLAIN, что в большинстве случаев достаточно эффективно.

-- Не работает напрямую:
-- CREATE INDEX ON urls USING SPGIST (domain, path);

-- Workaround: expression
CREATE INDEX urls_combined_spgist
  ON urls USING SPGIST ((domain || '|' || path));

Краткий путеводитель: какой индекс выбрать

Эта таблица — приближение. В реальной системе нужно смотреть EXPLAIN ANALYZE на конкретной нагрузке.

Чек-лист

• SP-GiST — фреймворк для индексов с неперекрывающимся пространственным разбиением.
• Дерево может быть несбалансированным — отлично для данных с естественной иерархией.
• Встроенные opclass: text_ops (trie), inet_ops (CIDR), point_ops (quadtree), kd_point_ops (k-d tree), range_ops, box_ops.
• Хорош для: URL/префиксного поиска, IP-сетей, фрактальных точек, телефонных номеров.
• Плох для: данных без иерархической структуры, multi-column ключей, высокого concurrent insert.
• GiST vs SP-GiST: GiST разрешает overlap (универсальнее, но иногда медленнее на поиске), SP-GiST — нет (специализированнее, быстрее на подходящих данных).
• Тип данных может реализовать свой opclass — пишутся 5 callback-функций.