CREATE TABLE `itemsposts` (
  `id` int(11) NOT NULL auto_increment,
  `parent_id` int(11) NOT NULL default '0',
  `category_id` int(11) NOT NULL default '0',
  `type_id` int(11) NOT NULL default '0',
  `status_id` int(11) NOT NULL default '0',
  `url` char(255) NOT NULL default '',
  `order` int(11) NOT NULL default '0',
  `user` char(16) NOT NULL default '',
  `date` datetime NOT NULL default '0000-00-00 00:00:00',
  `edit` datetime NOT NULL default '0000-00-00 00:00:00',
  PRIMARY KEY  (`id`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8;

Статистика ряда.
Длина ряда 854.
Размер ряда 901 байт.

Это как так? Если про суммировать никак не получится 901.

utf-8 = 2 байта на символ

Добавлено через 4 минуты и 59 секунд
и, да, про служебную информацию не забываем

Ясно :(

А для оптимизации можно задать для колонки другое сравнение, да? Например в url у меня будут только определенные символы

о боже
что ты собрался оптимизировать?!

В таблице несоклько миллионов записей... и она весит пару гигабайт.

Ничего страшного в этом нет. Бывает и больше.

Скорость обращение не велика, даже когда where по первичному ключу.

Значит, у тебя криво настроен сервер.

Следует понимать такие основополагающие вещи, что БД спроектирована специально для того, чтобы скорость выборки не зависела от размера базы.
А понимая - искать другие, более осмысленные варианты решения проблем. А ещё лучше - сразу озвучивать существующие проблемы, а не вопросы, вызванные смутными догадками.

Скорость выборки по первичному ключу невелика? Прекрасно. Сколько конкретно?
Действительно ли проблема именно в этой выборке, а не в   общей загруженности сервера?

Сервер не загружен. Посылается только один запроса. В таблице структура которой показана в первом посте. Выборка одного элемента по id.
При количестве строк около 2М время около 0.01с.
При количестве строк около 16М время около 2с.

Машина, обычный десктоп с поставленным на нее debian etch.

explain делал, что говоришь:
?
тот факт, что в Where условие с участием первичного ключа, ещё ничего не означает.
тем более, что 

выглядит странно.

Есть у меня подозрение, что индекс банально не помещается в память.