Indexing is on but my understanding is that it only help reading, not writing on the DB
Try taking a look at http://kevin.vanzonneveld.net/techblog/article/improve_mysql... , which suggests some things you can try. This might be a question better suited for StackOverflow, by the way.