Медленный INSERT в таблицу InnoDB со случайным значением столбца PRIMARY KEY

Для своего сайта я использую PHP API для Flickr ( http://www.flickr.com/services/api/ ). Этот API предоставляет несколько полезных методов для получения фотографий в районе определенных GPS-позиций.

Вызов методов API выглядит как URL с определенными параметрами, такими как широта, долгота, ключ API, радиус, сортировка и т.д. Скажем, это будет выглядеть как http://api.flickr.com/method?lat=0.0&lon=0.0&radius=10

Мой сайт делает более 200 000 обращений к API для генерации нескольких страниц с фотографиями из Flickr. Это довольно сильное давление на API, поэтому я создал кэш результатов в базе данных mySQL.

Упрощенная схема таблицы InnoDB с кэшем такова:

char(32) request
datetime expires // 2-3 days
text     response // serialized data from API response

где request является PRIMARY KEY и представляет собой MD5 хэш URI запроса. Остальные поля довольно просты :)

Проблема возникает, когда таблица становится достаточно большой, скажем, более 100 000 строк. Новые INSERT'ы занимают до 2 секунд (и до 6 (!) секунд при 1,000,000 строк).

Насколько я понимаю, проблема в PRIMARY INDEX и движке InnoDB. Каждый раз, когда вставляется новый запрос, движок InnoDB перестраивает древовидный индекс и перемещает данные, потому что MD5(request) - это действительно случайное значение.

Итак... Вопрос в том, есть ли лучший способ кэшировать такие запросы? Или, может быть, мне стоит перейти на движок MyISAM? Или, может быть, мне стоит попробовать псевдо-разделение и создать несколько таблиц для решения проблемы? А может просто использовать не BTREE, а HASH индекс?

Любые идеи приветствуются!

Edit:

Хорошо, я попытался изменить таблицу, как предложили Furicane и Johan, но все еще не повезло - INSERTs занимает до 3 секунд. В настоящее время поле request стало обычным неуникальным индексом, а новый столбец id был добавлен как PRIMARY KEY с автоматическим инкрементом. Также я попытался добавить 4 раздела на эту таблицу с теми же результатами.

Я думаю, что индекс на поле request все еще является узким местом. Единственный способ, который я сейчас вижу, это определить все возможные параметры, добавить их как столбцы в таблицу и затем создать индекс на них.

Есть другие идеи? :)

Edit 2:

Salman A в комментариях ниже сказал, что его аналогичная таблица работает намного лучше (~0.03 для insert). Возможно, проблема в IO нагрузке на систему. Хотя я не вижу высокой нагрузки на нее.

iostat результаты:

avg-cpu:  %user   %nice %system %iowait  %steal   %idle
          22.94    0.71    8.42    8.50    0.00   59.43

Device:            tps   Blk_read/s   Blk_wrtn/s   Blk_read   Blk_wrtn
sda              38.01       151.04       114.32 1383655437 1047309046

iotop результаты:

Total DISK READ: 152.91 K/s | Total DISK WRITE: 197.67 K/s

С mySQL на вершине списка как для записи, так и для чтения. Может быть, мои диски почти мертвы? Как я могу проверить производительность дисков?