BTREE(3) | Library Functions Manual | BTREE(3) |
btree
— btree
database access method
#include
<sys/types.h>
#include <db.h>
The routine
dbopen
()
is the library interface to database files. One of the supported file
formats is btree
files. The general description of
the database access methods is in
dbopen(3), this manual page describes
only the btree
specific information.
The btree
data structure is a sorted,
balanced tree structure storing associated key/data pairs.
The btree
access method
specific data structure provided to
dbopen
()
is defined in the <db.h>
include file as follows:
typedef struct { u_long flags; u_int cachesize; int maxkeypage; int minkeypage; u_int psize; int (*compare)(const DBT *key1, const DBT *key2); size_t (*prefix)(const DBT *key1, const DBT *key2); int lorder; } BTREEINFO;
The elements of this structure are as follows:
R_DUP
R_NOOVERWRITE
flag is specified. The
R_DUP
flag is overridden by the
R_NOOVERWRITE
flag, and if the
R_NOOVERWRITE
flag is specified, attempts to
insert duplicate keys into the tree will fail.
If the database contains duplicate keys, the order of
retrieval of key/data pairs is undefined if the
get routine is used, however,
seq routine calls with the
R_CURSOR
flag set will always return the
logical “first” of any group of duplicate keys.
NULL
(no comparison function is specified), the
keys are compared lexically, with shorter keys considered less than longer
keys.NULL
(no prefix function is specified),
and no
comparison function is specified, a default lexical comparison routine is
used. If prefix is NULL
and
a comparison routine is specified, no prefix comparison is done.If the file already exists (and the
O_TRUNC
flag is not specified), the values specified
for the flags, lorder and
psize arguments are ignored in favor of the values
used when the tree was created.
Forward sequential scans of a tree are from the least key to the greatest.
Space freed up by deleting key/data pairs from the tree is never
reclaimed, although it is normally made available for reuse. 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.
Searches, insertions, and deletions in a
btree
will all complete in O lg base N where base is
the average fill factor. Often, inserting ordered data into
btree
s results in a low fill factor. This
implementation has been modified to make ordered insertion the best case,
resulting in a much better than normal page fill factor.
The btree
access method routines may fail
and set errno for any of the errors specified for the
library routine dbopen(3).
dbopen(3), hash(3), mpool(3), recno(3)
Douglas Comer, The Ubiquitous B-tree, ACM Comput. Surv. 11, 2, 121-138, June 1979.
Bayer and Unterauer, Prefix B-trees, ACM Transactions on Database Systems, 1, Vol. 2, 11-26, March 1977.
D. E. Knuth, The Art of Computer Programming Vol. 3: Sorting and Searching, 471-480, 1968.
Only big and little endian byte order is supported.
August 18, 1994 | macOS 14.6 |