Modifica il tuo file /etc/mysql/my.cnf e assicurati di allocare memoria sufficiente al pool di buffer InnoDB. Se si tratta di un server dedicato, probabilmente potresti utilizzare fino all'80% della memoria di sistema.
# Provide a buffer pool for InnoDB - up to 80% of memory for a dedicated database server
innodb_buffer_pool_size=614M
Le chiavi primarie sono B Trees, quindi gli inserimenti impiegheranno sempre tempo O(logN) e una volta esaurita la cache, inizieranno a scambiarsi come un matto. Quando ciò accade, probabilmente vorrai partizionare i dati per mantenere la velocità di inserimento. Vedi http://dev.mysql.com/doc/refman/ 5.1/it/partizionamento.html per maggiori informazioni sul partizionamento.
Buona fortuna!
