| .\" Copyright (c) 1990, 1993 |
| .\" The Regents of the University of California. All rights reserved. |
| .\" |
| .\" %%%LICENSE_START(BSD_4_CLAUSE_UCB) |
| .\" Redistribution and use in source and binary forms, with or without |
| .\" modification, are permitted provided that the following conditions |
| .\" are met: |
| .\" 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 |
| .\" SUCH DAMAGE. |
| .\" %%%LICENSE_END |
| .\" |
| .\" @(#)btree.3 8.4 (Berkeley) 8/18/94 |
| .\" |
| .TH BTREE 3 2012-04-23 "" "Linux Programmer's Manual" |
| .\".UC 7 |
| .SH NAME |
| btree \- btree database access method |
| .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 in glibc up until version 2.1. |
| Since version 2.2, glibc no longer provides these interfaces. |
| Probably, you are looking for the APIs provided by the |
| .I libdb |
| library instead. |
| |
| 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. |
| .PP |
| The btree data structure is a sorted, balanced tree structure storing |
| associated key/data pairs. |
| .PP |
| The btree access-method-specific data structure provided to |
| .BR dbopen (3) |
| is defined in the |
| .I <db.h> |
| include file as follows: |
| .in +4n |
| .nf |
| |
| 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; |
| .fi |
| .in |
| .PP |
| 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 64K. |
| 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. |
| .PP |
| If the file already exists (and the |
| .B O_TRUNC |
| flag is not specified), the |
| values specified for the arguments |
| .IR flags , |
| .I lorder |
| and |
| .I psize |
| are ignored |
| in favor of the values used when the tree was created. |
| .PP |
| Forward sequential scans of a tree are from the least key to the greatest. |
| .PP |
| 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. |
| .PP |
| 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) |
| |
| .IR "The Ubiquitous B-tree" , |
| Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121-138. |
| |
| .IR "Prefix B-trees" , |
| Bayer and Unterauer, ACM Transactions on Database Systems, Vol. 2, 1 |
| (March 1977), 11-26. |
| |
| .IR "The Art of Computer Programming Vol. 3: Sorting and Searching" , |
| D.E. Knuth, 1968, pp 471-480. |