Søgehastighed og index

Jeg arbejder på en søgemaskine, og jeg kan søge gennem 3 mio records på 2 sekunder hvilket er alt for langsomt (antallet af records kommer op over 60 mio). Jeg HAR index på tabellen, og jeg henter kun minimal data (et ID nummer på 5 cifre).

Er der ingen måde hvorpå man kan forbedre dette?

(Ved søgning på samme ord to gange i træk er søgehastigheden under 0,01 sek pga. MySQL cache, men det kan vel ikke udnyttes?)