# GiST и SP-GiST

_Индексы · PostgreSQL Knowledge Base_

**TL;DR:** GiST - каркас деревьев для пересечений, содержания и расстояний (&&, @>,
<->): геометрия, диапазоны, exclusion constraint. SP-GiST делит
пространство на непересекающиеся части (точки, IP, префиксы). Оба lossy.


Для данных без линейного порядка (прямоугольники, интервалы) B-tree не
годится - нужны деревья с предикатами.

## GiST

Обобщённое дерево поиска: узлы хранят предикат, покрывающий поддерево
(например, bounding box у R-дерева). Поиск спускается только в ветви,
чей предикат не противоречит запросу. Поддерживает `&&` (пересечение),
`@>` (содержит), `<->` (расстояние, KNN). Качество дерева задают
support-функции penalty (куда вставлять) и picksplit (как делить).

## Exclusion constraint

```sql
CREATE TABLE room_booking (
  room int,
  during tstzrange,
  EXCLUDE USING gist (room WITH =, during WITH &&)
);
```

Запрещает пересекающиеся брони одной комнаты - декларативный запрет
двойного бронирования, опирается на GiST.

## SP-GiST

Делит пространство на непересекающиеся части (quadtree для точек,
radix-дерево для строк): спуск идёт в одну ветвь. Выгодно для точек,
IP-сетей, префиксов строк. Деревья несбалансированные.

## Lossy

Оба обычно lossy: индекс отбирает кандидатов по огрублённому описанию, а
точное условие перепроверяется (Recheck Cond), поэтому Index-Only Scan
недоступен. Какой оператор какой AM знает - в [operator-classes](/courses/postgres/kb/operator-classes.md).
Инвертированный поиск по элементам - в [gin-index](/courses/postgres/kb/gin-index.md).


## Команды

```sql
CREATE INDEX ON t USING gist (range_col);
```
GiST по диапазону - для пересечений && и содержания

```sql
CREATE INDEX ON t USING spgist (point_col);
```
SP-GiST для точек/IP/префиксов (непересекающееся разбиение)


## См. также

- [Operator classes и выбор индекса](/courses/postgres/kb/operator-classes.md)
- [GIN: инвертированный индекс](/courses/postgres/kb/gin-index.md)
- [Проектирование индексов](/courses/postgres/kb/index-design.md)