Ну как минимум чтение индекса при поиске обходится намного дешевле, чем чтение всей таблицы. Банально меньшее кол-во данных надо прочитать. Тем более индексы - упорядоченная структура, для поиска данных по какой-то колонке не надо читать весь индекс. Можно сравнить b-tree индекс с алфавитным указателем - чтобы найти в нём ссылку на какое-то слово, не надо читать весь алфавитный указатель, надо просто перейти к нужной букве.
Но да, не каждый индекс может быть полезен. Есть такое понятие, как селективность индекса. Условно, индекс по полю "пол" реально может не давать пользы, так как даже при использовании индекса так и так надо будет прочитать половину записей в таблице и может быть быстрее просто прочитать всю таблицу.
Рекомендую прочитать книги, например, я читал "Настройка производительности MySQL" Нихтера. Тогда всё станет ясно.