[Clarence]

Ett BTREE index är nog vad du har om du inte vet vad du har för index. Undantaget jag vet om med MySQL är om du använder innodb och har klustrade index.

Det låter som om du kan ha nytta av att öka på key buffer size, förutsatt att du använder myisam.

Annars kan det också vara så att själva datahämtningen tar väldig tid om du har en väldigt fragmenterad tabell. Testa att köra en optimize på tabellen.