Es conveniente definir un ID autoincrementable como clave de cada tabla?

[repara2]

La creación de índices no tiene nada que ver con los problemas que planteas.
El ID autoincremental se utiliza para IDENTIFICAR de forma definitica un registro.
Los índices tienen como objetivo acelerar las búsquedas y mantener la integridad de los datos.
Utilizar un auto_increment como índice no tiene sentido dado que incialmente, el id asignado será aleatorio y no relacionado con el contenido de la fila. Además, el campo auto_increment, estará siempre correctamente ordenado. Consulta la documentación del mysql_server al respecto.
Salu2