За счет чего увеличивается скорость выборки при использовании индексов

Что проверяют

Понимаете ли вы механику, а не только формулу «индекс ускоряет поиск»: почему несколько чтений страниц вместо миллиона строк и когда база индексом всё равно не воспользуется. Следом обычно показывают запрос и просят объяснить план из EXPLAIN.

Как отвечать

Ускорение складывается из нескольких механизмов:

• B+-дерево с большим ветвлением: база читает данные страницами (8 КБ в PostgreSQL, 16 КБ в InnoDB), а в одну страницу индекса помещаются сотни ключей. Дерево получается неглубоким: три-четыре уровня покрывают миллионы строк, и поиск по равенству стоит несколько чтений страниц вместо полного сканирования таблицы;
• упорядоченность: ключи в листьях отсортированы и связаны между собой, поэтому диапазон BETWEEN читается подряд, а ORDER BY ... LIMIT обходится без сортировки;
• покрывающий индекс: если все нужные колонки есть в индексе, в таблицу ходить не надо. В PostgreSQL это index-only scan и INCLUDE, в MySQL покрывающий вторичный индекс;
• компактность: индекс меньше таблицы и лучше держится в буферном кэше.

Назовите и цену обращения к таблице. Найдя ключ, база по ссылке читает саму строку, и это случайный доступ. В InnoDB вторичный индекс хранит первичный ключ, и за строкой идёт второй спуск по кластерному индексу. Поэтому при низкой селективности планировщик выбирает последовательное сканирование, и это правильно.

Для Java-стека свяжите с практикой: индекс создаётся миграцией Flyway или Liquibase, в JPA его можно описать через @Table(indexes = @Index(columnList = "email")), а SQL от Hibernate берут из лога и прогоняют через EXPLAIN ANALYZE. И помните, что PostgreSQL не создаёт индекс на внешний ключ сам, в отличие от InnoDB.

Где спотыкаются

Говорят, что индекс «сортирует таблицу» или что база «делает бинарный поиск по данным». Таблица остаётся как есть, ускоряет отдельная структура, по которой идёт спуск.

Уверены, что индекс применяется всегда. Функция над колонкой, неявное приведение типа, LIKE '%x' или устаревшая статистика оставляют его без дела.

Забывают, что каждый индекс замедляет INSERT и UPDATE и занимает место, так что индекс под редкий отчёт может стоить дороже, чем экономит.