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