Индексы: зачем нужны и как ускоряют

Индекс — это отсортированная структура, которая превращает полный перебор в быстрый поиск.

Индекс — дополнительная структура данных (обычно B-tree), хранящая значения колонки в отсортированном виде со ссылками на строки. Он даёт поиск за время порядка log(N) вместо перебора всех N строк.

Аналогия: указатель в книге

Чтобы найти слово в книге без указателя, придётся пролистать все страницы — это полный перебор (full scan). Алфавитный указатель в конце сразу приводит на нужную страницу. Индекс в БД — тот самый указатель: он отсортирован, поэтому поиск идёт делением пополам, а не перебором.

Видим разницу через план запроса

В SQLite (как и в Postgres) план показывает, читается ли таблица целиком. Сначала — без индекса.

CREATE TABLE users(id INTEGER PRIMARY KEY, email TEXT, name TEXT);
INSERT INTO users(email,name) VALUES ('a@x','Аня'),('b@x','Борис'),('c@x','Вика');

EXPLAIN QUERY PLAN
SELECT * FROM users WHERE email = 'b@x';

Вывод:

QUERY PLAN
`--SCAN users

SCAN users — «прочитать всю таблицу». На трёх строках неважно, на миллионе — катастрофа. Добавим индекс на email.

CREATE TABLE users(id INTEGER PRIMARY KEY, email TEXT, name TEXT);
INSERT INTO users(email,name) VALUES ('a@x','Аня'),('b@x','Борис'),('c@x','Вика');
CREATE INDEX idx_users_email ON users(email);

EXPLAIN QUERY PLAN
SELECT * FROM users WHERE email = 'b@x';

Вывод:

QUERY PLAN
`--SEARCH users USING INDEX idx_users_email (email=?)

Теперь SEARCH ... USING INDEX — БД прыгнула прямо к нужному значению через индекс, не читая лишних строк. На больших таблицах это разница между миллисекундами и секундами.

Что индексировать

Колонки в WHERE (фильтры по равенству и диапазону).
Колонки в JOIN ... ON (внешние ключи).
Колонки в ORDER BY — отсортированный индекс позволяет отдать строки без отдельной сортировки.

Когда индекс НЕ работает (или вредит)

Функция/выражение на колонке. WHERE LOWER(email) = 'a@x' прячет колонку внутри LOWER() — индекс по «голому» email не подходит, БД снова делает SCAN (это разберём в следующем уроке про SARGable-условия).
Низкая селективность. Индекс по колонке пол (два значения) почти бесполезен: половину таблицы всё равно надо прочитать.
Запись. Каждый индекс надо обновлять при INSERT/UPDATE/DELETE — лишние индексы замедляют запись и занимают место. Индексы — это компромисс «быстрое чтение ценой медленной записи».

Итог

Индекс (B-tree) хранит значения отсортированно и даёт поиск ~log(N) вместо перебора N строк.
Индексируйте колонки из WHERE, JOIN, ORDER BY.
Индекс не спасает при функции на колонке и низкой селективности; лишние индексы замедляют запись.