Caching Strategies/Database question

[Brian Kelley]

I am using a dictionary to hold

{string:[list of integers]}

key: values

The dictionary is randomly accessed to add an integer to the list
referenced by the string.

I have been exploring several differnent caching strategies ranging from
bsddb3 to the metakit toolkit for caching/retrieving these to disk.  One
of the problems that I am facing is that because the dictionary is
randomly accessed after the database gets to a certain size performance
goes WAY down with every strategy that I have tried.  (Note that
integers are never removed if that helps)  I have had success speed-wise
with MySQL but I simply cannot deliver that in my application, it's way
too costly to administer.

Has anyone examined a similar problem?  Thanks in advance.

Brian Kelley