johnl (09/09/82)
The DBM package that comes with seventh edition and Berklix
systems is a very nice set of routines for storing (key,data) pairs.
In general, it can find the data for any key with only one disk read
for file sizes up to about 8 megabytes. Insertion is slightly
slower, but not much. Disk utilization is comparable to that of a
B-tree, so that the total file size is less than twice the size of
the underlying data. Compared to a B-tree, access for specific keys
is much faster, but you get no help retrieving data in key order.
If you only need stuff in key order occasionally, you could just get
all the keys (which it gives to you in random hashed order) and
write them to a file, sort the file of keys, and then read the
sorted key file and retrieve the entries in key order.
My experience with the DBM package is that it works quite
nicely. I went over the code carefully and found no important nits
worth picking.
If you want B-trees, a few packages have shown up for sale in
places like Byte and Computerworld. I think they're overpriced.
John Levine, decvax!cca!ima!johnl, harpo!esquire!ima!johnl (uucp)
Levine@YALE (Arpa), 617-491-5450 (desperation)
--------