DBM (computing): Difference between revisions

Revision as of 13:35, 26 February 2020

Latest revision as of 09:06, 21 June 2025

(44 intermediate revisions by 21 users not shown)

Line 1:

{{Short description|Key-value database management system}}

{{refimprove|date=April 2018}}

{{About|the family of database engines||DBM (disambiguation){{!}}DBM}}

{{Use mdy datesrefimprove|date=JuneJanuary 20162022}}

In computing, a '''DBM''' is a [[Librarylibrary (computing)|library]] and [[file format]] providing fast, single-keyed access to data. It is aA [[key-value database]] from the original [[Unix]], ''dbm'' is an early example of a [[NoSQL]] system.<ref name="2007-kew-apache"/><ref name="2001-hazel-exim"/><ref name="2001-ladd-odonell-xhtml"/>

==History==

The original ''dbm'' library and file format was a simple [[database engine]], originally written by [[Ken Thompson]] and released by [[AT&T]] in 1979. The name is a [[three -letter acronym]] 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 fixed-size [[bucket (computing)|buckets]] and uses [[hash function|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.

Line 16:

The original AT&T ''dbm'' library has been replaced by its many successor implementations. Notable examples include:<ref name="2001-ladd-odonell-xhtml"/>

* ''ndbm'' ("new dbm"), based on the original dbm with some new features.

* ''[https://gnu.org/s/gdbm''/ GDBM] ("GNU dbm"), [[GNU]] rewrite of the library implementing ''ndbm'' features and its own interface. Also provides new features like crash tolerance for guaranteeing data consistency.<ref>{{cite web |title=Crash Tolerance |website=GDBM manual |url=https://www.gnu.org.ua/software/gdbm/manual/Crash-Tolerance.html |websiteaccess-date=www3 October 2021}}</ref><ref>{{cite web |title=Crashproofing the Original NoSQL Key-Value Store |url=https://queue.gnuacm.org/detail.uacfm?id=3487353 |access-date=3 October 2021}}</ref>

* ''sdbm'' ("small dbm"), a [[public ___domain]] rewrite of ''dbm''. It is a part of the standard distributionsdistribution for [[Perl]] and is available as an external library for [[Ruby_(programming_language)|Ruby]].<ref>{{cite web |last1=yigit |first1=ozan |title=sdbm.bun |website=cse.yorku.ca |url=http://www.cse.yorku.ca/~oz/sdbm.bun |website=cse.yorku.ca |accessdateaccess-date=8 May 2019}}</ref><ref>{{cite web |title=classRuby SDBM library |website=SDBM on Github |url=https://docsgithub.com/ruby-lang.org/en/2.4.0/SDBM.htmlsdbm |websitequote=DocumentationNote forthat Ruby used to ship SDBM in the standard distribution up until version 2.4.07, |quote=Noteafter thatwhich Rubyit comeswas withmade theavailable sourceonly codeas foran SDBMexternal library, whilesimilarly to the DBM and GDBM standard libraries, relyremoved onfrom externalthe librariesstandard andlibrary headersin Ruby 3.1.}}</ref>

* ''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.<ref>{{cite web |date=2006 |title=QDBM: Quick Database Manager |website=fallabs.com |url=https://fallabs.com/qdbm/ |access-date=2020-02-27 |archive-date=2020-02-27 |archive-url=https://web.archive.org/web/20200227064151/https://fallabs.com/qdbm/ |url-status=dead }}</ref>

* [[Berkeley DB]], 1991 replacement of ndbm by [[Sleepycat Software]] (now [[Oracle Corporation|Oracle]]) created to get around the AT&T Unix copyright on [[Berkeley Software Distribution|BSD]]. It features many extensions.

* ''tdb'' ("Trivial Database"), a simple database used by [[Samba (software)|Samba]] that supports multiple writers. Has a gdbm-based API.<ref>{{cite web |title=tdb: Main Page |website=tdb.samba.org |url=https://tdb.samba.org/}}</ref>

* [[Lightning Memory-Mapped Database|LMDB]]: [[copy-on-write]] [[memory-mapped file|memory-mapped]] [[B+ tree]] implementation in [[C (programming language)|C]] with a dbm and Berkeley-style API. Has improvements to parallelism.

* [[Berkeley DB]], 1991 replacement of ndbm by [[Sleepycat Software]] (now [[Oracle Corporation|Oracle]]) created to get around the AT&T Unix copyright on [[Berkeley Software Distribution|BSD]]. It features many extensions like parallelism, transactional control, hashing, and B-tree storage.

* [[Lightning Memory-Mapped Database|LMDB]]: [[copy-on-write]] [[memory-mapped file|memory-mapped]] [[B+ tree]] implementation in [[C (programming language)|C]] with a dbm and Berkeley-style API. Has improvements to parallelism.

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 (software)|cdb]] ("constant database"), database by [[Daniel J. Bernstein]], database files can only be created and read, but never be modified

* [[Tokyo Cabinet and Kyoto Cabinet]]: [[C (programming language)|C]] and [[C++]] implementations employing [[hash table]], [[B+ tree]], or fixed-length [[array data structure|array]] structures by FAL Labs. Has improvements to parallelism.<ref> {{ cite web | url = http://fallabs.com/tokyocabinet/spex-ja.html | title = Tokyo Cabinet第1版基本仕様書 | access-date = 25 May 2019 | date = 5 August 2010 | website = Fall Labs | language = ja | trans-title = Fundamental Specifications of Tokyo Cabinet Version 1 | quote = Tokyo CabinetはGDBMやQDBMの後継として次の点を目標として開発されました。これらの目標は達成されており、Tokyo Cabinetは従来のDBMを置き換える製品だと言えます。 | format = html | archive-url = https://web.archive.org/web/20181028124047/http://fallabs.com/tokyocabinet/spex-ja.html | archive-date = 28 October 2018 | df = dmy-all }} </ref>

* [[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 the''gdbm'' is ubiquitous on [[Linux]]. The Berkeley DB implementations were standard on some free operating systems.<ref name="2001-hazel-exim"/><ref name=fuzz/> After a change of licensing of the Berkeley DB to [[GNU AGPL]] in 2013, projects like [[Debian]] have moved to LMDB.<ref name=deb>{{cite mailing list |last=Surý |first=Ondřej |date=19 June 2014 |title=New project goal: Get rid of Berkeley DB (post jessie) |mailing-list=debian-devel |publisher=[[Debian]] |url=https://lists.debian.org/debian-devel/2014/06/msg00338.html}}</ref>

== Reliability ==

A 2018 [[american fuzzy lop (fuzzer)|AFL]] [[fuzzing]] test against many DBM-family databases exposed many problems in implementations when it comes to corrupt or invalid database files. Only [[cdb (software)|''freecdb'']] by [[Daniel J. Bernstein]] 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;<ref name=fuzz>{{cite web |last=Debroux |first=Lionel |date=16 Jun 2018 |title=oss-security - Fun with DBM-type databases... |website=openwall.com |url=https://www.openwall.com/lists/oss-security/2018/06/17/1}}</ref> the fixes would be irrelevant to open-source software users due to the licensing change locking them back on an old version.<ref name=deb/>

== See also ==

* [[Ordered Key-Value Store]]

* [[Embedded database]]

* [[Flat file database]]

* [[ISAM]]

* [[Key-valueKey–value database]]

* [[Mobile database]]

* [[NoSQL]]

Line 46 ⟶ 53:

==Bibliography==

{{refbegin}}

*{{cite book |ref=harv |year=2001 |last=Hazel |first=Philip |publisheryear=O'Reilly2001 |title=Exim: The Mail Transfer Agent |publisher=O'Reilly |url=https://books.google.co.ukcom/books?id=AcLDAQAAQBAJ&pg=PT500}}

*{{cite book |reflast1=harv |year=2001Ladd |first1=Eric |last1last2=LaddO'Donnell |first2=Jim |last2year=O'Donnell |publisher=Que2001 |title=Using XHTML, XML and Java 2: Platinum Edition |publisher=Que |isbn=9780789724731 |url=https://books.google.co.ukcom/books?id=NLc_TQiWvo4C&pg=PA823}}

*{{cite book |reflast=harv |year=2007Kew |first=Nick |lastyear=Kew |publisher=Prentice Hall Professional2007 |title=The Apache Modules Book: Application Development with Apache |publisher=Prentice Hall Professional |isbn=9780132704502 |url=https://books.google.co.ukcom/books?id=HTo_AmTpQPMC&pg=PA80}}

{{refend}}

* [https://apr.apache.org/docs/apr-util/0.9/group__APR__Util__DBM__SDBM.html SDBM library] @[[The Apache Software Foundation|Apache]]

* {{cite | url=https://books.google.com/books?id=vvuzDziOMeMC&pg=PT270book | titlelast1=Beginning Linux ProgrammingMatthew | first1=Neil | last1last2=MatthewStones | first2=Richard | last2year=Stones2008 | publishertitle=WileyBeginning |Linux date=2008Programming | chapter=Databases |publisher=Wiley ref|url=nonehttps://books.google.com/books?id=vvuzDziOMeMC&pg=PT270}}

* {{cite web |authorlast1=Olson, |first1=Michael A. |last2=Bostic &|first2=Keith |last3=Seltzer |first3=Margo |year=1999 |title=Berkeley DB |work=Proceedings of the FREENIX Track:1999 USENIX Annual Technical Conference |url=http://www.usenix.org/events/usenix99/full_papers/olson/olson.pdf}}

[[Category:Database engines]]