Оптимизация таблицы Mysql

Есть таблица

CREATE TABLE IF NOT EXISTS `ps_category` (

`id_category` int(10) unsigned NOT NULL AUTO_INCREMENT,

`id_parent` int(10) unsigned NOT NULL,

`level_depth` tinyint(3) unsigned NOT NULL DEFAULT '0',

`nleft` int(10) unsigned NOT NULL DEFAULT '0',

`nright` int(10) unsigned NOT NULL DEFAULT '0',

`active` tinyint(1) unsigned NOT NULL DEFAULT '0',

`date_add` datetime NOT NULL,

`date_upd` datetime NOT NULL,

`position` int(10) unsigned NOT NULL DEFAULT '0',

PRIMARY KEY (`id_category`),

KEY `category_parent` (`id_parent`),

KEY `nleftright` (`nleft`,`nright`)

) ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT=1518 ;

Индексы

PRIMARY BTREE Да Нет id_category 1561 A

category_parent BTREE Нет Нет id_parent 86 A

nleftright BTREE Нет Нет nleft 1561 A

nright 1561 A

В ней примерно 1,5тис записей, но по непонятним причинам есть проблемка, запись в таблицу длится очень долго, 10 и более секунд. Чтение проходит нормально. Пример запроса которий выполняется:

UPDATE ps_category SET nleft = 267, nright = 268 WHERE id_category = 399 LIMIT 1

В процессах сначала идет Updating item (бысто) а потом он висит долго со статусом freeing items.

Задание - решить в чем проблема. Доступ к серверу не даю, предоставляю по запросу все конфиги итп, вы пишите что сделать, я делаю и смотрим на результат. Оплата по факту. Приемлемый результат - 2-3 секунды. Желаемый - менее 1с.