BTREE(3) | Library Functions Manual | BTREE(3) |
btree
— btree
database access method
#include
<sys/types.h>
#include <db.h>
The
dbopen
()
routine 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 { unsigned long flags; unsigned int cachesize; int maxkeypage; int minkeypage; unsigned 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 parameters flags,
lorder, and psize 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 btrees 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).
Douglas Comer, The Ubiquitous B-tree, ACM Comput. Surv. 11, pp. 121–138, June 1979.
Rudolf Bayer and Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems, Vol. 2, 1, pp. 11–26, March 1977.
D. E. Knuth, The Art of Computer Programming Vol. 3: Sorting and Searching, pp. 471–480, 1968.
Only big and little endian byte order is supported.
April 23, 2019 | OpenBSD-current |