Na maioria dos casos você pode estimar a performance contando buscas em disco. Para tabelas pequenas, normalmente você pode encontrar o registro com 1 pesquisa em disco (uma vez que o índice provavelmente está no cache). Par tabelas maiores, você pode estimar (usando indíces de arvores B++) que você precisará de: log(row_count) / log(index_block_length / 3 * 2 / (index_length + data_pointer_length)) + 1 buscas em disco para encontrar um registro.

No MySQL um bloco de índice tem geralmente 1024 bytes e o ponteiro de dados 4 bytes. Uma tabela de 500.000 registros com um índice com tamanho de 3 (inteiro médio) lhe dá: log(500,000)/log(1024/3*2/(3+4)) + 1 = 4 pesquisas.

Como o índice acima necessita cerca de 500,000 * 7 * 3/2 = 5.2M, (assumindo que os buffers de índices são carregados até 2/3, que é o normal) você provavelmente terá grande parte dos índices em memória e provavelmente precisará somente de 1 ou 2 chamadas para ler dados do SO para encontrar o registro.

Entretanto, para escritas, você precisará utilizar 4 requisições para encontrar onde posicionar o novo índice e normalmente 2 buscas para atualizar o índice e escrever o registro.

Perceba que o que foi dito acima não significa que sua aplicação perderá performance por N log N! Como tudo é armazenado no cache de seu SO ou do servidor SQL as coisas começarão a ficar um pouco mais lentas quando as tabelas começarem a crescer. Quando os dados se tornam muito grandes para o cache, as coisas começarão a ficar bem mais lentas até que suas aplicações estejam limitadas a buscas em disco (o que aumenta em N log N). Para evitar isto, aumente o cache de índice quando os dados crescerem. See Secção 5.5.2, “Parâmetros de Sintonia do Servidor”.