diff options
Diffstat (limited to 'man/man3/btree.3')
| -rw-r--r-- | man/man3/btree.3 | 229 |
1 files changed, 229 insertions, 0 deletions
diff --git a/man/man3/btree.3 b/man/man3/btree.3 new file mode 100644 index 000000000..b3ce40c13 --- /dev/null +++ b/man/man3/btree.3 @@ -0,0 +1,229 @@ +.\" Copyright (c) 1990, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" SPDX-License-Identifier: BSD-4-Clause-UC +.\" +.\" @(#)btree.3 8.4 (Berkeley) 8/18/94 +.\" +.TH btree 3 (date) "Linux man-pages (unreleased)" +.\".UC 7 +.SH NAME +btree \- btree database access method +.SH LIBRARY +Standard C library +.RI ( libc ", " \-lc ) +.SH SYNOPSIS +.nf +.ft B +#include <sys/types.h> +#include <db.h> +.ft R +.fi +.SH DESCRIPTION +.IR "Note well" : +This page documents interfaces provided up until glibc 2.1. +Since glibc 2.2, glibc no longer provides these interfaces. +Probably, you are looking for the APIs provided by the +.I libdb +library instead. +.P +The routine +.BR dbopen (3) +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 +.BR dbopen (3), +this manual page describes only the btree-specific information. +.P +The btree data structure is a sorted, balanced tree structure storing +associated key/data pairs. +.P +The btree access-method-specific data structure provided to +.BR dbopen (3) +is defined in the +.I <db.h> +include file as follows: +.P +.in +4n +.EX +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; +.EE +.in +.P +The elements of this structure are as follows: +.TP +.I flags +The flag value is specified by ORing any of the following values: +.RS +.TP +.B R_DUP +Permit duplicate keys in the tree, that is, +permit insertion if the key to be +inserted already exists in the tree. +The default behavior, as described in +.BR dbopen (3), +is to overwrite a matching key when inserting a new key or to fail if +the +.B R_NOOVERWRITE +flag is specified. +The +.B R_DUP +flag is overridden by the +.B R_NOOVERWRITE +flag, and if the +.B R_NOOVERWRITE +flag is specified, attempts to insert duplicate keys into +the tree will fail. +.IP +If the database contains duplicate keys, the order of retrieval of +key/data pairs is undefined if the +.I get +routine is used, however, +.I seq +routine calls with the +.B R_CURSOR +flag set will always return the logical +"first" of any group of duplicate keys. +.RE +.TP +.I cachesize +A suggested maximum size (in bytes) of the memory cache. +This value is +.I only +advisory, and the access method will allocate more memory rather than fail. +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 (but only increases) the likelihood of +corruption or lost data if the system crashes while a tree is being modified. +If +.I cachesize +is 0 (no size is specified), a default cache is used. +.TP +.I maxkeypage +The maximum number of keys which will be stored on any single page. +Not currently implemented. +.\" The maximum number of keys which will be stored on any single page. +.\" Because of the way the btree data structure works, +.\" .I maxkeypage +.\" must always be greater than or equal to 2. +.\" If +.\" .I maxkeypage +.\" is 0 (no maximum number of keys is specified), the page fill factor is +.\" made as large as possible (which is almost invariably what is wanted). +.TP +.I minkeypage +The minimum number of keys which will be stored on any single page. +This value is used to determine which keys will be stored on overflow +pages, that is, if a key or data item is longer than the pagesize divided +by the minkeypage value, it will be stored on overflow pages instead +of in the page itself. +If +.I minkeypage +is 0 (no minimum number of keys is specified), a value of 2 is used. +.TP +.I psize +Page size is the size (in bytes) of the pages used for nodes in the tree. +The minimum page size is 512 bytes and the maximum page size is 64\ KiB. +If +.I psize +is 0 (no page size is specified), a page size is chosen based on the +underlying filesystem I/O block size. +.TP +.I compare +Compare is the key comparison function. +It must return an integer less than, equal to, or greater than zero if the +first key argument is considered to be respectively less than, equal to, +or greater than the second key argument. +The same comparison function must be used on a given tree every time it +is opened. +If +.I compare +is NULL (no comparison function is specified), the keys are compared +lexically, with shorter keys considered less than longer keys. +.TP +.I prefix +Prefix is the prefix comparison function. +If specified, this routine must return the number of bytes of the second key +argument which are necessary to determine that it is greater than the first +key argument. +If the keys are equal, the key length should be returned. +Note, the usefulness of this routine is very data-dependent, but, in some +data sets can produce significantly reduced tree sizes and search times. +If +.I prefix +is NULL (no prefix function is specified), +.I and +no comparison function is specified, a default lexical comparison routine +is used. +If +.I prefix +is NULL and a comparison routine is specified, no prefix comparison is +done. +.TP +.I lorder +The byte order for 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. +If +.I lorder +is 0 (no order is specified), the current host order is used. +.P +If the file already exists (and the +.B O_TRUNC +flag is not specified), the +values specified for the arguments +.IR flags , +.IR lorder , +and +.I psize +are ignored +in favor of the values used when the tree was created. +.P +Forward sequential scans of a tree are from the least key to the greatest. +.P +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. +.P +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. +.SH ERRORS +The +.I btree +access method routines may fail and set +.I errno +for any of the errors specified for the library routine +.BR dbopen (3). +.SH BUGS +Only big and little endian byte order is supported. +.SH SEE ALSO +.BR dbopen (3), +.BR hash (3), +.BR mpool (3), +.BR recno (3) +.P +.IR "The Ubiquitous B-tree" , +Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121-138. +.P +.IR "Prefix B-trees" , +Bayer and Unterauer, ACM Transactions on Database Systems, Vol. 2, 1 +(March 1977), 11-26. +.P +.IR "The Art of Computer Programming Vol. 3: Sorting and Searching" , +D.E. Knuth, 1968, pp 471-480. |