Сколько записей необходимо для того, чтобы индексация стала эффективной?

Количество записей, при котором индексация становится эффективной, зависит от конкретной базы данных, типа данных и запросов, которые будут выполняться.

Однако, как правило, рекомендуется начинать создавать индексы для таблицы, когда количество записей превышает несколько тысяч. Это позволяет ускорить выполнение запросов, улучшить производительность базы данных и снизить нагрузку на сервер.

При этом следует помнить, что создание слишком большого количество индексов также может негативно сказаться на производительности базы данных, поэтому необходимо балансировать количество индексов и их необходимость для конкретных запросов.

С какого количества записей индексация имеет смысл?
 
 С того момента, когда планировщик начал показывать приличную разницу, как только получаете прирост - используйте индексацию, не получаете - не используйте. 
 
Сделал выборку по определенному имени, вышло 75-90 мсек.

SELECT name FROM users WHERE name='Mike';

Добавил индекс CREATE INDEX name_idx ON users (name);

Выборка так и осталась в пределах 75-85 мсек.
 
 Вы сами задали вопрос и сразу же ответили на него...

С того количества, на котором планировщик решит применять индекс, а это зависит от множества переменчивых факторов. Поэтому при проектировании БД нужно задумывать о сценариях её использования, а не о конкретных количествах строк.