À partida a posição dos dados numa tabela é indiferente. O importante, é teres em consideração os INDEX´s que defines, tais como certas propriedades que caracterizam determinado campo. Um campo único, chaves primárias, etc... são formas de indexação interna dos dados que resultarão numa performance superior quando considerado o tempo de acesso.
O tempo de concretização de uma query começa a ser importante quando se tratam de composições de diversas querys. Especial atenção aos JOIN´s, pois são estes que conseguem colocar um load sobre uma tabela imenso. Por vezes é preferível fazer subdivisões de JOIN´s, para não colocar tudo numa só query, tornando o processo total de selecção de dados mais eficiente, embora tendo mais linhas de código.
Last, but not least, é importantíssimo o hardware sobre o qual corre o servidor de MySQL, e a configuração orientada para determinado processo. O servidor MySQL deverá ser capaz de criar várias threads simultâneas, distribuindo-as pelos CPU´s em ambientes SMP. Será importante também averiguar até que ponto criar caches de querys frequentes na RAM, será preferível.
Ainda para concluir, existem diversos tipos de tabelas, com diferentes vantagens e desvantagens. As mais importantes e vulgares são o MyISAM, InnoDB e MEMORY. No fundo, InnoDB será uma boa escolha para tabelas com muitos indexes e frequentemente acedidas cuja integridade dos dados é tão importante quanto o rápido acesso a eles, MyISAM é o ideal para "storage", onde existe bastante segurança de dados, e pouca utilização de recursos e MEMORY é perfeita para alocar em memória a tabela, e assim aproveitar os seeks diminutos e elevada largura de banda deste interface, tendo e conta no entanto que a um mero shutdown, todos os dados são perdidos (utilizada sobretudo para SESSION´s por exemplo, ou outros dados descartáveis).
Verás que uma optimização da estrutura de dados por vezes é muito mais importante que optimizações ao nível de PHP. É exactamente a estrutura de dados que por vezes origina "bottlenecks" em sites de imensos acesso, criando depois a dependência em hardware de grande capacidade, por vezes para tarefas não muito complexas.