Verificar usuário

Olá

Antes, devo mencionar que busquei na net essa solução, mas não achei nada. Talvez não estivesse usando os termos corretos na pesquisa.

O que preciso é bastante simples: verificar se um usuário, cadastrado no DB Mysql já existe, em tempo real. Algo assim:

A mensagem abaixo apareceria, talvez, quando o foco saísse desse campo ou algo similiar.

Se alguém puder me indicar um tutorial para tal, eu fico grato.