Большая таблица MyISAM работает медленно даже при одновременных вставках и обновлениях.

У меня есть таблица MyISAM с ~ 50 000 000 записей (задачи для поискового робота):

CREATE TABLE `tasks2` (
    `id` int(11) NOT NULL auto_increment,
    `url` varchar(760) character set latin1 NOT NULL,
    `state` varchar(10) collate utf8_bin default NULL,
    `links_depth` int(11) NOT NULL,
    `sites_depth` int(11) NOT NULL,
    `error_text` text character set latin1,
    `parent` int(11) default NULL,
    `seed` int(11) NOT NULL,
    `random` int(11) NOT NULL default '0',
    PRIMARY KEY  (`id`),
    UNIQUE KEY `URL_UNIQUE` (`url`),
        KEY `next_random_task` (`state`,`random`)
) ENGINE=MyISAM AUTO_INCREMENT=61211954 DEFAULT CHARSET=utf8 COLLATE=utf8_bin

Каждые несколько секунд выполняется одна из следующих операций (но никогда одновременно):

1. INSERT ... VALUES (500 строк) - вставляет новые задачи
2. ОБНОВЛЕНИЕ ... ГДЕ id IN (до 10 идентификаторов) - обновляет состояние пакета задач
3. SELECT ... WHERE (по индексу next_random_task) - загружает пакет задач для обработки

Моя проблема в том, что вставки и обновления выполняются очень медленно - порядка десятков секунд, иногда более минуты. Однако выбор происходит быстро. Почему это могло произойти и как повысить производительность?