Как устроен под капотом индекс в БД?

Структура индекса в базе данных

Индекс — это структура данных, которая позволяет БД быстро находить строки без просмотра всей таблицы. Думай об индексе как об оглавлении в книге: вместо того чтобы читать каждую страницу, ты смотришь в оглавление и сразу переходишь к нужному разделу.

B-tree: самый распространённый тип индекса

Большинство БД (PostgreSQL, MySQL, Oracle) используют B-tree индексы по умолчанию:

Корень (root node)
    ├─ [10, 25, 40]
    ├─ Потомок 1: [5, 8]
    ├─ Потомок 2: [15, 20]
    ├─ Потомок 3: [30, 35]
    └─ Потомок 4: [50, 60]

Ключевые свойства B-tree:

• Сбалансированное дерево: все листья на одном уровне
• Множественные ветви: каждый узел содержит несколько ключей (обычно 100-1000)
• O(log n) поиск: даже на 1 млрд записей это ~10-15 операций дискового чтения
• Отсортированы: ключи хранятся в порядке, что позволяет делать range queries

Как работает поиск с индексом

Когда ты выполняешь запрос:

SELECT * FROM users WHERE id = 42;

БД делает это:

1. Входит в корень индекса
2. Сравнивает 42 с ключами: "42 > 25 и < 40 → идём вправо"
3. Переходит в нужный потомок
4. Повторяет пока не найдёт листовой узел
5. Получает ROW ID из листа
6. Прыгает в таблицу по ROW ID (одно дисковое чтение)

Без индекса: БД читает ВСЕ записи (full table scan).

Типы индексов и их применение

1. B-tree (по умолчанию)

CREATE INDEX idx_user_id ON users(id);

• Работает для: =, <, >, <=, >=, BETWEEN, LIKE (если начинается с конкретного символа)
• Универсальный, почти всегда правильный выбор

2. Hash индекс

CREATE INDEX idx_hash ON users USING HASH(email);

• Только для точного совпадения (=)
• Быстрее B-tree для точного поиска
• Не поддерживает range queries и сортировку

3. Bitmap индекс (Oracle, PostgreSQL)

CREATE INDEX idx_status ON orders(status);

• Отлично для колонок с малым количеством уникальных значений
• Экономит память
• Быстро работает с AND/OR операциями

4. GiST / GIN (PostgreSQL)

CREATE INDEX idx_json ON data USING GIN(metadata);

• Для JSON, полнотекстового поиска, массивов
• GIN (Generalized Inverted Index) быстрее для поиска, медленнее для вставок

Составной индекс (Composite Index)

Для оптимизации запросов с несколькими условиями:

CREATE INDEX idx_user_status ON users(status, created_at);

-- Этот запрос использует индекс полностью
SELECT * FROM users WHERE status = active AND created_at > 2025-01-01;

-- Этот использует индекс только для status
SELECT * FROM users WHERE status = active AND name = John;

Правило: колонки в WHERE с AND — кандидаты на составной индекс. Порядок важен (левосторонний префикс).

Плата за индекс

Индексы ускоряют чтение, но замедляют запись:

-- Одна вставка = одна запись в таблицу + одна запись в каждый индекс
INSERT INTO users(id, name, email, status) VALUES (...);
-- Если на таблице 5 индексов → 6 операций записи

Поэтому:

• Создавай индексы только на колонках, которые часто используются в WHERE/JOIN
• Убирай неиспользуемые индексы (см. pg_stat_user_indexes)
• На таблицах с частыми INSERT/UPDATE не создавай избыточные индексы

Как PostgreSQL выбирает план запроса

БД смотрит на запрос и решает:

• Использовать индекс?
• Какой индекс лучше?
• Full table scan дешевле?

EXPLAIN ANALYZE
SELECT * FROM users WHERE id = 42;

-- Результат:
-- Index Scan using idx_user_id on users
--   Index Cond: (id = 42)
--   Actual rows: 1

Если БД выбирает full scan вместо индекса — проверь, достаточно ли данных в таблице (на маленьких таблицах индекс неэффективен).

Практический совет

Не гадай — измеряй:

-- Смотри какие индексы есть
SELECT schemaname, tablename, indexname FROM pg_indexes;

-- Смотри какие не используются
SELECT schemaname, tablename, indexname, idx_scan
FROM pg_stat_user_indexes
ORDER BY idx_scan;

-- Видишь idx_scan = 0? Удаляй:
DROP INDEX idx_unused;

Индексы — это инвестиция: немного больше памяти и медленнее вставки, но намного быстрее чтение. Правильные индексы могут ускорить запрос в 100-1000 раз.