Hi there. Sorry for the delay in replying, I kind of missed this.
I have been a bit wary of using SQL since I don't want to require the external daemon, but something like SQLite looks pretty good.
If you were just to simply use it to replace the cache storage, it should be pretty straightforward. That is (almost) all contained in cache.cc/cache.h. (Though coming up with a good/fast schema may be tricky due to the heirarchical nature of nget's data)
If you wanted to go a bit further and actually take advantage of SQL queries and stuff, that would be a bit more extensive of a change. And somewhat problematic due to the lack of regexps, but there could be other ways to use it (ie, only looking up what data is needed to do a test, doing sorting, etc).
There are also other possibilities:
Probably the simplest solution would be to split the storage of data for each server/group into multiple cache files, each one covering only a certain range of article numbers. Then on update each file could be
processed seperately, limiting the memory needed, and on searching the current meta-grouping code could be used to join them together on the fly.
In any case, help would certainly be appreciated as I haven't had much time to devote to this lately.