Small DBMs: ODBM, NDBM, and SDBM

• Another problem is that these databases use sparse storage

• The hash isn't represented very efficiently on the disk

          # Keys   File extent  Space used
                     (ls -l)     (ls -s)

               1         1024        8  
               2         2048        8
               4         4096        8
               8         8192       48
              16       120832      120
              32       245760      208
              64       441344      296
             128      4251648      456
             256     12701696     1456
             512     21091328     2320
            1024     33284096     4128
            2048    536668160    11592
            4096   1065409536    22272

• Even though we're not storing that much data, the file extents get huge

• Many systems can't handle a file with an extent greater than 2GiB.

• On these systems, O/N/SDBM are severely limited in the amount of data they can store

• (This output produced by sdbm_test.pl in your handout)

Next

Copyright © 2003 M. J. Dominus