Ciao,
ecco un esempio

Codice PHP:
<?php 
header ("Content-Type:text/xml"); 

$urlset = array(
    array(
        'loc' => 'loc1',
        'lastmod' => 'lastmod1',
        'changefreq' => 'changefreq1',
        'priority' => 'priority1',
    ),
    array(
        'loc' => 'loc2',
        'lastmod' => 'lastmod2',
        'changefreq' => 'changefreq2',
        'priority' => 'priority2',
    )
);

echo "<?xml version=\"1.0\" encoding=\"UTF-8\"?>";
echo "<urlset xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xsi:schemaLocation=\"http://www.sitemaps.org/schemas/sitemap/0.9 [url]http://www.sitemaps.org/schemas/sitemap/0.9/sitemap.xsd\[/url]" xmlns=\"http://www.sitemaps.org/schemas/sitemap/0.9\">";

foreach( $urlset AS $url ) {
echo "<url>
<loc>".$url['loc']."</loc>
<lastmod>".$url['lastmod']."</lastmod>
<changefreq>".$url['changefreq']."</changefreq>
<priority>".$url['priority']."</priority>
</url>";
}

echo "</urlset>";
Il tuo array $urlset deve ovviamente contenere i dati corretti.
In questo modo la sitemap è generata in automatico senza fare nessuna modifica,
devi fare in modo che tuosito/sitemap.xml punti ad uno script del genere.

Per quanto riguarda la cache, se non hai migliaia di record puoi ometterla, ti consiglio di fare qualche ricerca sul web a proposito di questo argomento.

Ciao