MySQL: UPDATE too slow

The following is a benchmark of a series of queries I have to run. As you can see, the UPDATEs are significantly slower than the other queries. What can I do to speed them up?

0.0002  LOCK TABLE category WRITE; 
0.0004  
        SELECT
            @myLeft := left_id
        FROM
            category
        WHERE
            `amazon_browse_node_id` = 2675;

0.0184  UPDATE category SET right_id = right_id + 2 WHERE right_id >开发者_开发技巧 @myLeft; 
0.0161  UPDATE category SET left_id = left_id + 2 WHERE left_id > @myLeft; 
0.0007  INSERT INTO category(`name`, `amazon_browse_node_id`, `category_seo_friendly_url`, `left_id`, `right_id`) VALUES('Training', 2697, 'training-2697/', @myLeft + 1, @myLeft + 2); 
0.0004  UNLOCK TABLES;

This problem is related to the following problems (and my attempt at a solution), which I also posted here in SO:

1. MySQL: nested set is slow?
2. MySQL trigger in order to cache results?

UPDATE:

CREATE TABLE IF NOT EXISTS `category`
  (
     `category_id`               INT(11) NOT NULL AUTO_INCREMENT,
     `name`                      CHAR(255) DEFAULT NULL,
     `category_seo_friendly_url` CHAR(255) DEFAULT NULL,
     `left_id`                   INT(11) DEFAULT '1',
     `right_id`                  INT(11) DEFAULT '2',
     PRIMARY KEY (`category_id`),
     UNIQUE KEY `seo_friendly_url_UNIQUE` (`category_seo_friendly_url`),
     KEY `category_id` (`category_id`),
     KEY `left_id` (`left_id`),
     KEY `right_id` (`right_id`)
  )

You probably have an index on the table which

1. Speeds up SELECT queries
2. Slows down UPDATE queries since the index needs to be updated

INSERT statements only add one record which means is faster than updating N records.

The only thing that could help is proper keys on right_id and left_id. Even then, updates are just slower than selects or inserts. There is not a lot you can do about it.