Базы данных

Индексы: B-Tree и как они работают

Цели урока

Понять структуру B+ Tree и почему поиск O(log n)
Применять prefix rule при создании составных индексов
Создавать covering index для Index Only Scan
Диагностировать и устранять index bloat

Запрос без индекса по таблице из 50 миллионов строк - это 8 секунд ожидания. Тот же запрос с правильным индексом - 2 миллисекунды. B-Tree превращает O(n) в O(log n), но только если понимать как его создавать и обслуживать.

**E-commerce:** индекс (user_id, status) ускоряет загрузку заказов пользователя
**Analytics:** covering index позволяет считать агрегаты без обращения к heap
**High-write системы:** fillfactor и мониторинг bloat предотвращают деградацию
**Отладка:** EXPLAIN ANALYZE показывает какой scan используется и почему

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

Таблица `orders` с 50 миллионами строк. Запрос `WHERE user_id = 42` без индекса читает все 50 млн строк - полный sequential scan. С индексом B-Tree тот же запрос делает ~25 операций чтения. Разница - от минут до миллисекунд.

**B-Tree (Balanced Tree)** - сбалансированное дерево поиска, где каждый узел хранит несколько ключей и ссылок на дочерние узлы. В PostgreSQL B-Tree - это B+ Tree: все данные только в листьях, внутренние узлы хранят только ключи для навигации.

Листья связаны двусвязным списком - это ключевое свойство B+ Tree. Благодаря ему работают **range-запросы** (`WHERE id BETWEEN 100 AND 200`): находим первый лист, затем идём по цепочке не возвращаясь в корень.

**Порядок B-Tree в PostgreSQL:** страница = 8KB, каждая страница хранит сотни ключей. Высота дерева для 50 млн строк = 3-4 уровня. Значит любой поиск = 3-4 чтения страниц.

Почему листовые страницы B+ Tree связаны в список?

Составные индексы и порядок столбцов

Запрос `WHERE status = 'active' AND created_at > '2024-01-01'` - два условия. Можно создать два отдельных индекса, но PostgreSQL скорее всего выберет один. Лучше создать **составной индекс** `(status, created_at)` - и тогда оба условия используются за одно сканирование.

Ключевое правило составного индекса: **prefix rule**. Индекс `(a, b, c)` работает для запросов по `(a)`, `(a, b)`, `(a, b, c)`. Но запрос только по `(b)` или `(c)` индекс не использует - нет точки входа в дерево.

**Cardinality первой колонки** - важный фактор при выборе порядка. Поле с высокой кардинальностью (много уникальных значений) как первый ключ сильнее фильтрует данные. Но если запрос всегда фильтрует по обоим полям - порядок менее критичен.

**Сколько индексов создавать?** Каждый индекс замедляет INSERT/UPDATE/DELETE (нужно обновлять B-Tree). Правило: индекс создаётся под конкретный медленный запрос, а не "на всякий случай". Смотрите `pg_stat_user_indexes` - неиспользуемые индексы видны там.

Индекс создан на (country, city, street). Какой запрос его использует?

Covering Index

Обычный индекс возвращает heap tid, затем база идёт в основную таблицу за данными - это **heap fetch**. Каждый heap fetch = случайное чтение диска. При большом количестве строк это дорого. **Covering Index** содержит все нужные запросу колонки прямо в индексе, heap fetch не нужен.

В PostgreSQL covering index создаётся через `INCLUDE`. Разница с добавлением колонки в ключ: колонки из INCLUDE не участвуют в сортировке и поиске по индексу, они просто хранятся в листовых страницах как payload.

**Visibility Map:** Index Only Scan работает идеально только если страница помечена как all-visible в visibility map (т.е. все строки видимы всем транзакциям). Иначе PostgreSQL всё равно сходит в heap для проверки видимости. VACUUM обновляет visibility map.

Чем INCLUDE отличается от добавления колонки в ключ индекса?

Index-Only Scan

**Index Scan** vs **Index Only Scan** - принципиальная разница. Index Scan: находим tid в индексе, идём в heap за строкой. Index Only Scan: все нужные данные в индексе, heap не трогаем. При высокой нагрузке Index Only Scan может быть в 10-100 раз быстрее.

**Bitmap Index Scan** - четвёртый тип. Применяется когда запрос возвращает много строк (низкая selectivity, но индекс всё равно быстрее seq scan). PostgreSQL сначала строит bitmap совпавших страниц из индекса, затем читает heap страницы в порядке их физического расположения - снижая случайные I/O.

Запрос SELECT amount FROM orders WHERE order_id = 42. Индекс: PRIMARY KEY (order_id) INCLUDE (amount). Какой scan будет выбран?

Index Bloat и обслуживание

После миллиона UPDATE и DELETE индекс превратился в 8GB при таблице в 2GB. Это **index bloat** - мёртвые версии строк накапливаются в B-Tree страницах, не освобождаясь автоматически. Запросы замедляются, потому что читают страницы с мусором.

Причина: PostgreSQL использует MVCC - старые версии строк не удаляются сразу. VACUUM убирает мёртвые кортежи из heap, но в B-Tree страницы помечаются как доступные для повторного использования - они не возвращаются ОС и не уменьшают файл.

**Fillfactor** - проактивная защита от bloat при UPDATE-heavy таблицах. По умолчанию B-Tree заполняет страницы на 100%. При fillfactor=70 оставляет 30% свободного места - UPDATE может обновить строку на той же странице (HOT update), не создавая новую версию в индексе.

**Автовакуум и индексы:** autovacuum убирает мёртвые кортежи и обновляет visibility map. Если autovacuum не справляется (много writes), индекс bloat растёт. Мониторьте `pg_stat_user_tables.n_dead_tup` - если > 10-20% от live строк, нужна ручная VACUUM.

После REINDEX CONCURRENTLY размер индекса уменьшился с 8GB до 1GB. Что означает это расхождение?