This was my assumption as well (that lookups should be roughly constant at some point). But clearly it is not so.

I've already tried switching to BTREE with no measurable result--I think having the db in RAM nullifies all of the tweaks that are available (like cachesize, etc.).

One thing I have thought of, which might be helpful, is that I already have a hash value which is my key in the database. As I understand it, the Berkeley DB then creates a new hash derived from my key to store the object. Any chance I could use my own hashes as record numbers or similar? (The hash I have for a key is a 32 byte MD5, which matches the Squid hash key for a given object.) Would avoid the key generation part of the STORE and FETCH. Might not be a benefit though...Will worry more about it if SDBM_File doesn't fix my problems.