Primární klíče se často používají jako sekvence, ve které jsou data skutečně uložena. Pokud je primární klíč inkrementován, data se jednoduše připojí. Pokud je primární klíč náhodný, znamenalo by to, že existující data musí být přesunuta, aby se nový řádek dostal do správné sekvence. Základní index (neprimární klíč) má obvykle mnohem lehčí obsah a lze se s ním pohybovat rychleji s menší režií.
Vím, že to platí pro ostatní DBMS; Troufnul bych si odhadnout, že MySQL v tomto ohledu funguje podobně.
AKTUALIZACE
Jak uvedl @BillKarwin v komentářích níže, tato teorie by neplatila pro tabulky MyISAM. Jako následnou teorii bych odkazoval na níže uvedenou odpověď @KevinPostlewaite (kterou je mezitím smazán), že problémem je absence AUTO_INCREMENT na PRIMÁRNÍM KLÍČI - který musí být jedinečný. S AUTO_INCREMENT je snazší určit, že hodnoty jsou jedinečné, protože je zaručeno, že budou přírůstkové. U náhodných hodnot může chvíli trvat, než se index skutečně projde, aby bylo možné toto určení provést.