I've used MLDBM with Storable over DB_File a few times.
It is perfectly fine as long as you don't need to do
searches through the value part of the data--for that
you really want a relational solution.
But as long as you're just doing key lookups,
it's wonderful.
MLDBM is not necessarily a drop-in replacement, however.
The biggest "gotcha" is that you cannot assign a value
directly to a non-top-level element.
That is, you can't do this to a MLDBM tied hash:
$hash{foo}{bar}{baz} = 'stuff';
You must instead do this:
$tmp = $hash{foo};
$tmp->{bar}{baz} = 'stuff';
$hash{foo} = $tmp;
