Para hacer un chat de ese tipo, necesitas tecnologias alternas que estan precisamente optimizadas para aplicaciones que funcionan en tiempo real, como lo es un chat y para eso se utiliza Node.JS.
Desafortunadamente conseguir un hosting con esta tecnologia es muy caro, entonces crear un chat con esas caracteristicas usando PHP y ajax, le va resultar muy pesado a tu servidor.
Lo que podrias hacer, es usar websockets, para esto puedes utilizar Ratchet de PHP:
http://socketo.me/docs/connections
Con esto ya no tienes que guardar los mensajes que los usuarios envien en la BD y luego hacer otra consulta para recuperarlos, sino que el websocket hara la gestion de estos mensajes y lo repplicara a todos los clientes conectados.
Para entender mejor esto te recomiendo leer sobre sockets.
Por supuesto esta es solo mi opinion y una forma sobre como podrias hacer el chat.
¡Saludos!