Con InnoDB no hay otra forma, solo utilizar LIKE
Por ejemplo:
si quiere buscar en una sola columna:
Código PHP:
SELEC nombre, ap, am FROM usuarios WHERE nombre LIKE '%nombre a buscar%'
si quieres buscar en varias columnas
Código PHP:
SELEC nombre, ap, am FROM usuarios WHERE CONCAT(nombre,ap,am) LIKE '%nombre o ap o am a buscar%'
Saludos!
Espero que te sirva