| 1 |
.\" Copyright 1990-1993, The Regents of the University of California. |
| 2 |
.\" Copyright, the authors of the Linux man-pages project |
| 3 |
.\" |
| 4 |
.\" SPDX-License-Identifier: BSD-4-Clause-UC |
| 5 |
.\" |
| 6 |
.TH btree 3 2025-09-21 "Linux man-pages 6.18" |
| 7 |
.\".UC 7 |
| 8 |
.SH NAME |
| 9 |
btree \- btree database access method |
| 10 |
.SH LIBRARY |
| 11 |
Standard C library |
| 12 |
.RI ( libc ,\~ \-lc ) |
| 13 |
.SH SYNOPSIS |
| 14 |
.nf |
| 15 |
.ft B |
| 16 |
#include <sys/types.h> |
| 17 |
#include <db.h> |
| 18 |
.ft R |
| 19 |
.fi |
| 20 |
.SH DESCRIPTION |
| 21 |
.IR "Note well" : |
| 22 |
This page documents interfaces provided up until glibc 2.1. |
| 23 |
Since glibc 2.2, glibc no longer provides these interfaces. |
| 24 |
Probably, you are looking for the APIs provided by the |
| 25 |
.I libdb |
| 26 |
library instead. |
| 27 |
.P |
| 28 |
The routine |
| 29 |
.BR dbopen (3) |
| 30 |
is the library interface to database files. |
| 31 |
One of the supported file formats is btree files. |
| 32 |
The general description of the database access methods is in |
| 33 |
.BR dbopen (3), |
| 34 |
this manual page describes only the btree-specific information. |
| 35 |
.P |
| 36 |
The btree data structure is a sorted, balanced tree structure storing |
| 37 |
associated key/data pairs. |
| 38 |
.P |
| 39 |
The btree access-method-specific data structure provided to |
| 40 |
.BR dbopen (3) |
| 41 |
is defined in the |
| 42 |
.I <db.h> |
| 43 |
include file as follows: |
| 44 |
.P |
| 45 |
.in +4n |
| 46 |
.EX |
| 47 |
typedef struct { |
| 48 |
unsigned long flags; |
| 49 |
unsigned int cachesize; |
| 50 |
int maxkeypage; |
| 51 |
int minkeypage; |
| 52 |
unsigned int psize; |
| 53 |
int (*compare)(const DBT *key1, const DBT *key2); |
| 54 |
size_t (*prefix)(const DBT *key1, const DBT *key2); |
| 55 |
int lorder; |
| 56 |
} BTREEINFO; |
| 57 |
.EE |
| 58 |
.in |
| 59 |
.P |
| 60 |
The elements of this structure are as follows: |
| 61 |
.TP |
| 62 |
.I flags |
| 63 |
The flag value is specified by ORing any of the following values: |
| 64 |
.RS |
| 65 |
.TP |
| 66 |
.B R_DUP |
| 67 |
Permit duplicate keys in the tree, that is, |
| 68 |
permit insertion if the key to be |
| 69 |
inserted already exists in the tree. |
| 70 |
The default behavior, as described in |
| 71 |
.BR dbopen (3), |
| 72 |
is to overwrite a matching key when inserting a new key or to fail if |
| 73 |
the |
| 74 |
.B R_NOOVERWRITE |
| 75 |
flag is specified. |
| 76 |
The |
| 77 |
.B R_DUP |
| 78 |
flag is overridden by the |
| 79 |
.B R_NOOVERWRITE |
| 80 |
flag, and if the |
| 81 |
.B R_NOOVERWRITE |
| 82 |
flag is specified, attempts to insert duplicate keys into |
| 83 |
the tree will fail. |
| 84 |
.IP |
| 85 |
If the database contains duplicate keys, the order of retrieval of |
| 86 |
key/data pairs is undefined if the |
| 87 |
.I get |
| 88 |
routine is used, however, |
| 89 |
.I seq |
| 90 |
routine calls with the |
| 91 |
.B R_CURSOR |
| 92 |
flag set will always return the logical |
| 93 |
"first" of any group of duplicate keys. |
| 94 |
.RE |
| 95 |
.TP |
| 96 |
.I cachesize |
| 97 |
A suggested maximum size (in bytes) of the memory cache. |
| 98 |
This value is |
| 99 |
.I only |
| 100 |
advisory, and the access method will allocate more memory rather than fail. |
| 101 |
Since every search examines the root page of the tree, caching the most |
| 102 |
recently used pages substantially improves access time. |
| 103 |
In addition, physical writes are delayed as long as possible, so a moderate |
| 104 |
cache can reduce the number of I/O operations significantly. |
| 105 |
Obviously, using a cache increases (but only increases) the likelihood of |
| 106 |
corruption or lost data if the system crashes while a tree is being modified. |
| 107 |
If |
| 108 |
.I cachesize |
| 109 |
is 0 (no size is specified), a default cache is used. |
| 110 |
.TP |
| 111 |
.I maxkeypage |
| 112 |
The maximum number of keys which will be stored on any single page. |
| 113 |
Not currently implemented. |
| 114 |
.\" The maximum number of keys which will be stored on any single page. |
| 115 |
.\" Because of the way the btree data structure works, |
| 116 |
.\" .I maxkeypage |
| 117 |
.\" must always be greater than or equal to 2. |
| 118 |
.\" If |
| 119 |
.\" .I maxkeypage |
| 120 |
.\" is 0 (no maximum number of keys is specified), the page fill factor is |
| 121 |
.\" made as large as possible (which is almost invariably what is wanted). |
| 122 |
.TP |
| 123 |
.I minkeypage |
| 124 |
The minimum number of keys which will be stored on any single page. |
| 125 |
This value is used to determine which keys will be stored on overflow |
| 126 |
pages, that is, if a key or data item is longer than the pagesize divided |
| 127 |
by the minkeypage value, it will be stored on overflow pages instead |
| 128 |
of in the page itself. |
| 129 |
If |
| 130 |
.I minkeypage |
| 131 |
is 0 (no minimum number of keys is specified), a value of 2 is used. |
| 132 |
.TP |
| 133 |
.I psize |
| 134 |
Page size is the size (in bytes) of the pages used for nodes in the tree. |
| 135 |
The minimum page size is 512 bytes and the maximum page size is 64\ KiB. |
| 136 |
If |
| 137 |
.I psize |
| 138 |
is 0 (no page size is specified), a page size is chosen based on the |
| 139 |
underlying filesystem I/O block size. |
| 140 |
.TP |
| 141 |
.I compare |
| 142 |
Compare is the key comparison function. |
| 143 |
It must return an integer less than, equal to, or greater than zero if the |
| 144 |
first key argument is considered to be respectively less than, equal to, |
| 145 |
or greater than the second key argument. |
| 146 |
The same comparison function must be used on a given tree every time it |
| 147 |
is opened. |
| 148 |
If |
| 149 |
.I compare |
| 150 |
is NULL (no comparison function is specified), the keys are compared |
| 151 |
lexically, with shorter keys considered less than longer keys. |
| 152 |
.TP |
| 153 |
.I prefix |
| 154 |
Prefix is the prefix comparison function. |
| 155 |
If specified, this routine must return the number of bytes of the second key |
| 156 |
argument which are necessary to determine that it is greater than the first |
| 157 |
key argument. |
| 158 |
If the keys are equal, the key length should be returned. |
| 159 |
Note, the usefulness of this routine is very data-dependent, but, in some |
| 160 |
data sets can produce significantly reduced tree sizes and search times. |
| 161 |
If |
| 162 |
.I prefix |
| 163 |
is NULL (no prefix function is specified), |
| 164 |
.I and |
| 165 |
no comparison function is specified, a default lexical comparison routine |
| 166 |
is used. |
| 167 |
If |
| 168 |
.I prefix |
| 169 |
is NULL and a comparison routine is specified, no prefix comparison is |
| 170 |
done. |
| 171 |
.TP |
| 172 |
.I lorder |
| 173 |
The byte order for integers in the stored database metadata. |
| 174 |
The number should represent the order as an integer; |
| 175 |
for example, |
| 176 |
big endian order would be the number 4,321. |
| 177 |
If |
| 178 |
.I lorder |
| 179 |
is 0 (no order is specified), the current host order is used. |
| 180 |
.P |
| 181 |
If the file already exists (and the |
| 182 |
.B O_TRUNC |
| 183 |
flag is not specified), the |
| 184 |
values specified for the arguments |
| 185 |
.IR flags , |
| 186 |
.IR lorder , |
| 187 |
and |
| 188 |
.I psize |
| 189 |
are ignored |
| 190 |
in favor of the values used when the tree was created. |
| 191 |
.P |
| 192 |
Forward sequential scans of a tree are from the least key to the greatest. |
| 193 |
.P |
| 194 |
Space freed up by deleting key/data pairs from the tree is never reclaimed, |
| 195 |
although it is normally made available for reuse. |
| 196 |
This means that the btree storage structure is grow-only. |
| 197 |
The only solutions are to avoid excessive deletions, or to create a fresh |
| 198 |
tree periodically from a scan of an existing one. |
| 199 |
.P |
| 200 |
Searches, insertions, and deletions in a btree will all complete in |
| 201 |
O lg base N where base is the average fill factor. |
| 202 |
Often, inserting ordered data into btrees results in a low fill factor. |
| 203 |
This implementation has been modified to make ordered insertion the best |
| 204 |
case, resulting in a much better than normal page fill factor. |
| 205 |
.SH ERRORS |
| 206 |
The |
| 207 |
.I btree |
| 208 |
access method routines may fail and set |
| 209 |
.I errno |
| 210 |
for any of the errors specified for the library routine |
| 211 |
.BR dbopen (3). |
| 212 |
.SH BUGS |
| 213 |
Only big and little endian byte order is supported. |
| 214 |
.SH SEE ALSO |
| 215 |
.BR dbopen (3), |
| 216 |
.BR hash (3), |
| 217 |
.BR mpool (3), |
| 218 |
.BR recno (3) |
| 219 |
.P |
| 220 |
.IR "The Ubiquitous B-tree" , |
| 221 |
Douglas Comer, ACM Comput.\& Surv.\& 11, 2 (June 1979), 121-138. |
| 222 |
.P |
| 223 |
.IR "Prefix B-trees" , |
| 224 |
Bayer and Unterauer, ACM Transactions on Database Systems, Vol.\& 2, 1 |
| 225 |
(March 1977), 11-26. |
| 226 |
.P |
| 227 |
.IR "The Art of Computer Programming Vol.\& 3: Sorting and Searching" , |
| 228 |
D.E.\& Knuth, 1968, pp 471-480. |