Първичните ключове често се използват като последователност, в която действително се съхраняват данните. Ако първичният ключ се увеличи, данните просто се добавят. Ако първичният ключ е произволен, това би означавало, че съществуващите данни трябва да бъдат преместени, за да се постави новият ред в правилната последователност. Базовият индекс (без първичен ключ) обикновено е много по-лек по съдържание и може да се мести по-бързо с по-малко разходи.
Знам, че това е вярно за други СУБД; Бих се осмелил да предположа, че MySQL работи по подобен начин в това отношение.
АКТУАЛИЗАЦИЯ
Както е посочено от @BillKarwin в коментарите по-долу, тази теория няма да е вярна за таблиците MyISAM. Като последваща теория бих се позовал на отговора на @KevinPostlewaite по-долу (който той оттогава е изтрил), че проблемът е липсата на AUTO_INCREMENT на PRIMARY KEY - който трябва да е уникален. С AUTO_INCREMENT е по-лесно да се определи, че стойностите са уникални, тъй като е гарантирано, че са нарастващи. При произволни стойности може да отнеме известно време за действително обхождане на индекса, за да се направи това определяне.
