Как индексы в базе данных ускоряют поиск и почему поиск по индексу быстрее полного сканирования
Что проверяют
Понимаете ли вы механику, а не только лозунг «индекс ускоряет». Интервьюер ждёт слов про дерево, логарифм и страницы на диске, а следом обычно спрашивает, почему база иногда игнорирует индекс и всё равно читает таблицу целиком.
Как отвечать
Начните с того, что делает полное сканирование: база читает все страницы таблицы и проверяет условие для каждой строки, это O(n). Индекс сокращает эту работу:
- B-tree: отсортированное сбалансированное дерево. Узел занимает страницу (в PostgreSQL 8 КБ) и хранит сотни ключей, поэтому даже для ста миллионов строк глубина дерева три-четыре уровня. Поиск это O(log n) и несколько чтений страниц вместо сотен тысяч;
- ссылка на строку: в листе лежит ключ и адрес строки (в PostgreSQL это
ctid), по нему база забирает из таблицы только нужные строки; - порядок: ключи уже отсортированы, поэтому индекс обслуживает диапазоны и
ORDER BYбез отдельной сортировки; - покрывающий индекс: если все нужные колонки есть в индексе (
INCLUDE), выполняется Index Only Scan, обычно без похода в таблицу.
Обязательно скажите про планировщик. Индексный доступ читает страницы вразброс, и если условию соответствует заметная доля таблицы, последовательное чтение дешевле. Поэтому на неселективном условии вы увидите Seq Scan, и это правильное решение. Проверяется всё через EXPLAIN ANALYZE: в psql или прямо из Django через QuerySet.explain().
И цена: индекс занимает место и обновляется при каждой записи, так что вставки и обновления становятся медленнее.
Где спотыкаются
Говорят, что индекс «лежит в памяти». Он лежит на диске, как и таблица, просто его горячие страницы чаще оказываются в буферном кэше.
Считают, что индекс используется всегда, если он есть. Функция над колонкой, LIKE '%текст' или несовпадение типов в условии делают его бесполезным.
Не знают правила левого префикса у составного индекса: индекс по (a, b) рассчитан на запросы по a или по паре, а запрос только по b чаще всего пойдёт мимо него.