Hay muchos tutoriales de ajax por la red, te recomiendo que te leas alguno.
 
Igualmente te dejo un ejemplo adaptado a tu caso:    
Código Javascript
:
Ver original- <script type="text/javascript"> 
- function peticionAjax(urlPeticion) { 
-     var res = ''; 
-     var ajax = false; 
-     try { 
-         ajax = new ActiveXObject("Msxml2.XMLHTTP"); 
-     } catch (e) { 
-         try { 
-             ajax = new ActiveXObject("Microsoft.XMLHTTP"); 
-         } catch (E) { 
-             ajax = false; 
-         } 
-     } 
-     if (!ajax && typeof XMLHttpRequest != 'undefined') { 
-         ajax = new XMLHttpRequest(); 
-     } 
-     var url = urlPeticion; 
-     ajax.open("POST", url, false); 
-     ajax.setRequestHeader('Content-Type', 
-             'application/x-www-form-urlencoded; charset=UTF-8'); 
-     ajax.onreadystatechange = function() { 
-         if (ajax.readyState == 4) { 
-             var res = ajax.responseText; 
-             var xhr_data = res.substring(res.indexOf('<etiquetaElementoXML>'), res.indexOf('</etiquetaElementoXML>')); 
-             xhr_data = xhr_data.substring(xhr_data.indexOf('>'), xhr_data.indexOf('</')); 
-             if (!isNaN(xhr_data)) { 
-                 document.getElementById('idContador').value=xhr_data; 
-             } 
-             setTimeout( function() { peticionAjax(url);}, 5000); 
-         } 
-     } 
-     ajax.send(); 
- } 
- setTimeout(function() { peticionAjax(urlPeticion); }, 1000); 
- </script> 
En el parametro urlPeticion debes poner la direccion donde vas a llamar al servidor para que te responda con el numero de registros que hay. 
etiquetaElementoXML es la etiqueta donde vas a enmascarar el numero de registros dentro del xml que devuelve el servidor. 
idContador es el id de por ejemplo un cuadro de texto donde vas a mostrar el numero de registros. 
La peticion hace lo siguiente: 
Realiza la peticion, coge la etiqueta xml donde esta el numero de registros y luego el numero dentro de esta etiqueta, comprueba que es un numero valido y lo pone en idContador. Luego hace una peticion nueva a los 5 segundos (5000 milisegundos). Asi hasta que el cliente cierre o cambie la pagina. 
El xml que responde el servidor podria ser asi:
<?xml version="1.0"?>
<numeroRegistros>
   <etiquetaElementoXML>1000</etiquetaElementoXML>
</numeroRegistros> 
Basicamente no necesitas mas que modificar la url del servidor, como quieres llamar a la etiqueta XML y el id del campo donde vayas a mostrar el numero de registros. 
Depende de donde coloques el script, quizas necesites añadirlo como funcion al onLoad de tu body, o bien al final de la pagina. 
Un saludo!