GiST — обобщённое дерево поиска
Предпосылки: B-tree.
← GIN | Hash Index →
Где B-tree и GIN перестают работать
B-tree работает с линейно упорядоченными данными. Для любых двух значений можно сказать: первое меньше, равно, или больше второго. Числа, строки, даты — всё это ложится на одномерную ось.
GIN работает с составными значениями, но отвечает только на вопрос “содержит ли значение элемент X”. Поиск по дискретному вхождению.
Проблема: не все данные и не все запросы укладываются в эти модели.
Пример: геометрические данные
Таблица ресторанов с координатами:
CREATE TABLE restaurants (
id SERIAL PRIMARY KEY,
name TEXT,
location POINT -- координаты (x, y)
);
Запрос: найти все рестораны в радиусе 1 км от точки (10, 20).
SELECT * FROM restaurants
WHERE location <@ circle '((10,20), 1)';
Почему B-tree не поможет: точки двумерные. Нет естественного линейного порядка. Можно отсортировать по X, но тогда точки с близким X, но далёким Y окажутся рядом в индексе, хотя географически они далеко.
Почему GIN не поможет: точка — не составное значение в том смысле, как массив. Её нельзя разбить на элементы для инвертированного индекса. Запрос “в радиусе 1 км” — не проверка вхождения элемента.
Оба индекса не подходят для данных, которые описывают регионы в пространстве — геометрические фигуры, временные интервалы, IP-диапазоны. Для таких типов PostgreSQL предоставляет GiST (Generalized Search Tree) — обобщённое дерево поиска. «Обобщённое» означает, что GiST работает не с конкретным типом данных, а с абстрактным интерфейсом: разработчик типа определяет операции сравнения через operator class, а GiST предоставляет механизм дерева, балансировки и страничной организации. Появился в PostgreSQL 7.0 (2000), основан на работе Hellerstein, Naughton, Pfeffer (1995).
Пример: диапазоны
Таблица бронирований переговорок:
CREATE TABLE bookings (
id SERIAL PRIMARY KEY,
room_id INTEGER,
during TSRANGE -- временной диапазон
);
Запрос: найти все бронирования, пересекающиеся с интервалом 10:30-11:30.
SELECT * FROM bookings
WHERE during && '[2024-01-15 10:30, 2024-01-15 11:30)';
Почему B-tree не поможет: диапазоны можно линейно упорядочить (по началу, потом по концу). Но запрос “пересекается с” не сводится к сравнению. Диапазон [14:00, 15:00) “больше” чем [10:30, 11:30) по началу, но они не пересекаются. Диапазон [10:00, 11:00) “меньше” по началу, но пересекается.
Идея GiST: иерархическая группировка по охватывающим регионам
Вместо сортировки по одной оси, разбиваем пространство на регионы:
Корень:
Весь мир: bounding box [(-180,-90), (180,90)]
Дети корня:
Европа: [(-10,35), (40,70)]
Азия: [(40,5), (180,75)]
Америка: [(-170,-55), (-30,70)]
Внутри Европы:
Франция: [(-5,42), (8,51)]
Германия: [(6,47), (15,55)]
...
Каждый внутренний узел содержит bounding box — минимальный прямоугольник, охватывающий все объекты в поддереве.
Поиск “все рестораны в радиусе 1 км от точки P”:
1. Проверяем корень: пересекается ли bounding box корня с кругом поиска?
Да — идём глубже
2. Проверяем детей корня: какие bounding boxes пересекаются с кругом?
Только Европа — спускаемся только туда
Азия и Америка отсекаются целиком (pruning)
3. Внутри Европы: какие bounding boxes пересекаются?
Только Франция — спускаемся
4. В листьях: проверяем каждый ресторан точно
Ключевая идея: если bounding box узла НЕ пересекается с областью поиска, всё поддерево можно отбросить без проверки. Это даёт логарифмическое время поиска в типичном случае.
Фундаментальное отличие от B-tree
В B-tree разделитель делит пространство на две непересекающиеся части: “меньше” и “больше-или-равно”. Значение может быть только в одном поддереве. Спуск — всегда одна ветка.
В GiST bounding boxes детей одного узла могут пересекаться:
Узел:
Ребёнок A: bbox [(0,0), (10,10)]
Ребёнок B: bbox [(8,0), (20,10)]
↑
Перекрытие по X от 8 до 10
Ищем точку (9, 5):
Попадает в bbox A? Да
Попадает в bbox B? Да
Нужно спускаться в ОБА поддерева
Почему это допускается: для многомерных данных часто невозможно разбить пространство без пересечений, не создавая несбалансированное дерево. Поддержание непересекающихся регионов требовало бы дорогих перестроений.
Влияние на производительность: в худшем случае (сильно пересекающиеся данные) придётся обойти всё дерево — O(N). На практике для реальных геоданных пересечения локальны, и pruning отсекает большую часть дерева. Для данных, которые естественно разбиваются без пересечений (строки по префиксам, точки по квадрантам), SP-GiST использует противоположный подход — непересекающиеся разбиения с гарантией спуска по одной ветке.
Мёртвый объём (dead space)
Когда два объекта помещаются в один узел, их общий bounding box охватывает оба. Но часть bbox может не содержать реальных объектов:
R1 = [(0,0), (2,2)] площадь = 4
R3 = [(8,8), (10,10)] площадь = 4
Общий bbox = [(0,0), (10,10)] площадь = 100
Реальные объекты занимают: 4 + 4 = 8
Мёртвый объём: 100 - 8 = 92
(0,0)─────────────────────(10,0)
│ R1 │
│ ██ │
│ │
│ мёртвый │
│ объём │
│ │
│ ██ │ R3
(0,10)────────────────────(10,10)
Почему это плохо: при поиске в области между R1 и R3 мы спустимся в узел, но ничего не найдём — ложное срабатывание, потраченный I/O.
Operator Class для GiST
GiST требует от типа данных определить набор функций:
consistent(node_predicate, query_predicate) — может ли поддерево содержать результаты? Возвращает true/false. Это функция pruning — если false, поддерево отсекается.
Пример для точек и запроса "в круге":
consistent(bbox, circle) = пересекается ли bbox с circle?
union(entries) — вычислить охватывающий регион для набора записей. Используется при построении и модификации дерева.
Пример для точек:
union([(1,1), (5,3), (2,7)]) = bbox [(1,1), (5,7)]
penalty(existing_entry, new_entry) — штраф за добавление новой записи в узел. Используется при выборе, куда вставлять. Меньший штраф — лучше.
Пример: насколько увеличится bbox узла при добавлении новой точки?
Большое увеличение = большой штраф = лучше поискать другой узел
picksplit(entries) — как разделить переполненный узел на два. Критически важно для качества дерева.
Поиск в GiST: пошаговый пример
Задача: найти все прямоугольники, пересекающиеся с запросом Q = [(5,5), (15,15)].
Структура GiST:
Корень:
Entry1: bbox [(0,0), (12,18)], ptr → Лист A
Entry2: bbox [(0,20), (30,30)], ptr → Лист B
Лист A: R1=[(0,0),(10,10)], R3=[(8,8),(12,18)], R5=[(10,0),(20,10)]
Лист B: R2=[(20,20),(30,30)], R4=[(0,20),(5,25)]
Шаг 1: Корень
consistent([(0,0), (12,18)], Q) = пересекаются? Да → Лист A в очередь
consistent([(0,20), (30,30)], Q) = пересекаются? Нет (20 > 15) → Лист B отсекается
Шаг 2: Лист A
consistent(R1, Q) = [(0,0),(10,10)] && [(5,5),(15,15)]? Да → кандидат
consistent(R3, Q) = [(8,8),(12,18)] && Q? Да → кандидат
consistent(R5, Q) = [(10,0),(20,10)] && Q? Да → кандидат
Итог: R1, R3, R5. Лист B (с R2, R4) не читали вообще.
Вставка в GiST
Вставляем новый прямоугольник R6 = [(6,6), (9,9)].
Шаг 1: Выбор поддерева (chooseSubtree)
Начиная с корня, для каждого уровня выбираем entry с минимальным penalty:
penalty(Entry1, R6) = насколько увеличится bbox [(0,0), (12,18)]?
R6 уже внутри bbox → увеличение = 0
penalty(Entry2, R6) = насколько увеличится bbox [(0,20), (30,30)]?
Нужно расширить до [(0,6), (30,30)] → значительное увеличение
Выбираем Entry1, спускаемся в Лист A.
Шаг 2: Вставка в лист
Добавляем R6 в Лист A. Если лист не переполнен — готово.
Шаг 3: Обновление bbox предков
R6 внутри старого bbox Entry1 — не изменился. Если бы R6 выходил за пределы — обновили бы bbox и проверили выше.
Split в GiST
Лист переполнен. Нужно разделить на два.
Проблема: в B-tree split тривиален — берём медиану. В GiST нет линейного порядка.
Функция picksplit решает задачу. Стратегии:
Quadratic split: Найти пару записей, которая при помещении в один узел создаёт максимальный мёртвый объём. Они становятся “семенами” двух узлов. Остальные записи распределяем по минимальному penalty.
Хороший picksplit минимизирует суммарный мёртвый объём и перекрытие результирующих bbox.
Удаление в GiST
Важное отличие от B-tree: GiST не использует borrowing и merge.
В B-tree borrowing работает благодаря линейному порядку — можно взять крайний элемент у соседа. В GiST нет понятия “соседний узел” в том же смысле.
Стратегия GiST при underflow: reinsertion
1. Удаляем все записи из underfull узла
2. Удаляем сам узел
3. Вставляем записи заново (через обычный insert)
Это дорого, но происходит редко и может улучшить общую структуру.
Recheck: ложные срабатывания
В GIN поиск точный: если TID в posting list — строка точно содержит элемент.
В GiST поиск приблизительный на уровне внутренних узлов. Bounding box говорит “объект МОЖЕТ быть здесь”, не “объект ТОЧНО здесь”.
Пример:
Ищем: точки в круге с центром (5,5) и радиусом 1
Bounding box узла: [(4,4), (6,6)]
Круг пересекается с bbox? Да — спускаемся
В листе находим точку (4, 6)
Точка в круге? Расстояние = √((5-4)² + (5-6)²) = √2 ≈ 1.41 > 1
Точка ВНЕ круга, но была внутри bbox
PostgreSQL делает recheck — после получения кандидатов из индекса проверяет каждого точным условием.
Уникальная возможность: KNN (K Nearest Neighbors)
GiST поддерживает поиск ближайших соседей через оператор расстояния ←>:
SELECT * FROM restaurants
ORDER BY location <-> point '(10, 20)'
LIMIT 5;
“Найти 5 ресторанов ближайших к точке (10, 20)”
Это нельзя эффективно сделать через B-tree или GIN — у них нет понятия “расстояние”.
Поддерживаемые операторы
| Оператор | Значение |
|---|---|
&& | Пересекается |
@> | Содержит регион |
<@ | Содержится в регионе |
<< | Строго слева |
>> | Строго справа |
&< | Не правее |
&> | Не левее |
<-> | Расстояние (для KNN) |
Типичные типы данных для GiST
| Тип | Применение |
|---|---|
| point, box, polygon, circle | Геометрия |
| geometry, geography (PostGIS) | Геоданные |
| int4range, tsrange, и др. | Диапазоны |
| inet, cidr | IP-адреса и сети |
| ltree | Иерархические метки |
Сравнение GIN и GiST
| Характеристика | GIN | GiST |
|---|---|---|
| Модель данных | Инвертированный индекс | Дерево с охватывающими регионами |
| Типичные запросы | ”содержит элемент" | "пересекается”, “содержится”, “ближайший к” |
| Типичные типы | array, jsonb, tsvector | geometry, point, range types |
| Точность поиска | Точный | Может требовать recheck |
| Спуск по дереву | Всегда одна ветка | Возможно несколько веток |
| Размер индекса | Обычно больше | Обычно компактнее |
| KNN | Нет | Да |
Когда выбирать:
GIN — когда значения состоят из дискретных элементов и нужен поиск по вхождению.
GiST — когда данные описывают непрерывные регионы (диапазоны, геометрии) или нужны пространственные операции (пересечение, расстояние).
GiST — фреймворк для пространственных и нестандартных типов данных. Для простейшего случая — поиск только по точному равенству — существует более компактный Hash-индекс.
Sources
- PostgreSQL Documentation (пример: v16): GiST, KNN search. https://www.postgresql.org/docs/16/gist.html
← GIN | Hash Index →