1.\" Copyright (c) 1990, 1993 2.\" The Regents of the University of California. All rights reserved. 3.\" 4.\" Redistribution and use in source and binary forms, with or without 5.\" modification, are permitted provided that the following conditions 6.\" are met: 7.\" 1. Redistributions of source code must retain the above copyright 8.\" notice, this list of conditions and the following disclaimer. 9.\" 2. Redistributions in binary form must reproduce the above copyright 10.\" notice, this list of conditions and the following disclaimer in the 11.\" documentation and/or other materials provided with the distribution. 12.\" 3. All advertising materials mentioning features or use of this software 13.\" must display the following acknowledgement: 14.\" This product includes software developed by the University of 15.\" California, Berkeley and its contributors. 16.\" 4. Neither the name of the University nor the names of its contributors 17.\" may be used to endorse or promote products derived from this software 18.\" without specific prior written permission. 19.\" 20.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30.\" SUCH DAMAGE. 31.\" 32.\" @(#)btree.3 8.4 (Berkeley) 8/18/94 33.\" $FreeBSD: src/lib/libc/db/man/btree.3,v 1.3.2.3 2003/03/15 15:11:05 trhodes Exp $ 34.\" $DragonFly: src/lib/libc/db/man/btree.3,v 1.2 2003/06/17 04:26:41 dillon Exp $ 35.\" 36.Dd August 18, 1994 37.Dt BTREE 3 38.Os 39.Sh NAME 40.Nm btree 41.Nd "btree database access method" 42.Sh SYNOPSIS 43.In sys/types.h 44.In db.h 45.Sh DESCRIPTION 46The routine 47.Fn dbopen 48is the library interface to database files. 49One of the supported file formats is 50.Nm 51files. 52The general description of the database access methods is in 53.Xr dbopen 3 , 54this manual page describes only the 55.Nm 56specific information. 57.Pp 58The 59.Nm 60data structure is a sorted, balanced tree structure storing 61associated key/data pairs. 62.Pp 63The 64.Nm 65access method specific data structure provided to 66.Fn dbopen 67is defined in the 68.Aq Pa db.h 69include file as follows: 70.Bd -literal 71typedef struct { 72 u_long flags; 73 u_int cachesize; 74 int maxkeypage; 75 int minkeypage; 76 u_int psize; 77 int (*compare)(const DBT *key1, const DBT *key2); 78 size_t (*prefix)(const DBT *key1, const DBT *key2); 79 int lorder; 80} BTREEINFO; 81.Ed 82.Pp 83The elements of this structure are as follows: 84.Bl -tag -width indent 85.It Va flags 86The flag value is specified by 87.Em or Ns 'ing 88any of the following values: 89.Bl -tag -width indent 90.It Dv R_DUP 91Permit duplicate keys in the tree, i.e. permit insertion if the key to be 92inserted already exists in the tree. 93The default behavior, as described in 94.Xr dbopen 3 , 95is to overwrite a matching key when inserting a new key or to fail if 96the 97.Dv R_NOOVERWRITE 98flag is specified. 99The 100.Dv R_DUP 101flag is overridden by the 102.Dv R_NOOVERWRITE 103flag, and if the 104.Dv R_NOOVERWRITE 105flag is specified, attempts to insert duplicate keys into 106the tree will fail. 107.Pp 108If the database contains duplicate keys, the order of retrieval of 109key/data pairs is undefined if the 110.Va get 111routine is used, however, 112.Va seq 113routine calls with the 114.Dv R_CURSOR 115flag set will always return the logical 116.Dq first 117of any group of duplicate keys. 118.El 119.It Va cachesize 120A suggested maximum size (in bytes) of the memory cache. 121This value is 122.Em only 123advisory, and the access method will allocate more memory rather than fail. 124Since every search examines the root page of the tree, caching the most 125recently used pages substantially improves access time. 126In addition, physical writes are delayed as long as possible, so a moderate 127cache can reduce the number of I/O operations significantly. 128Obviously, using a cache increases (but only increases) the likelihood of 129corruption or lost data if the system crashes while a tree is being modified. 130If 131.Va cachesize 132is 0 (no size is specified) a default cache is used. 133.It Va maxkeypage 134The maximum number of keys which will be stored on any single page. 135Not currently implemented. 136.\" The maximum number of keys which will be stored on any single page. 137.\" Because of the way the 138.\" .Nm 139.\" data structure works, 140.\" .Va maxkeypage 141.\" must always be greater than or equal to 2. 142.\" If 143.\" .Va maxkeypage 144.\" is 0 (no maximum number of keys is specified) the page fill factor is 145.\" made as large as possible (which is almost invariably what is wanted). 146.It Va minkeypage 147The minimum number of keys which will be stored on any single page. 148This value is used to determine which keys will be stored on overflow 149pages, i.e. if a key or data item is longer than the pagesize divided 150by the minkeypage value, it will be stored on overflow pages instead 151of in the page itself. 152If 153.Va minkeypage 154is 0 (no minimum number of keys is specified) a value of 2 is used. 155.It Va psize 156Page size is the size (in bytes) of the pages used for nodes in the tree. 157The minimum page size is 512 bytes and the maximum page size is 64K. 158If 159.Va psize 160is 0 (no page size is specified) a page size is chosen based on the 161underlying file system I/O block size. 162.It Va compare 163Compare is the key comparison function. 164It must return an integer less than, equal to, or greater than zero if the 165first key argument is considered to be respectively less than, equal to, 166or greater than the second key argument. 167The same comparison function must be used on a given tree every time it 168is opened. 169If 170.Va compare 171is 172.Dv NULL 173(no comparison function is specified), the keys are compared 174lexically, with shorter keys considered less than longer keys. 175.It Va prefix 176The 177.Va prefix 178element 179is the prefix comparison function. 180If specified, this routine must return the number of bytes of the second key 181argument which are necessary to determine that it is greater than the first 182key argument. 183If the keys are equal, the key length should be returned. 184Note, the usefulness of this routine is very data dependent, but, in some 185data sets can produce significantly reduced tree sizes and search times. 186If 187.Va prefix 188is 189.Dv NULL 190(no prefix function is specified), 191.Em and 192no comparison function is specified, a default lexical comparison routine 193is used. 194If 195.Va prefix 196is 197.Dv NULL 198and a comparison routine is specified, no prefix comparison is 199done. 200.It Va lorder 201The byte order for integers in the stored database metadata. 202The number should represent the order as an integer; for example, 203big endian order would be the number 4,321. 204If 205.Va lorder 206is 0 (no order is specified) the current host order is used. 207.El 208.Pp 209If the file already exists (and the 210.Dv O_TRUNC 211flag is not specified), the 212values specified for the 213.Va flags , lorder 214and 215.Va psize 216arguments 217are ignored 218in favor of the values used when the tree was created. 219.Pp 220Forward sequential scans of a tree are from the least key to the greatest. 221.Pp 222Space freed up by deleting key/data pairs from the tree is never reclaimed, 223although it is normally made available for reuse. 224This means that the 225.Nm 226storage structure is grow-only. 227The only solutions are to avoid excessive deletions, or to create a fresh 228tree periodically from a scan of an existing one. 229.Pp 230Searches, insertions, and deletions in a 231.Nm 232will all complete in 233O lg base N where base is the average fill factor. 234Often, inserting ordered data into 235.Nm Ns s 236results in a low fill factor. 237This implementation has been modified to make ordered insertion the best 238case, resulting in a much better than normal page fill factor. 239.Sh ERRORS 240The 241.Nm 242access method routines may fail and set 243.Va errno 244for any of the errors specified for the library routine 245.Xr dbopen 3 . 246.Sh SEE ALSO 247.Xr dbopen 3 , 248.Xr hash 3 , 249.Xr mpool 3 , 250.Xr recno 3 251.Rs 252.%T "The Ubiquitous B-tree" 253.%A Douglas Comer 254.%J "ACM Comput. Surv. 11" 255.%N 2 256.%D June 1979 257.%P 121-138 258.Re 259.Rs 260.%A Bayer 261.%A Unterauer 262.%T "Prefix B-trees" 263.%J "ACM Transactions on Database Systems" 264.%N 1 265.%V Vol. 2 266.%D March 1977 267.%P 11-26 268.Re 269.Rs 270.%B "The Art of Computer Programming Vol. 3: Sorting and Searching" 271.%A D. E. Knuth 272.%D 1968 273.%P 471-480 274.Re 275.Sh BUGS 276Only big and little endian byte order is supported. 277