SP-GiST — индекс для разбиения пространства

Предпосылки: B-tree (порядок и range scan), GiST (bounding boxes, пересечения регионов, recheck), базовая идея дерева.

← BRIN | Планировщик запросов →

B-tree хранит ключи в отсортированном порядке — оптимально, когда данные ложатся на одномерную ось. GiST группирует данные в охватывающие регионы (bounding boxes) — подходит для геометрии и диапазонов, но bounding boxes сиблингов могут пересекаться, вынуждая поиск спускаться по нескольким веткам одновременно. Есть, однако, данные, которые естественно разбиваются на непересекающиеся части: строка начинается с «a» или с «b», но не с обоих; точка лежит в северо-западном или юго-восточном квадранте, но не в двух сразу. Для таких данных перекрытия GiST — лишняя работа. SP-GiST (Space-Partitioned Generalized Search Tree) строит деревья разбиений, в которых каждый шаг гарантированно сужает область поиска ровно в одну ветку.

Разберём это на двух задачах: префиксный поиск по доменным именам (50 млн строк) и поиск точек в прямоугольнике (10 млн координат ресторанов).

Trie: дерево префиксов

Первый сценарий — DNS-реестр. Таблица dns_records с 50 млн строк, колонка domain TEXT. Типичный запрос: найти все поддомены example.com — WHERE domain <@ 'example.com', или все домены по префиксу — WHERE domain LIKE 'api.example%'.

B-tree может ускорить prefix LIKE, но он хранит полные ключи в отсортированном порядке и сканирует диапазон. Для данных с иерархической структурой префиксов (домены, пути файлов, IP-адреса) существует более естественное дерево — trie.

Trie (от retrieval) — дерево, в котором каждое ребро помечено одним символом, а путь от корня до узла образует префикс. Пусть в таблице есть домены api.ex.com, app.ex.com, auth.ex.com и blog.other.org:

root
 ├─ a
 │   ├─ p
 │   │   ├─ i.ex.com
 │   │   └─ p.ex.com
 │   └─ u
 │       └─ th.ex.com
 └─ b
     └─ log.other.org

Запрос LIKE 'ap%' в trie означает: спуститься по a → p и взять всё поддерево. Ветка b отсекается на первом же шаге, ветка au — на втором. B-tree ответит на тот же запрос диапазонным сканом по отсортированному списку, но trie делает это через структурную навигацию: каждый символ — развилка, которая отбрасывает всё, что не начинается с нужного префикса.

У trie есть очевидная проблема: длинные цепочки узлов с единственным потомком тратят место и глубину. Если «auth.ex.com» — единственная строка на «au», хранить два отдельных узла «a» и «u» расточительно. Radix tree решает это сжатием: цепочка одиночных узлов схлопывается в одно ребро с многосимвольной меткой. Вместо a → u → t → h — одно ребро auth. PostgreSQL operator class text_ops строит именно radix tree.

Ключевое свойство trie, которое отличает его от GiST: разбиение непересекающееся. Строка, начинающаяся с «a», никогда не окажется в ветке «b». Поиск на каждом уровне выбирает ровно одну ветку.

Quad-tree: рекурсивное разбиение плоскости

Второй сценарий — сервис доставки еды. Таблица restaurants с 10 млн координат, колонка location POINT. Типичный запрос: все рестораны в прямоугольнике — WHERE location <@ box '((37.7,-122.4),(37.8,-122.3))'.

GiST решает эту задачу через bounding boxes, но для точек (в отличие от полигонов) существует более компактная структура — quad-tree. Quad-tree рекурсивно делит область на четыре квадранта: NW, NE, SW, SE. Каждый внутренний узел представляет прямоугольную область и содержит ровно четыре потомка:

(0,0)──────────────┬──────────────(100,0)
  │  NW             │  NE              │
  │  . . . .        │                  │
  │  . . .          │       .          │
  │    . . .        │                  │
  ├─────────────────┼──────────────────┤
  │  SW             │  SE              │
  │         .       │                  │
  │                 │            .     │
(0,100)─────────────┴──────────────(100,100)

Точки распределены неравномерно: NW плотный, остальные квадранты разреженные. Quad-tree делит NW дальше — на четыре подквадранта — и повторяет, пока число точек в узле не станет допустимым. SE с двумя точками остаётся одним листом. Дерево адаптируется к плотности данных: там, где много точек — глубже, где мало — мельче.

Запрос «все точки в прямоугольнике R» обходит дерево сверху вниз. На каждом узле проверяет: пересекается ли квадрант с R? Если нет — всё поддерево отсекается. Если да — спуск продолжается. В отличие от GiST, квадранты не пересекаются: точка принадлежит ровно одному квадранту, поэтому поиск не дублирует обход.

Похожую идею реализует k-d tree: вместо разбиения на четыре квадранта он на каждом уровне делит пространство пополам, чередуя оси — сначала по X, потом по Y, снова по X. PostgreSQL предлагает operator class kd_point_ops для этого варианта.

SP-GiST как фреймворк

SP-GiST — не один конкретный алгоритм, а фреймворк, объединяющий trie, radix tree, quad-tree и k-d tree общей инфраструктурой. Конкретную логику разбиения определяет operator class.

Внутренние узлы SP-GiST хранят метки разбиений — символ для trie, номер квадранта для quad-tree — вместо bounding boxes GiST. Каждая метка соответствует непересекающейся области. Листовые узлы хранят значения (или остатки после сжатия префикса в radix tree).

Фреймворк берёт на себя страничную организацию, WAL-журнал и конкурентный доступ. Operator class предоставляет четыре функции: как разбить пространство при вставке (picksplit), как выбрать ветку для запроса (inner_consistent), как проверить лист (leaf_consistent), как восстановить полное значение из пути. В PostgreSQL доступны operator classes: text_ops (radix tree для строк), quad_point_ops (quad-tree для точек), kd_point_ops (k-d tree для точек), inet_ops (префиксы IP-адресов и подсетей), range_ops (quad-tree для диапазонов).

Ключевое отличие от GiST

В GiST bounding boxes сиблингов могут пересекаться. Поиск точки (9, 5) при bbox A = [(0,0),(10,10)] и bbox B = [(8,0),(20,10)] попадает в оба — приходится спускаться по двум веткам. В худшем случае (сильно пересекающиеся данные) GiST обходит всё дерево — O(N). Кроме того, «мёртвый объём» между объектами внутри одного bbox вызывает ложные срабатывания и лишний I/O.

SP-GiST строит непересекающиеся разбиения. Точка лежит в ровно одном квадранте, строка начинается с ровно одного символа. Поиск на каждом шаге выбирает единственную ветку:

GiST:     bbox [A] и [B] перекрываются -> спуск в A и B
SP-GiST:  области [A] и [B] не пересекаются -> спуск только в одну

Это даёт O(глубина дерева) обращений к страницам при поиске — без лишних спусков и без dead space от перекрытий. Однако дерево SP-GiST не сбалансировано: глубина зависит от распределения данных. Radix tree для миллиона длинных строк с малым общим префиксом будет глубоким, а quad-tree для равномерно разбросанных точек — мелким. B-tree гарантирует O(log N) глубину независимо от данных; SP-GiST — нет.

GiST поддерживает KNN-поиск (<->) для многих типов данных. SP-GiST тоже поддерживает KNN для точек (с PostgreSQL 12+), но для более узкого набора типов.

Создание и использование

Возвращаемся к DNS-сценарию:

CREATE TABLE dns_records (
    id BIGSERIAL PRIMARY KEY,
    domain TEXT NOT NULL
);

CREATE INDEX idx_domain_spgist ON dns_records USING spgist (domain);

-- Все поддомены example.com
SELECT * FROM dns_records WHERE domain <@ 'example.com';

-- Префиксный поиск
SELECT * FROM dns_records WHERE domain LIKE 'api.example%';

Сценарий с координатами:

CREATE TABLE restaurants (
    id BIGSERIAL PRIMARY KEY,
    name TEXT,
    location POINT
);

CREATE INDEX idx_location_spgist ON restaurants USING spgist (location);

-- Точки в прямоугольнике (Сан-Франциско)
SELECT * FROM restaurants
WHERE location <@ box '((37.7,-122.4),(37.8,-122.3))';

EXPLAIN (ANALYZE, BUFFERS) покажет количество прочитанных страниц. При удачном распределении данных SP-GiST прочитает меньше страниц, чем GiST для того же запроса, потому что не тратит I/O на ложные срабатывания от пересекающихся bounding boxes.

Ограничения

Дерево SP-GiST не сбалансировано — глубина пропорциональна длине ключа или глубине пространственного разбиения, а не логарифму от числа строк. Для коротких строк с общими префиксами radix tree компактен, но для длинных строк без общих частей дерево становится глубоким.

SP-GiST не поддерживает ORDER BY: в дереве разбиений нет тотального порядка, поэтому сортировка результатов требует отдельного шага. Набор встроенных operator classes ограничен — если для типа данных нет подходящего класса, SP-GiST не применим (в отличие от B-tree, который работает с любым типом, имеющим оператор сравнения).

На практике SP-GiST встречается реже B-tree, GIN или GiST. Его ниша узка: префиксный поиск по строкам, IP-подсетям и пространственные запросы по точкам с неравномерным распределением. Но в этой нише он может превосходить GiST по размеру индекса и скорости поиска — непересекающиеся разбиения исключают мёртвый объём и гарантируют однозначный спуск по дереву.

Sources

PostgreSQL Documentation (пример: v16): SP-GiST. https://www.postgresql.org/docs/16/spgist.html
Aref W.G., Ilyas I.F. SP-GiST: An Extensible Database Index for Supporting Space Partitioning Trees // SIGMOD, 2001.

← BRIN | Планировщик запросов →

CS Notes

Explorer

spgist