Что такое индекс в БД?

Индекс — дополнительная структура данных, ускоряющая поиск в таблице. Без индекса БД делает full table scan — перебирает все строки. С индексом находит нужную за O(log n).

CREATE INDEX idx_users_email ON users(email);
-- теперь SELECT * FROM users WHERE email = $1 летает

Под капотом — B-tree (по умолчанию). Индекс хранит отсортированные ключи со ссылками на строки таблицы. Минусы: занимает место на диске, замедляет INSERT/UPDATE/DELETE (нужно обновлять индекс). Поэтому не надо индексировать всё подряд — только колонки, по которым часто ищешь или JOIN-ишь.