Lightweight Databases

Numeric Indices

In some cases, we can speed up searching
Suppose we want to look up usernames by UID
Trick: Record number n holds information for user #n

     root    0    PLM/VF.estSxwSuper user
     larry   1    ..qQYY3gYY0yAWall                Larry
     GARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEG
     GARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEG
     ...
     GARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEG
     GARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEG
     mjd     119  A12FMTJGN5wpYDominus             Mark
     GARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEG
     ...
     GARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEGARBAGEG
     billg   666  xyPXkPQTjCjnUGates               William
     ...

Locating a user is now very fast:

     sub find_user_by_uid {
       my ($fh, $uid) = @_;
       seek $fh, $uid * 64, SEEK_SET;
       if (read($fh, my($rec), 64) == 64) {
         my (@field) = unpack "A8 A5 A13 A20 A18", $rec;
         return @field;
       }
       return;
     }