diff options
Diffstat (limited to 'man3/btree.3')
| -rw-r--r-- | man3/btree.3 | 229 |
1 files changed, 0 insertions, 229 deletions
diff --git a/man3/btree.3 b/man3/btree.3 deleted file mode 100644 index e93e25b..0000000 --- a/man3/btree.3 +++ /dev/null @@ -1,229 +0,0 @@ -.\" 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 2023-10-31 "Linux man-pages 6.7" -.\".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. |