Qual a melhor forma de guardar mensagens(cx de entrada) no banco?

Boa tarde pessoal!

Estou com um “pequeno” problema! Estou fazendo um serviço WEB de mensagens (tipo e-mail), e preciso saber a melhor forma de montar a caixa de entrada no banco de dados, atualmente eu criei uma tabela que guarda todas as mensagens, ate ai tudo bem, porém será coisa de milhares de usuários, e um select numa tabela com tamanho conteúdo vai demorar muito, já que um usuário pode ter várias mensagens (infinitas), ouvi falar em colocar esses dados em colunas na própria tabela usuários (teoricamente usado pelo Facebook), facilitando o select, já que os usuários são únicos e sua caixa de entrada também, porém não encontro um modo de fazer isso, alguém pode me ajudar com a melhor forma de resolver isso?