QDBM(3)

💖 QDBM — quick database manager 💖

okay bestie, welcome to QDBM(3), aka the Quick Database Manager, and honestly? it's giving legendary. this is the manual page for it, and we're gonna get through it together. part 1, let's go 🫶

---

✨ NAME ✨

QDBM — quick database manager. that's it, that's the name, short and iconic 👑

---

🌸 OVERVIEW 🌸

so QDBM is a library of routines for managing a database. and what's a database here? literally just a simple data file stuffed with records, where each record is a pair of a key and a value. that's the whole vibe. every key and every value is serial bytes with variable length, so both binary data and character string can be used as a key and a value. there's neither concept of data tables nor data types — no schema drama, no type-checking lectures, we're free 💅

records get organized in a hash table or a B+ tree. pick your fighter.

the hash table situation 🔥

for a database of hash table, each key must be unique within a database, so it is impossible to store two or more records with a key overlaps. no duplicates allowed, periodt. the access methods it gives you are:

• storing a record with a key and a value
• deleting a record by a key
• retrieving a record by a key

plus traversal access to every key is provided, although the order is arbitrary. these access methods are similar to ones of DBM (or its followers: NDBM and GDBM) library defined in the UNIX standard. QDBM is literally an alternative for DBM because of its higher performance. not me casually outperforming the ancestors 😌

the B+ tree situation 🦋

for a database of B+ tree, records whose keys are duplicated can be stored. yes bestie, duplicates are welcome here. access methods of storing, deleting, and retrieving are provided as with the database of hash table. records are stored in order by a comparing function assigned by a user. it is possible to access each record with the cursor in ascending or descending order. according to this mechanism, forward matching search for strings and range search for integers are realized. and on top of all that, transaction is available in database of B+ tree. she does it all 💖

---

⚡ EFFECTIVE IMPLEMENTATION OF HASH DATABASE ⚡

QDBM was developed referring to GDBM for the purpose of the following three points: higher processing speed, smaller size of a database file, and simpler API. and they have been achieved, no cap. moreover, the following three restrictions of traditional DBM are cleared:

• a process can handle only one database
• the size of a key and a value is bounded
• a database file is sparse

gone. deleted. we don't know them 🌈

QDBM uses hash algorithm to retrieve records. if a bucket array has sufficient number of elements, the time complexity of retrieval is O(1). that is, time required for retrieving a record is constant, regardless of the scale of a database. it is also the same about storing and deleting. collision of hash values is managed by separate chaining. data structure of the chains is binary search tree. even if a bucket array has unusually scarce elements, the time complexity of retrieval is O(log n). so like, either way, she's fast 💅

QDBM attains improvement in retrieval by loading RAM with the whole of a bucket array. if a bucket array is on RAM, it is possible to access a region of a target record by about one path of file operations. a bucket array saved in a file is not read into RAM with the read call but directly mapped to RAM with the mmap call. therefore, preparation time on connecting to a database is very short, and two or more processes can share the same memory map. sharing is caring, bestie 🫶

the math part (she's a nerd and we love her) 📊

if the number of elements of a bucket array is about half of records stored within a database, although it depends on characteristic of the input, the probability of collision of hash values is about 56.7% (36.8% if the same, 21.3% if twice, 11.5% if four times, 6.0% if eight times). in such case, it is possible to retrieve a record by two or less paths of file operations. if it is made into a performance index, in order to handle a database containing one million of records, a bucket array with half a million of elements is needed. the size of each element is 4 bytes. that is, if 2M bytes of RAM is available, a database containing one million records can be handled. iconic. no notes. 👑

reader and writer modes 📚

QDBM provides two modes to connect to a database: reader and writer.

• a reader can perform retrieving but neither storing nor deleting
• a writer can perform all access methods

exclusion control between processes is performed when connecting to a database by file locking. while a writer is connected to a database, neither readers nor writers can be connected. while a reader is connected to a database, other readers can be connect, but writers can not. according to this mechanism, data consistency is guaranteed with simultaneous connections in multitasking environment. boundaries, bestie. we love boundaries ✨

insert, replace, and the iconic concatenate 💅

traditional DBM provides two modes of the storing operations: insert and replace. in the case a key overlaps an existing record, the insert mode keeps the existing value, while the replace mode transposes it to the specified value. in addition to the two modes, QDBM provides concatenate mode. in that mode, the specified value is concatenated at the end of the existing value and stored. this feature is useful when adding a element to a value as an array.

moreover, although DBM has a method to fetch out a value from a database only by reading the whole of a region of a record, QDBM has a method to fetch out a part of a region of a value. when a value is treated as an array, this feature is also useful. we love a partial read moment 🎀

fragmentation, alignment, and the glow-up 🌸

generally speaking, while succession of updating, fragmentation of available regions occurs, and the size of a database grows rapidly. QDBM deal with this problem by coalescence of dispensable regions and reuse of them, and featuring optimization of a database. when overwriting a record with a value whose size is greater than the existing one, it is necessary to remove the region to another position of the file. because the time complexity of the operation depends on the size of the region of a record, extending values successively is inefficient. however, QDBM deal with this problem by alignment. if increment can be put in padding, it is not necessary to remove the region. she said "no moving, we pad" and honestly? queen behavior 💜

the 2GB problem and the directory database 🗂️

as for many file systems, it is impossible to handle a file whose size is more than 2GB. to deal with this problem, QDBM provides a directory database containing multiple database files. due to this feature, it is possible to handle a database whose total size is up to 1TB in theory. moreover, because database files can be deployed on multiple disks, the speed of updating operations can be improved as with RAID-0 (striping). it is also possible for the database files to deploy on multiple file servers using NFS and so on. distributed queen behavior, we're obsessed 🌈

---

🌟 USEFUL IMPLEMENTATION OF B+ TREE DATABASE 🌟

although B+ tree database is slower than hash database, it features ordering access to each record. and the order can be assigned by users — your database, your rules. records of B+ tree are sorted and arranged in logical pages. sparse index organized in B tree that is multiway balanced tree are maintained for each page. thus, the time complexity of retrieval and so on is O(log n).

cursor is provided to access each record in order. the cursor can jump to a position specified by a key and can step forward or backward from the current position. because each page is arranged as double linked list, the time complexity of stepping cursor is O(1). literal perfection, the cursor ate 💅

B+ tree database is implemented, based on above hash database. because each page of B+ tree is stored as each record of hash database, B+ tree database inherits efficiency of storage management of hash database. because the header of each record is smaller and alignment of each page is calculated statistically, in most cases, the size of database file is cut by half compared to one of hash database. HALF. bestie. 😭

although operation of many pages are required to update B+ tree, QDBM expedites the process by caching pages and reducing file operations. in most cases, because whole of the sparse index is cached on memory, it is possible to retrieve a record by one or less path of file operations. one path or less, she's not even trying and she's winning 🏆

transactions, the main character feature 🔐

B+ tree database features transaction mechanism. it is possible to:

• commit a series of operations between the beginning and the end of the transaction in a lump
• abort the transaction and perform rollback to the state before the transaction

even if the process of an application is crushed while the transaction, the database file is not broken. like, she gets knocked down and gets back up, no damage taken. main character energy fr fr 👑

compression, the glow-up nobody asked for but everybody needed 🦋

in case that QDBM is built with ZLIB, LZO, or BZIP2 enabled, a lossless data-compression library, the content of each page of B+ tree is compressed and stored in a file. because each record in a page has similar patterns, high efficiency of compression is expected due to the Lempel-Ziv algorithm and the like. in case handling text data, the size of a database is reduced to about 25%. if the scale of a database is large and disk I/O is the bottleneck, featuring compression makes the processing speed improved to a large extent. she compressed AND she got faster? that's not fair to the other databases 😭✨

---

okay that's part 1, and there is so much more coming, so don't go anywhere 💖

💖 SIMPLE BUT VARIOUS INTERFACES 💖

okay so first things first: QDBM's APIs are so simple. like, you can do database I/O the exact same way you do normal file I/O, using a FILE pointer — yes, the one defined in ANSI C. in the basic API of QDBM, the entity of a database is recorded as one single file. in the extended API, the entity of a database is recorded as several files in one directory. and because those two APIs are super similar to each other, porting an application from one to the other is genuinely easy. no drama, no rewriting your whole life. ✨

APIs that are compatible with NDBM and GDBM are also provided. there are a lot of applications out there using NDBM or GDBM, so porting them onto QDBM is a breeze. in most cases it's literally completed only by replacement of the header including (#include) and re-compiling. 🎀

⚠️ but bestie, listen: QDBM can not handle database files made by the original NDBM or GDBM. that's a hard no, not a vibe check fail, just a fact.

to handle records on memory easily, the utility API is provided. it implements memory allocating functions, sorting functions, extensible datum, array list, hash map, and so on. using them, you can handle records in C language cheaply — as in, like, such script languages as Perl or Ruby cheaply. C girlies, we ate. 💅

the B+ tree database is used with the advanced API. the advanced API is implemented using the basic API and the utility API. and because the advanced API is also similar to the basic API and the extended API, it's easy to learn how to use it. consistency?? we love her. 👑

in order to handle an inverted index — the kind used by full-text search systems — the inverted API is provided. if it's easy to handle an inverted index of documents, an application can focus on text processing and natural language processing. and because this API does not depend on character codes nor languages, it's possible to implement a full-text search system which can respond to various requests from users. global icon behavior. 🌈

along with APIs for C, QDBM provides APIs for C++, Java, Perl, and Ruby. the APIs for C are composed of seven kinds:

1. the basic API
2. the extended API
3. the NDBM-compatible API
4. the GDBM-compatible API
5. the utility API
6. the advanced API
7. the inverted API

command line interfaces corresponding to each API are also provided. they're useful for prototyping, testing, debugging, and so on. the C++ API encapsulates database handling functions of the basic API, the extended API, and the advanced API with the class mechanism of C++. the Java API has native methods calling the basic API, the extended API, and the advanced API with Java Native Interface. the Perl API has methods calling the basic API, the extended API, and the advanced API with XS language. the Ruby API has method calling the basic API, the extended API, and the advanced API as modules of Ruby. 🦋

and moreover — CGI scripts for administration of databases and full-text search are provided. we're not just a library, we're a whole ecosystem, periodt. 🫶

---

🌍 WIDE PORTABILITY 🌍

QDBM is implemented being based on the syntax of ANSI C (C89) and using only APIs defined in ANSI C or POSIX. thus, QDBM works on most UNIX and its compatible OSs. no cap, it just runs. 💜

as for the C API, checking operations have been done at least on:

• Linux 2.2
• Linux 2.4
• FreeBSD 4.8
• FreeBSD 5.0
• SunOS 5.7
• SunOS 5.8
• SunOS 5.9
• HP-UX 11.00
• Cygwin 1.3.10
• Mac OS X 10.2
• RISC OS 5.03

one tiny thing though — a database file created by QDBM depends on the byte order of the processor. but to do with it (yes, the manpage says "to do with it", iconic), utilities to dump data in a format which is independent to byte orders are provided. so you're covered. 🧚

---

🔨 BUILDING 🔨

for building a program using QDBM, the program should be linked with a library file libqdbm.a or libqdbm.so. for example, the following command is executed to build sample from sample.c.

gcc -I/usr/local/include -o sample sample.c -L/usr/local/lib -lqdbm

that's it. copy it, paste it, slay it. 🍓

---

✍️ AUTHOR ✍️

QDBM is written by Mikio Hirabayashi. you can contact the author by e-mail to <mikio@fallabs.com>. any suggestion or bug report is welcome to the author — so if you find something cursed, tell him, he genuinely wants to know. 💖

---

⚖️ COPYRIGHT ⚖️

Copyright(c) 2000-2003 Mikio Hirabayashi

QDBM is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2 of the License, or any later version.

QDBM is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with QDBM; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.

---

👀 SEE ALSO 👀

• depot(3)
• curia(3)
• relic(3)
• hovel(3)
• cabin(3)
• villa(3)
• odeum(3)
• ndbm(3)
• gdbm(3)

---

and that's the whole page, bestie!! 🌸 this beauty is from the QDBM(3) man page, dated 2004-04-22 — shoutout to the Man Page crew for shipping it. now go build something iconic with it, you absolute main character. 💅✨👑🦋💖