You mention trying DB_File to store the hash. Did you use your posted with DB_File?
If you used your posted code, none of the data would have actually ended up in the database. What you would want to do is to use split/join (or Storable for that matter) to turn your array into a string, and store that in the database, something like this:
my $data = $Hash{$a};
my @elt = split /::/, $data;
# Do stuff with @elt here.
# push @elt, $new_data to add data
$data = join '::', @elt;
$Hash{$a} = $data;
This way, your database won't be just the reference to the data in memory, your data will actually reside on disk.