tie %index1, "DB_File", "index1", O_RDWR│O_CREAT, 0666, $DB_BTREE
tie %index2, "DB_File", "index2", O_RDWR│O_CREAT, 0666, $DB_BTREE

...

sub insert
{
  my $msg = shift;
  $index1{$msg->key1} = $msg->uid;
  $index2{$msg->key2} = $msg->uid;
...
}

my @sorted_by_index1 = @uid2msg{values %index1};