In computing, a DBM is a

library A library is a collection of materials, books or media that are accessible for use and not just for display purposes. A library provides physical (hard copies) or digital access (soft copies) materials, and may be a physical location or a vi ...

and

file format A file format is a Computer standard, standard way that information is encoded for storage in a computer file. It specifies how bits are used to encode information in a digital storage medium. File formats may be either proprietary format, pr ...

providing fast, single-keyed access to data. A key-value database from the original

Unix Unix (; trademarked as UNIX) is a family of multitasking, multiuser computer operating systems that derive from the original AT&T Unix, whose development started in 1969 at the Bell Labs research center by Ken Thompson, Dennis Ritchie, a ...

, ''dbm'' is an early example of a

NoSQL A NoSQL (originally referring to "non- SQL" or "non-relational") database provides a mechanism for storage and retrieval of data that is modeled in means other than the tabular relations used in relational databases. Such databases have existed ...

system.

History

The original ''dbm'' library and file format was a simple

database engine A database engine (or storage engine) is the underlying software component that a database management system (DBMS) uses to create, read, update and delete (CRUD) data from a database. Most database management systems include their own applicatio ...

, originally written by

Ken Thompson Kenneth Lane Thompson (born February 4, 1943) is an American pioneer of computer science. Thompson worked at Bell Labs for most of his career where he designed and implemented the original Unix operating system. He also invented the B programmi ...

and released by

AT&T AT&T Inc. is an American multinational telecommunications holding company headquartered at Whitacre Tower in Downtown Dallas, Texas. It is the world's largest telecommunications company by revenue and the third largest provider of mobile tel ...

in 1979. The name is a

three letter acronym A three-letter acronym (TLA), or three-letter abbreviation, is an abbreviation consisting of three letters. These are usually the initial letters of the words of the phrase abbreviated, and are written in capital letters (upper case); three-lett ...

for ''DataBase Manager'', and can also refer to the family of database engines with APIs and features derived from the original ''dbm''. The ''dbm'' library stores arbitrary data by use of a single key (a

primary key In the relational model of databases, a primary key is a ''specific choice'' of a ''minimal'' set of attributes (columns) that uniquely specify a tuple (row) in a relation ( table). Informally, a primary key is "which attributes identify a record ...

) 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 extendible 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. The ''dbm'' library and its derivatives are pre-

relational database A relational database is a (most commonly digital) database based on the relational model of data, as proposed by E. F. Codd in 1970. A system used to maintain relational databases is a relational database management system (RDBMS). Many relatio ...

s they manage

associative array In computer science, an associative array, map, symbol table, or dictionary is an abstract data type that stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection. In mathematical terms an ...

s, implemented as on-disk

hash table In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', ...

s. In practice, they can offer a more practical solution for high-speed storage accessed by key, as they do not require the overhead of connecting and preparing queries. This is balanced by the fact that they can generally only be opened for writing by a single process at a time. An agent

daemon Daimon or Daemon (Ancient Greek: , "god", "godlike", "power", "fate") originally referred to a lesser deity or guiding spirit such as the daimons of ancient Greek religion and mythology and of later Hellenistic religion and philosophy. The wo ...

can handle requests from multiple processes, but introduces

IPC IPC may refer to: Computing * Infrastructure protection centre or information security operations center * Instructions per cycle or instructions per clock, an aspect of central-processing performance * Inter-process communication, the sharin ...

overhead.

Implementations

The original AT&T ''dbm'' library has been replaced by its many successor implementations. Notable examples include: * ''ndbm'' ("new dbm"), based on the original dbm with some new features.
GDBM
("GNU dbm"),

GNU GNU () is an extensive collection of free software Free software or libre software is computer software distributed under terms that allow users to run the software for any purpose as well as to study, change, and distribute it and any ...

rewrite of the library implementing ''ndbm'' features and its own interface. Also provides new features like crash tolerance for guaranteeing data consistency. * ''sdbm'' ("small dbm"), a

public domain The public domain (PD) consists of all the creative work to which no exclusive intellectual property rights apply. Those rights may have expired, been forfeited, expressly waived, or may be inapplicable. Because those rights have expired, ...

rewrite of ''dbm''. It is a part of the standard distribution for

Perl Perl is a family of two High-level programming language, high-level, General-purpose programming language, general-purpose, Interpreter (computing), interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it ...

and is available as an external library for

Ruby A ruby is a pinkish red to blood-red colored gemstone, a variety of the mineral corundum (aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called sapp ...

. * ''qdbm'' ("Quick Database Manager"), a higher-performance ''dbm'' employing many of the same techniques as Tokyo/Kyoto Cabinet. Written by the same author before they moved on to the cabinets. * ''tdb'' ("Trivial Database"), a simple database used by

Samba Samba (), also known as samba urbano carioca (''urban Carioca samba'') or simply samba carioca (''Carioca samba''), is a Brazilian music genre that originated in the Afro-Brazilian communities of Rio de Janeiro in the early 20th century. Havi ...

that supports multiple writers. Has a gdbm-based API. *

Berkeley DB Berkeley DB (BDB) is an unmaintained embedded database software library for key/value data, historically significant in open source software. Berkeley DB is written in C with API bindings for many other programming languages. BDB stores arbit ...

, 1991 replacement of ndbm by Sleepycat Software (now

Oracle An oracle is a person or agency considered to provide wise and insightful counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. As such, it is a form of divination. Description The wor ...

) created to get around the AT&T Unix copyright on BSD. It features many extensions like parallelism, transactional control, hashing, and B tree storage. *

LMDB Lightning Memory-Mapped Database (LMDB) is a software library that provides an embedded transactional database in the form of a key-value store. LMDB is written in C with API bindings for several programming languages. LMDB stores arbitrar ...

copy-on-write Copy-on-write (COW), sometimes referred to as implicit sharing or shadowing, is a resource-management technique used in computer programming to efficiently implement a "duplicate" or "copy" operation on modifiable resources. If a resource is dupl ...

memory-mapped

B+ tree A B+ tree is an m-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children. A B+ tree can be viewed as a B ...

implementation in C with a Berkeley-style API. The following databases are dbm-inspired, but they do not directly provide a dbm interface, even though it would be trivial to wrap one: * cdb ("constant database"), database by

Daniel J. Bernstein Daniel Julius Bernstein (sometimes known as djb; born October 29, 1971) is an American German mathematician, cryptologist, and computer scientist. He is a visiting professor at CASA at Ruhr University Bochum, as well as a research professor of ...

, database files can only be created and read, but never be modified * Tkrzw, an Apache 2.0 licensed successor to Kyoto Cabinet and Tokyo Cabinet * WiredTiger: database with traditional row-oriented and column-oriented storage.

Availability

As of 2001, the ''ndbm'' implementation of DBM was standard on Solaris and IRIX, whereas ''gdbm'' is ubiquitous on

Linux Linux ( or ) is a family of open-source Unix-like operating systems based on the Linux kernel, an operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically packaged as a Linux distribution, which i ...

. The Berkeley DB implementations were standard on some free operating systems. After a change of licensing of the Berkeley DB to

GNU AGPL The GNU Affero General Public License (GNU AGPL) is a free, copyleft license published by the Free Software Foundation in November 2007, and based on the GNU General Public License, version 3 and the Affero General Public License. The Free So ...

in 2013, projects like

Debian Debian (), also known as Debian GNU/Linux, is a Linux distribution composed of free and open-source software, developed by the community-supported Debian Project, which was established by Ian Murdock on August 16, 1993. The first version of De ...

have moved to LMDB.

Reliability

A 2018 AFL

fuzzing In programming and software development, fuzzing or fuzz testing is an automated software testing technique that involves providing invalid, unexpected, or random data as inputs to a computer program. The program is then monitored for exception ...

test against many DBM-family databases exposed many problems in implementations when it comes to corrupt or invalid database files. Only ''freecdb'' by

showed no crashes. The authors of gdbm, tdb, and lmdb were prompt to respond. Berkeley DB fell behind due to the sheer amount of other issues; the fixes would be irrelevant to open-source software users due to the licensing change locking them back on an old version.

References

Bibliography