lib/libc/db/man/btree.3

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