Индекс первичный... с auto_increment
вы меня запутали.... получается все правильно сделано, только вся проблема в сервере и кол-ве строк?

p.s. оперы на 1000мб, на кроне висят скрипты постоянно что то добавляющие в базу..