Tenho um banco de dados com mais de 250 tabelas, existem tabelas com mais de milhões de registros e quando preciso procurar ou alterar algum desses registros, leva bastante tempo, o que acaba deixando a experiência bem ruim para o usuário.

A tabela Clientes tem mais de 50 milhões de registros. Essa tabela fica em produção 24 horas por dia, numa média de 200 *queries*/min em certas horas do dia. Sempre que preciso procurar um cliente, existe uma forma mais rápida, que é procurando pela chave primária da tabela, mas nem sempre tenho a possibilidade de saber o ID de um cliente de cor. Nesses casos, utilizo uma busca parcial pelo nome (usando o operador [`LIKE`][1]), ou seja, procurando por `Dar`, ele me retorna:

    Darth Vader
    Darcisio Araujo
    Darlene Silva
    [...]

Claro, além de só o nome, existem mais filtros que possam ser aplicados na mesma *query*.  Das duas formas apresentadas, procurar pelo Nome acaba demorando bastante em certos casos. 

 - O que fazer para otimizar a velocidade das consultas?
 - O que costuma deixar as consultas lentas? (além de ter milhões de registros na tabela, acredito que existam más práticas que deixam-as ainda menos performáticas)

  [1]: http://www.w3schools.com/sql/sql_like.asp