Почему поиск с индексом быстрее и насколько? Сравни поиск без индекса, с B-tree индексом и с hash-индексом.

Без подходящего индекса поиск часто просматривает O(n) строк; B-tree сужает поиск за O(log n), Hash обычно ищет равенство с ожидаемой O(1) стоимостью. Но ускорение в секундах нельзя вывести только из этих оценок.

Нужно учесть число найденных строк k, чтение страниц таблицы, кеш, коллизии и стоимость сравнения. Индекс не избавляет от обработки всего результата, а для большой доли таблицы последовательное чтение может оказаться дешевле. B-tree также поддерживает диапазоны и порядок, Hash существенно уже по операциям. Сравнивайте EXPLAIN и фактическое время на характерных данных. Нельзя обещать «в тысячу раз быстрее» без измерений и описания запроса.