Primære nøgler bruges ofte som den rækkefølge, hvori dataene faktisk lagres. Hvis den primære nøgle øges, tilføjes dataene simpelthen. Hvis den primære nøgle er tilfældig, vil det betyde, at eksisterende data skal flyttes for at få den nye række i den rigtige rækkefølge. Et grundlæggende (ikke-primær-nøgle) indeks er typisk meget lettere i indhold og kan flyttes rundt hurtigere med mindre overhead.
Jeg ved, at dette er sandt for andre DBMS'er; Jeg vil vove at gætte på, at MySQL fungerer på samme måde i denne henseende.
OPDATERING
Som angivet af @BillKarwin i kommentarerne nedenfor, ville denne teori ikke holde stik for MyISAM-tabeller. Som en opfølgningsteori vil jeg henvise til @KevinPostlewaites svar nedenfor (som han siden har slettet), at problemet er manglen på AUTO_INCREMENT på en PRIMÆR NØGLE - som skal være unik. Med AUTO_INCREMENT er det nemmere at bestemme, at værdierne er unikke, da de med garanti er trinvise. Med tilfældige værdier kan det tage noget tid at gå gennem indekset for at foretage denne bestemmelse.