Note that with DB_File you can choose between two types: DB_HASH and DB_BTREE. Maybe one of both behaves better/worse depending on the keys in use.