You are looking at historical revision 34179 of this page. It may differ significantly from its current revision.

sdbm

sdbm is a clone of the SDBM database library.

Overview

sdbm is a reimplementation of the public-domain SDBM database library, which is itself essentially a clone of NDBM. SDBM provides a simple key-value store with a fixed limit on data length and no ACID semantics to speak of, providing no write locking, no atomicity, no transactions, and little guarantee that your file won't be corrupted in a crash. It also relies on sparse file support, which is not present on filesystems such as HFS+.

Despite these shortcomings, it is a simple implementation without dependencies, written completely in Scheme. And some issues with the original implementation have been remedied: byte order is configurable, and page and directory block size can be adjusted at runtime. Therefore, sdbm might still be useful as a very simple key-value store for non-critical applications.

Joint Database Technology

Where external, binary, persistent, SDBM database files (tied to program hash tables) can really be made useful is in using the key/value pairs for random access indexing into a huge relational "text" flat file database composed of many flat files (with fixed-length records) exhibiting parent/child (1-to-many record) relationships. The key would be composed of a: single field, single partial field, or a compound key of multiple single and/or partial fields concatenated together (perhaps with a delimiter character between them such as a pipe "|"). The value in the key/value pair would the location offset (in bytes) to seek to (i.e. position the file pointer) in a flat file at the start of a specific record wished to be random accessed for: READ, READ/WRITE, or APPEND access. Multiple SDBM files can be setup as alternate indexes into each of the Flat File database text files, each SDBM file containing a different key (composed of a: single field, single partial field, or a compound key of multiple single and/or partial fields concatenated together). When editing records, the changes are made "in place" overwriting existing data in the flat file record. In a multi-user environment, a manual record locking system could be designed to lock a specific record for editing by one user. The username, flat file name, and record offset could be stored in an external SDBM database file (tied to a program hash table) at the time a user makes the request to edit a specific record. Once the record is released from EDIT (SAVE or CANCEL issued), then the lock is removed from the SDBM file. Each time a user makes a request to edit a record, the user-interface to the Flat File database would perform a Lookup to this Lock File to determine if the record in the Flat File was available for edit or already locked by another user. If the user-interface was designed well, child records (in a 1-to-many, parent/child relationship) would not be directly editable, but only editable whenever the corresponding parent record was locked for edit. This is a very stable relational database system. The binary SDBM files can easily be rebuilt from the Flat File database records. This is more desirable, then let's say, a MS-Access database, where the text data and indexes are stored together in a binary file which can become corrupted making it sometimes difficult to rescue your important textual data. In MS-Access, the database Data and Objects: back-end Tables/Indexes/Data, and front-end Reports/Forms/Macros/etc. are often mistakenly stored in one file (in binary format) - although MS-Access does provide for the means to separate the back-end and front-end into separate files allowing for a much more stable DB system.

Installation

Use chicken-install as usual. But some configuration can be done by defining certain features at compile-time.

Byte order
sdbm-little-endian or sdbm-big-endian set the read and write order of bytes in the file. If no byte order is specified, host order is used, as in the original implementation.
Hash function
sdbm-hash-djb selects an alternate hash function by Dan Bernstein. If no hash function is specified, the native SDBM hash function is used.

To define a feature, set it in CSC_OPTIONS before calling chicken-install:

CSC_OPTIONS="-Dsdbm-hash-djb -Dsdbm-big-endian" chicken-install sdbm

will configure sdbm to use the DJB hash and big-endian order.

Basic interface

[procedure] (open-database pathname #!key flags mode page-block-power dir-block-power) -> db

Opens existing SDBM database pathname or creates an empty database if pathname does not exist. The database resides in two files: pathname.dir (directory file) and pathname.pag (page file). Returns an opaque database object.

Optional keyword arguments are:

flags
flags passed to file-open, default: (+ open/rdwr open/creat)
mode
permissions passed to file-open, default: (+ perm/irwxu perm/irgrp perm/iroth)
page-block-power
bytes in each data page, as a power of 2; default: 12 (4096 bytes)
dir-block-power
bytes in each directory block, as a power of 2; default: 12 (4096 bytes)

The data page size limits the length of a key/value pair, so you may need to increase it to correspond with your maximum pair size. An undersized page can lead to frequent hash bucket splits and a bloated file size with many holes. An oversized page can incur disk performance overhead on read and write, since an entire page is read or written for every operation. Values between 4096 and 16384 bytes seem reasonable.

Note: The SDBM format has no database header, so you must always specify the same page-block-power and dir-block-power for a given database. The reference implementation uses page-block-power of 10 (1024 bytes) and dir-block-power of 12 (4096 bytes).

[procedure] (close-database db)

Close database associated with db.

[procedure] (fetch db key) -> val

Fetch key from SDBM database db, returning the associated value or #f if the key did not exist. The returned value is a string. key is normally a string; if not, it is converted into a string.

[procedure] (store! db key val #!optional (replace #t))

Store key, val pair into SDBM database db. val must be a string; key is converted into a string if not already.

If the key exists, and optional argument replace is #t (the default) then the pair will be replaced. If replace is #f instead, an error is returned.

[procedure] (delete! db key)

Delete key from SDBM database db. If key does not exist, an error is raised.

Enumeration

[procedure] (pair-iterator db) -> iter

Return a new pair iterator object that can be used to iterate over pairs in the SDBM database db. Pass this iterator to next-pair repeatedly.

[procedure] (next-pair iter) -> (key . val)

Return the next pair that iter, a pair-iterator, sees in the database. If there are no more pairs, returns #f. Otherwise, it returns a (key . val) pair, where both values are strings.

[procedure] (pair-fold db kons knil) -> kvs

Perform a fold over all pairs in SDBM database db. knil is the initial value. kons is a procedure of three arguments: (key val kvs). The return value of kons is passed to the next execution of kons in kvs.

Author

Jim Ursetto

Version history

0.1.0
Initial release

License

BSD