Где mc хранит индексы поиска?

Ядро кеширует пути к файлам (насколько я понимаю, полную трассировку инодов), и повторные заходы по тем же самым маршрутам идёт очень быстро.

А само ядро только в памяти хранит? Просто есть переносной винт с кучей не очень больших файлов и хотелось бы как-то быстро искать на всех компьютерах.

А само ядро только в памяти хранит?

в памяти.

Помогут ли службы индексации? Не знаю. Обычно они вообще не установлены и поэтому не помогут.

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

Помогут ли службы индексации?

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