Как устроен индекс в базе данных и почему он ускоряет поиск? Когда индекс не поможет?
Короткий ответ
- Основной тип — B-tree: сбалансированное дерево с отсортированными ключами
- Поиск за O(log n) вместо полного прохода таблицы
- Работает для равенства, диапазонов, сортировки и префиксов LIKE
- Составной индекс работает слева направо (leftmost prefix)
- Функция над колонкой или ведущий % в LIKE ломают использование индекса
- Индексы замедляют запись и занимают место
B-tree-индекс превращает полный перебор в спуск по дереву, но работает только при подходящей форме условия.
Как сказать вслух
пример ответаИндекс — это отдельная структура, чаще всего B-дерево, где значения колонки хранятся отсортированными со ссылками на строки. Вместо того чтобы читать всю таблицу, база спускается по дереву за логарифмическое число шагов. Индекс помогает при поиске по равенству, диапазонам и сортировке. Но он не сработает, если обернуть колонку в функцию, искать по LIKE с процентом в начале или фильтровать по второй колонке составного индекса без первой.
Подробный ответ
Основной ответ
B-tree — сбалансированное дерево с большим коэффициентом ветвления: узлы соответствуют страницам диска, в листьях лежат отсортированные ключи со ссылками на строки (или сами строки в кластерном индексе, как в InnoDB). Поиск, вставка и удаление — O(log n), а отсортированность листьев даёт эффективные диапазонные сканы и ORDER BY без сортировки. Составной индекс (a, b, c) применим для условий по a, по a+b, по a+b+c — но не по b или c отдельно. Индекс бесполезен при функции над колонкой (lower(email) без функционального индекса), LIKE с ведущим процентом, неявном приведении типов и при низкой селективности, когда оптимизатор справедливо выбирает полный скан. Каждый индекс — это цена на запись: каждое изменение строки обновляет все затронутые индексы.
Ключевые моменты
- Кластерный и вторичный индекс. В кластерном индексе листья содержат сами строки (InnoDB по первичному ключу). Вторичный индекс хранит ссылку, поэтому часто нужен дополнительный переход к строке.
- Покрывающий индекс. Если все нужные колонки есть в индексе, база отвечает из него без чтения таблицы (index-only scan) — это сильно быстрее.
- Leftmost prefix. Составной индекс используется только по левому префиксу колонок; порядок колонок при создании — осознанное решение.
- Селективность. Индекс по колонке с двумя значениями почти бесполезен: оптимизатор предпочтёт seq scan, и это правильно.
Практический контекст
В ежедневной работе это анализ EXPLAIN / EXPLAIN ANALYZE: почему запрос делает seq scan, какой индекс добавить, почему существующий не используется. Интервьюер часто даёт конкретный запрос и просит сказать, сработает ли индекс. Хорошо упомянуть и другие типы: hash, GIN для JSONB и полнотекстового поиска, BRIN для огромных таблиц с естественным порядком — это показывает глубину.
Частые ошибки
- «Повесим индекс на всё» — забывают про стоимость записи и место на диске
- Не знают правило левого префикса составного индекса
- Не могут объяснить, почему WHERE lower(email) = ... не использует обычный индекс по email