My personal preference would be either to have one XML file per entry and generate indexes offline (either in a cron job, or every time you create/edit an entry), or do the whole thing in a database.

Generally I tend to go with the database route, because at the end of the day they're great for storing lots of bits of similar data, and I always turn stuff into XML anyway for output generation via axkit. That way I get the best of both worlds.