Vous devez soit utiliser des index de texte intégral (vous avez dit que vous ne pouviez pas), concevoir vous-même une recherche de texte intégral ou décharger la recherche de MySQL et utiliser Sphinx/Lucene. Pour Lucene, vous pouvez utiliser l'implémentation Zend_Search_Lucene de Zend Framework ou utiliser Solr.
Les index normaux dans MySQL sont des arbres B+, et ils ne peuvent pas être utilisés si le début de la chaîne n'est pas connu (et c'est le cas lorsque vous avez un caractère générique au début)
Une autre option consiste à implémenter la recherche par vous-même, en utilisant la table de référence. Divisez le texte en mots et créez une table contenant le mot, record_id. Ensuite, dans la recherche, vous divisez la requête en mots et recherchez chacun des mots dans la table de référence. De cette façon, vous ne vous limitez pas au début de tout le texte, mais uniquement au début du mot donné (et vous ferez de toute façon correspondre le reste des mots)
