Em geral, minha estratégia de indexação seria algo assim (estou usando o SQL Server exclusivamente por enquanto - adapte-se ao seu próprio sistema de banco de dados conforme necessário):

• 
  escolha um bom chave de cluster - não um GUID, não um VARCHAR(250) ou algo - um bom chave de agrupamento é estreita, única, estável, sempre crescente - algo como uma INT IDENTITY é perfeito. Torna esta sua chave primária clusterizada -> fornece seu primeiro índice na tabela
  
• 
  para qualquer coluna que está sendo usada como chave estrangeira em outra tabela - adicione um índice. Pode ser um índice de coluna única - ou pode ser um índice composto - o que funcionar melhor para o seu caso. É importante que a coluna de chave estrangeira seja a primeira coluna nesse índice (se você estiver usando um índice composto) - caso contrário, os benefícios para o JOIN 's ou para verificar a integridade referencial não estará disponível para o seu sistema
  

E é isso por enquanto.

Então:execute seu sistema - observe e meça - estabeleça uma linha de base. O aplicativo é rápido o suficiente? Se sim -> acabou - vá para casa e aproveite seu tempo livre.

Caso contrário:comece a coletar dados e indicações de por que o aplicativo não é rápido o suficiente. Veja por exemplo coisas como os DMVs no SQL Server que informam sobre as consultas com pior desempenho ou o índice ausente DMV . Analise esses. Veja o que você pode melhorar. Adicione um índice por vez e novamente:observe, meça, compare com sua linha de base.

Se você tiver melhora -> deixe esse índice no lugar e essa medida é sua nova linha de base. Enxágue e repita até que você (e seus usuários) estejam satisfeitos com o desempenho do aplicativo (e então vá para casa e aproveite seu tempo livre).

A indexação excessiva no SQL Server pode ser pior do que não ter nenhum índice. Não comece com muitos índices para começar! Apenas estabeleça bom PK clusterizado e índices não clusterizados de chave estrangeira - isso é tudo - então observe, meça, otimize e repita esse ciclo.