Почему использование индексов ускоряет запросы в базе данных?
Что проверяют
Понимаете ли вы, что индекс это отдельная структура данных, и знаете ли его цену.
Как отвечать
Без индекса база вынуждена читать таблицу целиком и проверять условие на каждой строке: это O(n) по числу строк, а главное, это чтение с диска пропорционально размеру таблицы.
Индекс это отдельная упорядоченная структура (обычно B-дерево), хранящая значения колонки и ссылки на строки. Поиск по нему это спуск по дереву, то есть O(log n), а на практике три или четыре обращения даже для миллионов строк, потому что дерево очень ветвистое и верхние уровни лежат в памяти.
Ускоряется не только точный поиск:
- диапазоны (
BETWEEN,>,<), потому что листья дерева связаны и читаются подряд; - сортировка:
ORDER BYпо индексированной колонке не требует сортировки вовсе, данные уже упорядочены; - соединения: индекс на колонке внешнего ключа превращает цикл по внешней таблице из полного сканирования в точечный поиск;
- проверка уникальности: ограничение реализовано именно индексом;
- чтение только по индексу: если все нужные колонки есть в индексе, до самой таблицы дело не доходит.
Цена, которую обязательно надо назвать: каждый индекс это дополнительная запись при каждом INSERT, UPDATE и DELETE, плюс место на диске, плюс работа планировщику. Поэтому индекс на каждую колонку замедляет запись и не ускоряет чтение.
Когда индекс не сработает: функция или приведение типа над колонкой (WHERE upper(name) = ...), поиск по шаблону с ведущим процентом, низкая селективность (индекс по полу на большой таблице планировщик просто проигнорирует), очень маленькая таблица, где полное сканирование дешевле.
Где спотыкаются
Не могут назвать цену индексов при записи.
Считают, что индекс помогает любому условию с этой колонкой.
Не знают про составные индексы и порядок колонок в них.
Уверены, что база «сама решит» и планировщику не нужна статистика.