10.1 DBM Files
DBMs have been available in Unix systems for a long time. DBMs were first introduced as a mechanism for disk-oriented hashing in the form of a small library written by Ken Thompson in the Seventh Edition Unix system [AT79]. DBMs and their derivatives provide access to data in disks using keys. An extended version of the DBM library, NDBM, was later introduced. A public-domain clone of NDBM, called SDBM was later developed as well. Another version called GDBM which is compatible in terms of interfaces was made available by the Free Software Foundation.
The DBM and NDBM library implementations are based on the same algorithm by Ken Thompson. DBMs allowed only one database to be open at a time whereas NDBMs added support for multiple databases to be open concurrently. The SDBM library is a public-domain clone of the NDBM library, developed by Ozan Yigit to provide NDBM’s functionality under some versions of UNIX that exclude NDBM for licensing reasons. The basic structure of SDBM is identical to NDBM, but internal details of the access function, such as address calculation and different hashing functions used make the two databases incompatible.
DBMs have several shortcomings. Since data is disk-resident, each access requires a system call, and a disk operation. Caching may be able to reduce the number of disk operations to achieve efficiency. A DBM cannot store data items whose total key and data size exceeds the page size of the hash table. Similarly, if two or more keys produce the same hash value, the table cannot store colliding keys.