Dbm

From Wikipedia, the free encyclopedia

Dbm was the first of a family of simple database engines, originally written by Ken Thompson and released by AT&T in 1979 ^[1]. The name is a three letter acronym for Database manager. It stores data by use of a single key (a primary key) in fixed-size buckets and uses hashing techniques to enable fast retrieval of the data by key.

The hashing scheme used is a form of extensible hashing, so that the hashing scheme expands as new buckets are added to the database, meaning that, when nearly empty, the database starts with one bucket, which is then split when it becomes full. The two resulting child buckets will themselves split when they become full, so the database grows as keys are added.

Dbm has had many successors:

• Ndbm: In 1986 Berkeley produced ndbm (standing for New Database Manager). This added support for having multiple databases open concurrently.

• Sdbm: Some versions of unix were excluding ndbm due to licencing issues, so in 1987 Ozan Yigit produced this public domain clone^[2].

• Gdbm: Standing for 'Gnu Database Manager' this open source version was written by Philip A. Nelson for the GNU project (www.gnu.org). It added support for arbitrary length data in the database, as previously all data had had a fixed maximum length. http://www.gnu.org/software/gdbm/gdbm.html

• Tdbm: Provided support for Atomic transactions.

• TDB: Released by the samba team, under the GPL. From the sourceforge page: TDB is a Trivial Database. In concept, it is very much like GDBM, and BSD's DB except that it allows multiple simultaneous writers and uses locking internally to keep writers from trampling on each other. TDB is also extremely small. http://sourceforge.net/projects/tdb/

• QDBM: 'Quicker Database Manager'. Claims to be quicker, and was released under the GPL by Mikio Hirabayashi in 2000. http://qdbm.sourceforge.net/

• Berkeley DB: A version that is available under Dual licence, both open source and commercial. It is now supported and maintained by the company Sleepycat Software, which was formed by long time dbm developers Margo Seltzer and Keith Bostic. http://www.sleepycat.com. Sleepycat Software has been acquired by Oracle in Feb, 2006. http://www.oracle.com/database/berkeley-db/index.html

• JDBM: JDBM is a transactional persistence engine for Java. It aims to be for Java what GDBM is for other languages (C/C++, Python, Perl, etc.) http://jdbm.sourceforge.net

[edit] References

• Seltzer & Yigit 'A New Hashing Package for Unix' http://www.eecs.harvard.edu/margo/papers/usenix91/paper.ps.
• Brachman & Neufeld 'TDBM: A DBM Library With Atomic Transactions' http://www.dss.ca/dss/tech/papers/tdbm/usenix.pdf.
• Olsen, Bostic & Seltzer 'Berkeley DB'. http://www.sleepycat.com/docs/ref/refs/bdb_usenix.html