recherche avec php/mysql

bonjour;
je veux rechercher des données sur ma BD, cette derniere contient plus d'un million d'enregistrement...la recherche est devenue tres tres tres lourde meme elle depasse le time max de l'execution donc je l'ai changé dans le fichier"php.ini"
comment puis je faire pour accelerer cette recherche,notons que je voulais l'indexer mais je sais pas comment utiliser l'index dans ma recherche.
aussi..
je voulais faire une recherche intuitive, alors j ai fais
select ma_colone from ma_table where ma-colone LIKE '%$recherche%';
or ce n'est pas vraiment de l'intuitive.
Merci de me donner quelques idées.

travailler sur la structure de la table si ce n'est pas deja fait
- (ne pas trop utiliser les type TEXT, mais plutot les remplacer par des VARCHAR ou des ENUM quand tu peux. utiliser les DATETIME.

utiliser la pagination (LIMIT 0,20) avec des page (1, 2, 3... 10...) pour ne pas afficher tous les resultats

utiliser sql serveur de Microsoft, parce qu'une table avec plusieurs millions d'entrées au bout d'un moment ca commence a faire vraiment beaucoup...

Bonjour;
merci pour votre réponse
au niveau de ma BD j'utilise que des varchar et quelques INT
aussi,j'affiche mes resultats en utilisant la pagination
et j'utilise MYsql...
Voila.