Cita: entonces me imagino que tendre que particionar esa tabla mediante indices para que sea mas rapida la busqueda de esas foreing keys no?
¿Por qué?
De todos modos, desde el momento en que esas columnas sean FK, ya habrá índices defnidos en ellas... ¿para qué quieres crear más índices? Los índices debe crearse según reales encesidades, no "por si"... ya que afectan la performance de las inserciones/actualizaciones.
De hecho, si los valores buscados están en esos índices que administran las FK, la tabla ni siquiera se lee. MySQL leerá el índice solamente...