Busca em banco de dados grande

Tenho um banco de dados com mais de 75 mil registros, e quando faço uma busca, ele demora a carregar. alguém pode me ajudar com dicas de como pesquisar no banco de uma forma mais rápida?