Как индексы в базе данных ускоряют поиск и почему поиск по индексу быстрее полного сканирования

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

Понимаете ли вы, что происходит на уровне страниц на диске, а не только помните фразу «O(log n) против O(n)». Следом почти всегда спрашивают, когда база сама откажется от индекса и выберет полное сканирование, и как это увидеть в EXPLAIN.

Как отвечать

Для PHP-разработчика основной контекст это MySQL с InnoDB или PostgreSQL, поэтому объясняйте на B+-дереве:

• страницы: база читает не строки, а страницы (в InnoDB по умолчанию 16 КБ). Полное сканирование читает все страницы таблицы, индекс приводит к нужной за несколько переходов;
• высокое ветвление: в узле помещаются сотни ключей, поэтому высота индекса на миллионы строк обычно три или четыре уровня. Верхние уровни почти всегда лежат в буферном кеше, и поиск стоит пары чтений с диска;
• упорядоченность: ключи отсортированы, поэтому индекс обслуживает и равенство, и диапазоны, и ORDER BY без отдельной сортировки;
• кластерный индекс InnoDB: таблица физически лежит в дереве первичного ключа, а вторичный индекс хранит значение PK. Поиск по вторичному индексу это два спуска по деревьям, если индекс не покрывающий. Покрывающий EXPLAIN помечает как Using index.

Дальше объясните, когда полный скан выигрывает. Если запрос возвращает заметную долю таблицы, случайные чтения по индексу обходятся дороже одного последовательного прохода, и оптимизатор это учитывает. В MySQL полный скан виден как type: ALL, в PostgreSQL как Seq Scan. Цену индекса тоже назовите: место на диске и замедление каждого INSERT, UPDATE, DELETE.

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

Объясняют всё одной асимптотикой. Тогда хэш-индекс с O(1) был бы лучше всегда, а это не так: диапазоны и сортировку он не умеет.

Не знают про неявное приведение типов. В MySQL условие WHERE phone = 79001234567 по строковой колонке phone заставит сравнивать каждую строку как число, и индекс не используется. Значение нужно передавать строкой, например привязкой параметра с PDO::PARAM_STR.

Считают, что индекс по (last_name, first_name) поможет поиску по одному first_name. Составной индекс работает слева направо, а LIKE '%ov' с ведущим процентом не использует B-tree вовсе.