MidТеория6 min

Индексы: основы и типы

B-tree, Hash, GIN, GiST, покрывающие и составные индексы — когда и какой использовать

BdIndexing

Индекс — структура данных, которая ускоряет поиск строк в таблице. Без индексов база сканирует всю таблицу (Sequential Scan), что катастрофично при больших объёмах данных.

Зачем нужны индексы

-- Table: 10 million rows, no index
SELECT * FROM orders WHERE user_id = 42;
-- PostgreSQL scans ALL 10 million rows → 3-5 seconds

-- After: CREATE INDEX idx_orders_user_id ON orders(user_id);
SELECT * FROM orders WHERE user_id = 42;
-- B-tree lookup → 1-3 milliseconds

Индекс — компромисс: ускоряет чтение, замедляет запись (INSERT/UPDATE/DELETE должны обновлять индекс).

B-tree индекс

Самый распространённый тип. По умолчанию при CREATE INDEX.

Структура

B-tree (Balanced Tree) — сбалансированное дерево, где:

  • Корень — верхний узел
  • Внутренние узлы — диапазоны ключей, ведущие к листьям
  • Листья — значения ключей + указатели на строки в таблице (heap)
                    [50]
                   /    \
              [20, 35]   [70, 85]
             /   |   \    |    \
          [1-19][21-34][36-49][51-69][71-100]

Поддерживаемые операции

-- B-tree supports: =, <, >, <=, >=, BETWEEN, IN, LIKE 'prefix%'
SELECT * FROM users WHERE id = 42;               -- exact match
SELECT * FROM orders WHERE total BETWEEN 100 AND 500; -- range
SELECT * FROM products WHERE name LIKE 'iPhone%'; -- prefix
SELECT * FROM users ORDER BY created_at;          -- sort (index scan)

-- NOT supported efficiently:
SELECT * FROM products WHERE name LIKE '%phone%'; -- leading wildcard
SELECT * FROM logs WHERE date_part('year', created_at) = 2024; -- function

Создание

-- Simple index
CREATE INDEX idx_users_email ON users(email);

-- Unique index (also enforces uniqueness constraint)
CREATE UNIQUE INDEX idx_users_email_uniq ON users(email);

-- Index with specific order
CREATE INDEX idx_orders_created_desc ON orders(created_at DESC);

-- Concurrent creation (doesn't lock table for reads/writes)
CREATE INDEX CONCURRENTLY idx_products_category ON products(category_id);

Hash индекс

Оптимизирован исключительно для операции =. Хранит хэши значений.

CREATE INDEX idx_sessions_token ON sessions USING HASH (token);

-- Efficient:
SELECT * FROM sessions WHERE token = 'abc123xyz'; -- O(1)

-- NOT efficient (falls back to seq scan):
SELECT * FROM sessions WHERE token > 'abc';       -- no range support
SELECT * FROM sessions ORDER BY token;            -- no sort support

Когда использовать Hash

  • Поле используется только для поиска по точному совпадению
  • Большие текстовые ключи (хэш фиксированного размера vs полный текст в B-tree)
  • UUID-поля для lookup

На практике: Hash индексы используются редко. B-tree немного медленнее для =, но поддерживает всё остальное.

GIN (Generalized Inverted Index)

Используется для полнотекстового поиска и JSONB.

-- Full-text search
CREATE INDEX idx_articles_search ON articles USING GIN (to_tsvector('russian', body));

SELECT * FROM articles
WHERE to_tsvector('russian', body) @@ to_tsquery('russian', 'индекс & транзакция');

-- JSONB search
CREATE INDEX idx_events_data ON events USING GIN (data);

SELECT * FROM events WHERE data @> '{"type": "click"}';
SELECT * FROM events WHERE data ? 'error_code';  -- key exists

Когда использовать GIN

  • Полнотекстовый поиск (tsvector @@ tsquery)
  • Поиск в JSONB (@>, ?, ?|, ?&)
  • Массивы (@>, <@, &&)

GiST (Generalized Search Tree)

Для геометрических данных и диапазонов.

-- Geographic data (PostGIS)
CREATE INDEX idx_locations_point ON locations USING GIST (coordinates);

SELECT * FROM restaurants WHERE coordinates <-> point(55.75, 37.61) < 1000;

-- Range types
CREATE INDEX idx_events_duration ON events USING GIST (duration);

SELECT * FROM events WHERE duration && '[2024-01-01, 2024-12-31]'::daterange;

Составные индексы (Composite / Multi-column)

Индекс по нескольким столбцам.

Порядок столбцов критичен

CREATE INDEX idx_orders_user_status ON orders(user_id, status);

-- Uses index:
SELECT * FROM orders WHERE user_id = 42;                         -- ✓ leading column
SELECT * FROM orders WHERE user_id = 42 AND status = 'new';     -- ✓ full index
SELECT * FROM orders WHERE user_id = 42 ORDER BY status;        -- ✓ index sort

-- Does NOT use index:
SELECT * FROM orders WHERE status = 'new';                      -- ✗ not leading column

Правило: запрос может использовать составной индекс только если включает левый префикс столбцов индекса.

Когда составной индекс лучше двух раздельных

-- Query: WHERE user_id = 42 AND status = 'new'

-- Option 1: two separate indexes
CREATE INDEX ON orders(user_id);
CREATE INDEX ON orders(status);
-- PostgreSQL picks ONE index and filters, or uses bitmap and merge

-- Option 2: composite index
CREATE INDEX ON orders(user_id, status);
-- Single index lookup, more efficient

Покрывающий индекс (Covering Index)

Индекс содержит все столбцы, нужные запросу — чтение данных не требует обращения к таблице.

-- Query needs: user_id (filter), total (return), created_at (sort)
CREATE INDEX idx_orders_covering ON orders(user_id) INCLUDE (total, created_at);

SELECT total, created_at FROM orders WHERE user_id = 42 ORDER BY created_at;
-- Index Only Scan — data fetched entirely from index, no heap access

Как проверить

EXPLAIN SELECT total, created_at FROM orders WHERE user_id = 42;
-- Look for "Index Only Scan" vs "Index Scan"
-- Index Only Scan = covering index (faster, no heap access)

Частичный индекс (Partial Index)

Индексирует только часть строк таблицы.

-- Only index active orders (99% of queries)
CREATE INDEX idx_orders_active ON orders(user_id)
WHERE status = 'active';

-- Only index non-null values
CREATE INDEX idx_users_phone ON users(phone)
WHERE phone IS NOT NULL;

-- Only index large orders for analytics
CREATE INDEX idx_large_orders ON orders(total, created_at)
WHERE total > 10000;

Преимущества:

  • Меньший размер индекса
  • Быстрее обновляется (меньше строк)
  • Планировщик использует его только для подходящих запросов

Индексы на выражениях (Expression Indexes)

-- Case-insensitive email lookup
CREATE INDEX idx_users_email_lower ON users(lower(email));

SELECT * FROM users WHERE lower(email) = lower('[email protected]');

-- Index on date part
CREATE INDEX idx_orders_year ON orders(date_part('year', created_at));

SELECT * FROM orders WHERE date_part('year', created_at) = 2024;

-- Index on computed value
CREATE INDEX idx_products_full_name ON products((brand || ' ' || model));

Когда индексы НЕ помогают

-- 1. Low cardinality (few unique values) — table scan may be faster
-- Column "gender" with values: 'M', 'F' — 50% of table = seq scan better
CREATE INDEX idx_users_gender ON users(gender);  -- often useless

-- 2. Small tables (< 1000 rows) — seq scan is almost always faster
-- PostgreSQL planner will ignore the index

-- 3. Leading wildcard in LIKE
SELECT * FROM users WHERE name LIKE '%Иван%';  -- can't use B-tree

-- 4. Function on indexed column without expression index
SELECT * FROM users WHERE UPPER(name) = 'ИВАН';  -- no index on UPPER(name)

-- 5. Type mismatch
-- Index on INTEGER column id, but:
SELECT * FROM users WHERE id = '42';  -- '42' is text, implicit cast breaks index

Управление индексами

-- List all indexes for a table
SELECT indexname, indexdef
FROM pg_indexes
WHERE tablename = 'orders';

-- Index size
SELECT indexname, pg_size_pretty(pg_relation_size(indexname::regclass))
FROM pg_indexes
WHERE tablename = 'orders';

-- Index usage statistics
SELECT schemaname, tablename, indexname,
    idx_scan,       -- number of index scans
    idx_tup_read,   -- tuples read via index
    idx_tup_fetch   -- live tuples fetched
FROM pg_stat_user_indexes
WHERE tablename = 'orders'
ORDER BY idx_scan DESC;

-- Find unused indexes (candidates for removal)
SELECT schemaname, tablename, indexname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0
  AND NOT indisprimary  -- not primary key
ORDER BY pg_relation_size(indexname::regclass) DESC;

-- Rebuild index (fix bloat)
REINDEX INDEX CONCURRENTLY idx_orders_user_id;

Типичные вопросы на интервью

Q: «Какой индекс создать для LIKE '%search%'?»

Ответ: «B-tree не поддерживает leading wildcard. Варианты: GIN-индекс на tsvector для полнотекстового поиска (to_tsvector, tsquery), или расширение pg_trgm с GIN/GiST-индексом по триграммам для произвольных LIKE-паттернов.»

CREATE EXTENSION pg_trgm;
CREATE INDEX idx_products_name_trgm ON products USING GIN (name gin_trgm_ops);
SELECT * FROM products WHERE name LIKE '%phone%';  -- now uses GIN index

Q: «Почему NOT IN плохо работает с индексами?»

Ответ: «NOT IN требует проверить, что значение НЕ входит в множество. При наличии NULL в списке или в столбце результат всегда пустой из-за трёхзначной логики SQL. Планировщик часто выбирает seq scan. Предпочтительнее NOT EXISTS или LEFT JOIN.»

Проверь себя

В таблице 50 миллионов строк. Поле 'gender' содержит только 'M' и 'F'. Стоит ли создавать индекс на это поле?

Что такое 'Index Only Scan' в EXPLAIN?

Почему CREATE INDEX CONCURRENTLY предпочтительнее обычного CREATE INDEX в production?

Для какого запроса GIN-индекс предпочтительнее B-tree?

Создан индекс CREATE INDEX ON orders(user_id, status). Какой запрос НЕ будет его использовать?

Связанные темы

Указатели

Связанная тема

Основы дженериков

Связанная тема

Зачем оценивать

Связанная тема

Оптимизация запросов и EXPLAIN

Связанная тема

Блокировки в базах данных

Связанная тема