Space-Partitioned GiST для деревьев, трие и данных с дискретным разбиением.
SP-GiST — это индекс для данных, которые можно разбить на непересекающиеся подпространства. Трие, quad-деревья, kd-деревья — всё это SP-GiST.
SP-GiST (Space-Partitioned GiST) — это индекс, основанный на разделении пространства данных на непересекающиеся области.
В отличие от GiST, где области могут пересекаться (bounding box), в SP-GiST каждое значение принадлежит только одному подпространству.
GiST: области могут пересекаться
┌──────────┐ ┌──────────┐
│ Box 1 │────│ Box 2 │ ← Пересечение!
└──────────┘ └──────────┘
SP-GiST: непересекающиеся области
┌──────┬──────┬──────┐
│ Area 1 │ Area 2 │ Area 3 │ ← Нет пересечений
└──────┴──────┴──────┘
| Сценарий | Структура | Пример |
|---|---|---|
| Префиксный поиск | Трие (prefix tree) | WHERE text LIKE 'abc%' |
| Поиск по IP-адресам | Radix tree | WHERE inet << '192.168.0.0/16' |
| 2D-точки | Quad-tree | WHERE point <@ box |
| KD-дерево | k-dimensional tree | Поиск ближайших в многомерном пространстве |
| Фонетический поиск | Soundex-trie | WHERE name ~ 'smith' |
┌─────────────┐
│ ROOT │
│ (разбиение │
│ по первой │
│ букве) │
└──────┬──────┘
│
┌─────────────────┼─────────────────┐
│ │ │
┌────▼────┐ ┌────▼────┐ ┌────▼────┐
│ 'A' │ │ 'B' │ │ 'C' │ ← Узлы первого
│ (дальше │ │ (дальше │ │ (дальше │ уровня
│ по 2-й │ │ по 2-й │ │ по 2-й │
│ букве) │ │ букве) │ │ букве) │
└────┬────┘ └────┬────┘ └────┬────┘
│ │ │
┌────┴────┐ ┌────┴────┐ ┌────┴────┐
▼ ▼ ▼ ▼ ▼ ▼
┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐
│ 'AA' │ │ 'AB' │ │ 'BA' │ │ 'BB' │ │ 'CA' │ │ 'CB' │ ← Узлы второго
└──────┘ └──────┘ └──────┘ └──────┘ └──────┘ └──────┘ уровня
Для поддержки типа данных нужно определить 4 метода:
| Метод | Описание |
|---|---|
| Consistent | Проверяет, удовлетворяет ли элемент условию |
| Choose | Выбирает поддерево для вставки или разбиения |
| Picksplit | Разделяет узел на непересекающиеся подпространства |
| Compress | Сжимает данные (может возвращать NULL для хранения без сжатия) |
SELECT * FROM words WHERE word LIKE 'abc%';Преимущество: посещаем только нужные ветви, не пересекающиеся области.
CREATE TABLE words (
id BIGSERIAL PRIMARY KEY,
word VARCHAR(255)
);
INSERT INTO words (word) VALUES
('apple'),
('application'),
('apply'),
('banana'),
('band'),
('bandana');CREATE INDEX idx_words_word ON words USING SPGIST (word);-- Префиксный поиск
SELECT * FROM words WHERE word LIKE 'app%';
-- Найдёт: apple, application, apply
-- Префикс с оператором ~
SELECT * FROM words WHERE word ~ '^app';
-- Точное совпадение
SELECT * FROM words WHERE word = 'apple';
-- Начинaется с любого из префиксов
SELECT * FROM words WHERE word <@ ANY(ARRAY['app', 'ban']);EXPLAIN ANALYZE
SELECT * FROM words WHERE word LIKE 'app%';С SP-GiST:
Index Scan using idx_words_word on words
Index Cond: (word ~>=~ 'app' AND word ~<~ 'apq')
Execution Time: 0.2 ms
С B-деревом:
Index Scan using idx_words_btree on words
Index Cond: ((word >= 'app'::text) AND (word < 'apq'::text))
Execution Time: 0.3 ms
С Seq Scan:
Seq Scan on words
Filter: (word ~~ 'app%'::text)
Execution Time: 1.5 ms
CREATE TABLE ip_addresses (
id BIGSERIAL PRIMARY KEY,
ip INET
);
INSERT INTO ip_addresses (ip) VALUES
('192.168.1.1'),
('192.168.1.100'),
('10.0.0.1'),
('172.16.0.1');CREATE INDEX idx_ips_ip ON ip_addresses USING SPGIST (ip);-- Поиск по подсети (<< — содержится в)
SELECT * FROM ip_addresses
WHERE ip << '192.168.0.0/16'::inet;
-- Поиск по точному IP
SELECT * FROM ip_addresses WHERE ip = '192.168.1.1';
-- Поиск по диапазону
SELECT * FROM ip_addresses
WHERE ip >>= '192.168.1.0/24'::inet; -- Содержит подсеть| Оператор | Описание | Пример |
|---|---|---|
<< | Содержится в подсети | ip << '192.168.0.0/16' |
>>= | Содержит подсеть | '192.168.0.0/16' >>= ip |
= | Точное совпадение | ip = '192.168.1.1' |
<, > | Сравнение | ip < '192.168.2.0' |
CREATE TABLE locations (
id BIGSERIAL PRIMARY KEY,
point POINT
);
INSERT INTO locations (point) VALUES
('(1, 1)'),
('(1, 2)'),
('(2, 1)'),
('(2, 2)'),
('(10, 10)'),
('(11, 11)');CREATE INDEX idx_locations_point ON locations USING SPGIST (point);-- Поиск в прямоугольнике
SELECT * FROM locations
WHERE point <@ BOX('(0, 0), (3, 3)');
-- Поиск в круге (через расстояние)
SELECT * FROM locations
WHERE point <-> POINT '(2, 2)' < 2;
-- Ближайшие точки (KNN)
SELECT * FROM locations
ORDER BY point <-> POINT '(0, 0)'
LIMIT 5;Пространство разбивается на 4 квадранта:
┌──────────────┬──────────────┐
│ Q1 (x<0, │ Q2 (x>=0, │
│ y>=0) │ y>=0) │
├──────────────┼──────────────┤
│ Q3 (x<0, │ Q4 (x>=0, │
│ y<0) │ y<0) │
└──────────────┴──────────────┘
Каждый квадрант может быть разбит ещё на 4 и так далее.
CREATE TABLE products (
id BIGSERIAL PRIMARY KEY,
name VARCHAR(255),
price NUMERIC,
weight NUMERIC,
rating NUMERIC
);
-- KD-дерево по трём измерениям
CREATE INDEX idx_products_kd ON products
USING SPGIST ((price, weight, rating));-- Поиск в многомерном диапазоне
SELECT * FROM products
WHERE (price, weight, rating) <@
(100, 5, 4.5)::box3d;
-- Ближайшие соседи в многомерном пространстве
SELECT * FROM products
ORDER BY (price, weight, rating) <-> (50, 2, 4.0)
LIMIT 10;-- Таблица с 1 млн слов
CREATE TABLE big_words (
id BIGSERIAL,
word VARCHAR(255)
);
-- Индексы
CREATE INDEX idx_btree ON big_words USING BTREE (word);
CREATE INDEX idx_spgist ON big_words USING SPGIST (word);
-- Префиксный поиск
EXPLAIN ANALYZE
SELECT * FROM big_words WHERE word LIKE 'test%';Результаты:
| Индекс | Время |
|---|---|
| SP-GiST | 0.5 ms |
| B-дерево | 0.6 ms |
| Seq Scan | 50 ms |
Вывод: SP-GiST и B-дерево сопоставимы для префиксов.
-- B-дерево НЕ поддерживает оператор <<
CREATE INDEX idx_btree ON ip_addresses USING BTREE (ip);
-- Запрос с << не использует B-дерево
SELECT * FROM ip_addresses WHERE ip << '192.168.0.0/16';
-- Seq Scan!
-- SP-GiST использует индекс
SELECT * FROM ip_addresses WHERE ip << '192.168.0.0/16';
-- Index Scan!| Тип данных | SP-GiST размер |
|---|---|
| text (трие) | ~1.5x от данных |
| inet | ~1.2x от данных |
| point | ~2x от данных |
-- SP-GiST не может использоваться для сортировки
SELECT * FROM words ORDER BY word; -- Требуется отдельная сортировка
-- B-дерево может:
SELECT * FROM words ORDER BY word; -- Индекс используется длясортировки-- Для text SP-GiST не поддерживает <, >, BETWEEN
SELECT * FROM words WHERE word BETWEEN 'apple' AND 'banana';
-- B-дерево лучше для диапазонных запросов-- SP-GiST не индексирует NULL значения
INSERT INTO words (word) VALUES (NULL); -- Не в индексеSELECT
indexname,
pg_size_pretty(pg_relation_size(indexname::regclass)) as size
FROM pg_indexes
WHERE tablename = 'words';SELECT
indexrelname,
idx_scan,
idx_tup_read
FROM pg_stat_user_indexes
WHERE relname = 'words';-- Расширение pgstattuple
CREATE EXTENSION IF NOT EXISTS pgstattuple;
-- Для SP-GiST статистика ограничена
SELECT * FROM pgstatindex('idx_words_word');CREATE TABLE dictionary (
id BIGSERIAL PRIMARY KEY,
word VARCHAR(255) NOT NULL,
frequency INTEGER
);
CREATE INDEX idx_dictionary_word ON dictionary USING SPGIST (word);
-- Автодополнение
SELECT word, frequency
FROM dictionary
WHERE word LIKE 'прогр%'
ORDER BY frequency DESC
LIMIT 10;CREATE TABLE access_log (
id BIGSERIAL PRIMARY KEY,
ip INET NOT NULL,
accessed_at TIMESTAMP
);
CREATE INDEX idx_access_log_ip ON access_log USING SPGIST (ip);
-- Логи из определённой подсети
SELECT * FROM access_log
WHERE ip << '192.168.1.0/24'::inet
ORDER BY accessed_at DESC
LIMIT 100;CREATE TABLE taxis (
id BIGSERIAL PRIMARY KEY,
location POINT NOT NULL,
driver_name VARCHAR(255)
);
CREATE INDEX idx_taxis_location ON taxis USING SPGIST (location);
-- Такси в районе
SELECT * FROM taxis
WHERE location <@ BOX('(0, 0), (5, 5)');
-- Ближайшие такси
SELECT * FROM taxis
ORDER BY location <-> POINT '(2.5, 2.5)'
LIMIT 5;| Характеристика | SP-GiST | GiST | GIN | B-дерево |
|---|---|---|---|---|
| Префиксный поиск | ✅ Отлично | ⚠️ Хорошо | ❌ Нет | ✅ Хорошо |
| IP-адреса | ✅ Отлично | ⚠️ Требует расширения | ❌ Нет | ❌ Нет |
| 2D/3D точки | ✅ Хорошо | ✅ Отлично | ❌ Нет | ❌ Нет |
| Диапазоны | ❌ Нет | ✅ Отлично | ⚠️ Частично | ✅ Отлично |
| Сортировка | ❌ Нет | ⚠️ Частично | ❌ Нет | ✅ Отлично |
| NULL значения | ❌ Нет | ✅ Да | ✅ Да | ✅ Да |
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.