localtime in scalar context returns a string something like "Fri Jul 18 23:35:45 2003" which won't sort cleanly. Build the key like "YYYYMMDDHHMMSS" and the keys will be sorted on disk.

#!/usr/bin/perl

use strict;
use warnings;
use DB_File;

unlink 'db'; # to prevent dupes if this is run more than once
tie my %hash, 'DB_File', 'db', O_CREAT|O_RDWR, 0644, $DB_BTREE;

print "Building \%hash...\n";
$|++;
for my $count (1 .. 50) {
    my @time = localtime;
    my $key = $time[5] + 1900;
    $key .= sprintf "%02d", $time[$_] for reverse 0 .. 4;
    print "$count... " if $count % 10 == 0;
    $hash{$key} = "Message number $count";
    sleep 1;
}
print "Output:\n";
print "$_: $hash{$_}\n" for keys %hash;
[download]

Check the output, you'll see what I mean. The keys come out lexically sorted - the messages go from Message #1 to #50.

Remember that you can have duplicate keys with $DB_BTREE. If two values are inserted with the same time stamp, there's no guarantee which way they will be retrieved (which is why I suggested $DB_RECNO).

HTH