Only one comment:

And if you want to do a substring search, there is no easy method except for linear search. And that could be terribly slow even for small database.

In DB_File under the section Matching Partial Keys we see:

Matching Partial Keys

The BTREE interface has a feature which allows partial keys to be matched. This functionality is only available when the seq method is used along with the R_CURSOR flag.

           $x->seq($key, $value, R_CURSOR) ;
[download]

Here is the relevant quote from the dbopen man page where it defines the use of the R_CURSOR flag with seq:

Note, for the DB_BTREE access method, the returned key is not necessarily an exact match for the specified key. The returned key is the smallest key greater than or equal to the specified key, permitting partial key matches and range searches.

In the example script below, the match sub uses this feature to find and print the first matching key/value pair given a partial key.

           use strict ;
           use DB_File ;
           use Fcntl ;

           use vars qw($filename $x %h $st $key $value) ;

           sub match
           {
               my $key = shift ;
               my $value = 0;
               my $orig_key = $key ;
               $x->seq($key, $value, R_CURSOR) ;
               print "$orig_key\t-> $key\t-> $value\n" ;
           }

           $filename = "tree" ;
           unlink $filename ;

           $x = tie %h, "DB_File", $filename, O_RDWR|O_CREAT, 0640, $D
+B_BTREE
               or die "Cannot open $filename: $!\n";

           # Add some key/value pairs to the file
           $h{'mouse'} = 'mickey' ;
           $h{'Wall'} = 'Larry' ;
           $h{'Walls'} = 'Brick' ;
           $h{'Smith'} = 'John' ;

           $key = $value = 0 ;
           print "IN ORDER\n" ;
           for ($st = $x->seq($key, $value, R_FIRST) ;
                $st == 0 ;
                $st = $x->seq($key, $value, R_NEXT) )

             {  print "$key -> $value\n" }

           print "\nPARTIAL MATCH\n" ;

           match "Wa" ;
           match "A" ;
           match "a" ;

           undef $x ;
           untie %h ;
[download]

Here is the output:

           IN ORDER
           Smith -> John
           Wall  -> Larry
           Walls -> Brick
           mouse -> mickey

           PARTIAL MATCH
           Wa -> Wall  -> Larry
           A  -> Smith -> John
           a  -> mouse -> mickey

So, although I don't know how it is that DBM implements that internally, it does seem like it would give you a little bit more functionality (or at least a more elegant interface) than just a linear search. Comments?