主キーは、データが実際に保存されるシーケンスとしてよく使用されます。主キーがインクリメントされる場合、データは単に追加されます。主キーがランダムである場合、それは、新しい行を適切な順序にするために既存のデータを移動する必要があることを意味します。基本的な（主キーではない）インデックスは、通常、コンテンツがはるかに軽く、オーバーヘッドを抑えて高速に移動できます。
私はこれが他のDBMSにも当てはまることを知っています。私は、MySQLがこの点で同様に機能すると思い切って推測します。
更新
以下のコメントで@BillKarwinが述べているように、この理論はMyISAMテーブルには当てはまりません。フォローアップ理論として、以下の@KevinPostlewaiteの回答（彼は削除されました）を参照します。問題は、主キーにAUTO_INCREMENTがないことです。これは一意である必要があります。 AUTO_INCREMENTを使用すると、値が増分であることが保証されているため、値が一意であるかどうかを簡単に判断できます。ランダムな値の場合、この決定を行うために実際にインデックスをたどるのに時間がかかる場合があります。