For a random-access archive format that supports compression see DAR: http://dar.linux.free.fr/home.html
It doesn't seem very well known, which is unfortunate because it's much better suited for archiving files compared to gzipped tar (which is great for distributing files, but not great for archiving/backup).