.\" Copyright (c) 1990 The Regents of the University of California.
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" 1. Redistributions of source code must retain the above copyright
.\" notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\" notice, this list of conditions and the following disclaimer in the
.\" documentation and/or other materials provided with the distribution.
.\" 3. All advertising materials mentioning features or use of this software
.\" must display the following acknowledgement:
.\" This product includes software developed by the University of
.\" California, Berkeley and its contributors.
.\" 4. Neither the name of the University nor the names of its contributors
.\" may be used to endorse or promote products derived from this software
.\" without specific prior written permission.
.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
.\" @(#)db.3 5.16 (Berkeley) 4/2/91
btree_open, hash_open, recno_open \- database access methods
btree_open(const char *file, int flags, int mode,
const BTREEINFO * openinfo);
hash_open(const char *file, int flags, int mode,
const HASHINFO * openinfo);
recno_open(const char *file, int flags, int mode,
const RECNOINFO * openinfo);
are access method interfaces to database files in btree, hashed, and
flat-file formats, respectively.
The btree format is a representation of a sorted, balanced tree structure.
The hashed format is an extensible, dynamic hashing scheme.
The flat-file format is a UNIX file with fixed or variable length
These formats are described in more detail below.
Access to all file types is based on key/data pairs.
for reading and/or writing.
Databases never intended to be preserved on disk may be created by setting
the file parameter to NULL.
routine, however, only the O_CREAT, O_EXCL, O_RDONLY, O_RDWR, O_TRUNC
and O_WRONLY flags are meaningful.
is a pointer to an access method specific structure described below.
The open routines return a pointer to a DB structure on success and NULL
The DB structure contains at least the following fields:
int (*close)(const DB *db);
int (*sync)(const DB *db);
int (*del)(const DB *db, const DBT *key, u_int flags);
int (*get)(const DB *db, DBT *key, DBT *data, u_int flags);
int (*put)(const DB *db, const DBT *key, const DBT *data,
int (*seq)(const DB *db, DBT *key, DBT *data, u_int flags);
The elements of this structure consist of a pointer to an access method
specific structure and a set of routines which perform various functions.
All of these routines take a pointer to a structure as returned by
one of the open routines, one or more pointers to key/data structures,
and, optionally, a flag value.
A pointer to an internal structure specific to the access method.
The type of the underlying access method; either DB_BTREE, DB_HASH
A pointer to a routine to flush any cached information to disk, free any
allocated resources, and close the database file.
Since key/data pairs may be cached in memory, failing to close the
routine may result in inconsistent or lost information.
routines return -1 on error (setting
A pointer to a routine to remove key/data pairs from the database.
routines return -1 on error (setting
0 on success, and 1 if the specified
A pointer to a routine which is the interface for keyed retrieval from
The address and length of the data associated with the specified
are returned in the structure referenced by
routines return -1 on error (setting
0 on success, and 1 if the
A pointer to a routine to store key/data pairs in the database.
must be set to one of the following values:
Append the data immediately after the data referenced by
creating a new key/data pair.
(This implies that the access method is able to create new keys,
i.e. the keys are ordered and independent, for example, record numbers.
Insert the data immediately before the data referenced by
creating a new key/data pair.
(This implies that the access method is able to create new keys,
i.e. the keys are ordered and independent, for example, record numbers.
Enter the new key/data pair only if the key does not previously exist.
Enter the new key/data pair and replace any previously existing key.
routines return -1 on error (setting
0 on success, and 1 if the R_NOOVERWRITE
was set and the key already exists in the file.
A pointer to a routine which is the interface for sequential
retrieval from the database.
The address and length of the key are returned in the structure
and the address and length of the data are returned in the
Sequential key/data pair retrieval may begin at any time, and the
position of the ``cursor'' is not affected by calls to the
Modifications to the database during a sequential scan will be reflected
in the scan, i.e. records inserted behind the cursor will not be returned
while records inserted in front of the cursor will be returned.
The flag value must be set to one of the following values:
The data associated with the specified key is returned.
routines in that it sets the ``cursor'' to the location of the
(This implies that the access method has a implicit order which does
The first key/data pair of the database is returned.
The last key/data pair of the database is returned.
(This implies that the access method has a implicit order which does
Retrieve the key/data pair immediately after the key/data pair most recently
The cursor is moved to the returned key/data pair.
is set to R_NEXT the first time the
routine is called, the first key/data pair of the database is returned.
Retrieve the key/data pair immediately before the key/data pair most recently
The cursor is moved to the returned key/data pair.
is set to R_PREV the first time the
routine is called, the last key/data pair of the database is returned.
(This implies that the access method has a implicit order which does
routines return -1 on error (setting
0 on success, 1 if there are no more key/data pairs available.
access method is being used, and if the database file is a character special
file and no complete key/data pairs are currently available, the
A pointer to a routine to flush any cached information to disk.
If the database is in memory only, the
routine has no effect and will always succeed.
routines return -1 on error (setting
Access to all file types is based on key/data pairs.
Both keys and data are represented by the following data structure:
The elements of the DBT structure are defined as follows:
A pointer to a byte string.
The length of the byte string.
Key/data strings must fit into available memory.
One of the access methods is a btree: a sorted, balanced tree structure
with associated key/data pairs.
The access method specific data structure provided to
int (*compare)(const void *, const void *);
The elements of this structure are defined as follows:
The flag value is specified by
any of the following values:
if the key to be inserted already exists,
This flag permits duplicate keys in the tree.
duplicates are not permitted,
and attempts to insert them will fail.
Note, the order of retrieval of key/data pairs with duplicate keys is
A suggested maximum size, in bytes, of the memory cache.
Setting this value to zero specifies that an appropriate amount of memory
Since every search examines the root page of the tree, caching the most
recently used pages substantially improves access time.
In addition, physical writes are delayed as long as possible, so a moderate
cache can reduce the number of I/O operations significantly.
Obviously, using a cache increases the likelihood of corruption or lost data
if the system crashes while a tree is being modified.
pages decreases the creation time of a large tree by between two and three
Compare is a user defined comparison function.
It must return an integer less than, equal to, or greater than zero if the
first argument is considered to be respectively less than, equal to, or
The same comparison function must be used on a given tree every time it
If no comparison function is specified,
The byte order for 4-byte integers in the stored database metadata.
The number should represent the order as an integer; for example,
big endian order would be the number 4,321.
is 0 (no order is specified) the current host order is used.
If the file already exists, the specified value is ignored and the
value specified when the tree was created is used.
(Obviously, portability of the data forming the key/data pairs is the
concern of the application program.)
Page size is the size in bytes of the pages used for nodes in the tree.
If the file already exists, the specified value is ignored and the
value specified when the tree was created is used.
is zero, an appropriate page size is chosen (based on the system memory
and/or file system constraints), but will never be less than 512 bytes.
data structure is NULL, the
routine will use appropriate values.
If the database file already exists, and the O_TRUNC flag is not specified
Key structures may reference byte strings of slightly less than one-half the
tree's page size only (see
Data structures may reference byte strings of essentially unlimited length.
Searches, insertions, and deletions in a btree will all complete in
Forward sequential scans of a tree are from the least key to the greatest.
Space freed up by deleting key/data pairs from a btree is never reclaimed,
although it is normally made available for reuse.
The exception to this is that space occupied by large data items (those
greater than one quarter the size of a page) is neither reclaimed nor reused.
This means that the btree storage structure is grow-only.
The only solutions are to avoid excessive deletions, or to create a fresh
tree periodically from a scan of an existing one.
One of the access methods is hashed access and storage.
The access method specific data structure provided to
u_long (*hash)(const void *, const size_t);
The elements of this structure are defined as follows:
defines the hash table bucket size, and is, by default, 256 bytes.
It may be preferable to increase the page size for disk-resident tables and
tables with large data items.
A suggested maximum size, in bytes, of the memory cache.
Setting this value to zero specifies that an appropriate amount of memory
indicates a desired density within the hash table.
It is an approximation of the number of keys allowed to accumulate in any
one bucket, determining when the hash table grows or shrinks.
is a user defined hash function.
Since no hash function performs equally well on all possible data, the
user may find that the built-in hash function does poorly on a particular
User specified hash functions must take two arguments (a pointer to a byte
string and a length) and return an u_long to be used as the hash value.
The byte order for 4-byte integers in the stored database metadata.
The number should represent the order as an integer; for example,
big endian order would be the number 4,321.
is 0 (no order is specified) the current host order is used.
If the file already exists, the specified value is ignored and the
value specified when the tree was created is used.
(Obviously, portability of the data forming the key/data pairs is the
concern of the application program.)
is an estimate of the final size of the hash table.
If not set, the default value is 1.
If not set or set too low, hash tables will expand gracefully as keys
are entered, although a slight performance degradation may be noticed.
data structure is NULL, the
routine will use appropriate values.
If the hash table already exists, and the O_TRUNC flag is not
If a hash function is specified,
will attempt to determine if the hash function specified is the same as
the one with which the database was created, and will fail if it is not.
Both key and data structures may reference byte strings of essentially
Backward compatible interfaces to the routines described in
are provided, however, these interfaces are not compatible with
One of the access methods is either variable or fixed-length records,
the former delimited by a specific byte value.
The access method specific data structure provided to
The elements of this structure are defined as follows:
The flag value is specified by
any of the following values:
The records are fixed-length, not byte delimited.
specifies the length of the record, and the structure element
is used as the pad character.
This flag requires that a snapshot of the file be taken when
is called, instead of permitting any unmodified records to be
read from the original file.
A suggested maximum size, in bytes, of the memory cache.
Setting this value to zero specifies that an appropriate amount of memory
The length of a fixed-length record.
The delimiting byte to be used to mark the end of a record for
variable-length records, and the pad character for fixed-length
Variable-length and fixed-length data files require
structures to reference the following structure:
The elements of this structure are defined as follows:
The length of the record.
The offset in the file at which the record is located.
A flag value which indicates the validity of the other fields in the
The flag value is specified by
one or more of the following values:
The record length is valid.
The record number is valid.
The byte offset is valid.
If the record retrieval is successful, the record number, byte offset and
record length are set in the RECNOKEY structure referenced by the caller's
Data structures may reference byte strings of essentially unlimited length.
routines may fail and set
for any of the errors specified for the library routines
A file used by one of the
routines is incorrectly formatted.
A parameter has been specified (hash function, pad byte etc.) that is
incompatible with the current file specification or there is a mismatch
between the version number of file and the software.
routines may fail and set
for any of the errors specified for the library routines
routines may fail and set
for any of the errors specified for the library routines
routines may fail and set
for any of the errors specified for the library routine
.IR "Dynamic Hash Tables" ,
Per-Ake Larson, Communications of the ACM, April 1988.
.IR "A New Hash Package for UNIX" ,
Margo Seltzer, USENIX Proceedings, Winter 1991.
The typedef DBT is a mnemonic for ``data base thang'', and was used
because noone could think of a reasonable name that wasn't already used.
None of the access methods provide any form of concurrent access,
locking, or transactions.
Only big and little endian byte order is supported.
projects / unix-history / blob