B-Tree индексы: как работают и когда создавать

Таблица `orders` с 50 миллионами строк. Запрос `SELECT * FROM orders WHERE user_id = 42` без индекса: 8 секунд. С B-Tree индексом: 0.3 миллисекунды. Разница в 26000 раз. Один DDL-оператор - и система из «не работает» превращается в «летит».

• **E-commerce**: индекс на (user_id, created_at) на таблице заказов - разница между 10-секундным и мгновенным отображением истории покупок
• **Мониторинг**: индекс на (service_name, timestamp) на таблице логов позволяет строить дашборды в реальном времени без агрегации миллиардов строк
• **Аутентификация**: UNIQUE индекс на email - не только ограничение целостности, но и мгновенный поиск пользователя при логине вместо seq scan

Структура B-Tree

В 1972 году Байер и Макрейт предложили структуру данных, которая через полвека стала основой индексов в PostgreSQL, MySQL, SQLite и Oracle. **B-Tree** (сбалансированное дерево) - это не бинарное дерево: каждый узел хранит до нескольких сотен ключей. Высота дерева для таблицы в 100 миллионов строк - всего 4-5 уровней. Это значит, что любая строка находится за 4-5 обращений к диску, вместо полного перебора миллионов страниц.

Страница в PostgreSQL - 8KB. Узел B-Tree - это одна страница. В неё помещается несколько сотен ключей целочисленного типа. Чем больше ключей на страницу (branching factor), тем меньше высота дерева. Для таблицы в 1 млрд строк высота B-Tree - около 5 уровней.

Поиск и вставка

Поиск в B-Tree - traversal от корня к листу за O(log n). Но не всякий запрос может использовать индекс. PostgreSQL применяет индекс для поиска: **равенства** (`=`), **диапазонов** (`<`, `>`, `BETWEEN`), **начала строки** (`LIKE 'abc%'`). Индекс НЕ используется при `LIKE '%abc'` (нет начального якоря), `!=`, функциях над столбцом (`WHERE lower(email) = ...` без function index).

EXPLAIN ANALYZE показывает фактический план. `Index Scan` - поиск по индексу с обращением к heap. `Index Only Scan` - данные прямо из индекса (если SELECT покрыт индексом). `Bitmap Index Scan` + `Bitmap Heap Scan` - для нескольких совпадений: сначала строятся bitmap по индексу, затем heap читается упорядоченно. `Seq Scan` - полный перебор таблицы.

Составные индексы

Составной (composite) индекс покрывает несколько столбцов. `CREATE INDEX ON orders (user_id, created_at)` - это один индекс по обоим столбцам. Плюсы: покрывает запросы с обоими условиями лучше двух раздельных индексов; может быть **covering index** (Index Only Scan без обращения к heap). Минусы: занимает больше места; обновление любого из столбцов требует обновления индекса.

**Covering index**: если SELECT запрашивает только столбцы, которые есть в индексе, PostgreSQL может вернуть результат прямо из индекса без чтения heap страниц. В PostgreSQL для этого используется `INCLUDE` - добавление столбцов в индекс без участия в сортировке: `CREATE INDEX ON orders (user_id) INCLUDE (status, amount)`.

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

Порядок столбцов в составном индексе критичен. Правило: **equality первыми, range последними**. Индекс `(status, user_id)` хорошо работает для `WHERE status = 'active' AND user_id = 42`. Индекс `(user_id, created_at)` хорошо работает для `WHERE user_id = 42 AND created_at > X`. Если поменять порядок, эффективность резко падает: индекс по range-условию в первом столбце ограничивает поиск меньше, чем ожидается.

Правило выбора порядка: сначала столбцы с условием **равенства** (=), потом столбцы с **диапазоном** (<, >, BETWEEN, LIKE 'x%'). Это связано с тем, как B-Tree хранит данные: после нахождения диапазона по первому столбцу, поиск по второму столбцу уже не использует дерево линейно.

Селективность и когда НЕ создавать индекс

**Селективность** индекса - доля строк, которую возвращает запрос. Индекс эффективен при высокой селективности (мало строк). Индекс по столбцу `gender` (M/F) - почти бесполезен: запрос вернёт 50% таблицы, и seq scan будет быстрее. PostgreSQL сам принимает это решение через статистику (ANALYZE). Иногда разработчики создают индексы, которые оптимизатор никогда не выберет - это лишняя нагрузка на INSERT/UPDATE/DELETE.

Полезные инструменты диагностики: `pg_stat_user_indexes` - показывает сколько раз каждый индекс реально использовался. `pg_stat_user_tables` - сколько seq scan vs index scan. Индекс с `idx_scan = 0` за несколько месяцев - кандидат на удаление. Лишний индекс замедляет запись и занимает дисковое пространство.

Ключевые идеи

• **B-Tree** - сбалансированное дерево высотой 3-5 уровней для миллионов строк: поиск любого значения за O(log n) вместо O(n) полного сканирования
• **Составной индекс**: equality столбцы первыми, range последними; работает как prefix - запрос без первого столбца индекс не использует
• **Селективность определяет ценность**: индекс на столбце с 2-4 вариантами значений оптимизатор игнорирует; pg_stat_user_indexes показывает реальное использование

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

B-Tree индексы - база, но PostgreSQL поддерживает и другие типы индексов для специальных задач:

• Оконные функции — EXPLAIN ANALYZE показывает, используют ли оконные функции индексы при сортировке - критично для производительности аналитических запросов
• CTE и подзапросы — PostgreSQL может использовать индексы внутри CTE и подзапросов - план EXPLAIN покажет Index Scan в каждой части запроса

Вопросы для размышления

• Почему частичный индекс (partial index с WHERE) может быть эффективнее обычного для таблиц с 'горячим' подмножеством строк?
• Как определить, что индекс не используется оптимизатором, и какие шаги предпринять для диагностики?
• При каком соотношении операций чтения и записи создание дополнительных индексов начинает замедлять систему?

Связанные уроки

• pg-06-select — B-tree indexes directly accelerate WHERE equality/range predicates and ORDER BY in SELECT queries
• pg-13-covering — Covering indexes are B-trees extended with INCLUDE columns; this lesson is the prerequisite
• pg-18-explain — EXPLAIN ANALYZE output shows Index Scan vs Seq Scan; B-tree knowledge is needed to interpret it
• pg-19-join-algorithms — Merge join uses B-tree order; knowing the index structure explains why merge join prefers sorted inputs
• db-09-indexes-btree
• alg-10-binary-search