]>
Commit | Line | Data |
---|---|---|
fea681da MK |
1 | .\" Copyright (c) 1990, 1993 |
2 | .\" The Regents of the University of California. All rights reserved. | |
3 | .\" | |
a9cd9cb7 | 4 | .\" %%%LICENSE_START(BSD_4_CLAUSE_UCB) |
fea681da MK |
5 | .\" Redistribution and use in source and binary forms, with or without |
6 | .\" modification, are permitted provided that the following conditions | |
7 | .\" are met: | |
8 | .\" 1. Redistributions of source code must retain the above copyright | |
9 | .\" notice, this list of conditions and the following disclaimer. | |
10 | .\" 2. Redistributions in binary form must reproduce the above copyright | |
11 | .\" notice, this list of conditions and the following disclaimer in the | |
12 | .\" documentation and/or other materials provided with the distribution. | |
13 | .\" 3. All advertising materials mentioning features or use of this software | |
14 | .\" must display the following acknowledgement: | |
15 | .\" This product includes software developed by the University of | |
16 | .\" California, Berkeley and its contributors. | |
17 | .\" 4. Neither the name of the University nor the names of its contributors | |
18 | .\" may be used to endorse or promote products derived from this software | |
19 | .\" without specific prior written permission. | |
20 | .\" | |
21 | .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
22 | .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
23 | .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
24 | .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
25 | .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
26 | .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
27 | .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
28 | .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
29 | .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
30 | .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
31 | .\" SUCH DAMAGE. | |
8c9302dc | 32 | .\" %%%LICENSE_END |
fea681da MK |
33 | .\" |
34 | .\" @(#)btree.3 8.4 (Berkeley) 8/18/94 | |
35 | .\" | |
4b8c67d9 | 36 | .TH BTREE 3 2017-09-15 "" "Linux Programmer's Manual" |
fea681da MK |
37 | .\".UC 7 |
38 | .SH NAME | |
39 | btree \- btree database access method | |
40 | .SH SYNOPSIS | |
41 | .nf | |
42 | .ft B | |
43 | #include <sys/types.h> | |
44 | #include <db.h> | |
45 | .ft R | |
46 | .fi | |
47 | .SH DESCRIPTION | |
df21098d MK |
48 | .IR "Note well" : |
49 | This page documents interfaces provided in glibc up until version 2.1. | |
50 | Since version 2.2, glibc no longer provides these interfaces. | |
51 | Probably, you are looking for the APIs provided by the | |
52 | .I libdb | |
53 | library instead. | |
847e0d88 | 54 | .PP |
fea681da | 55 | The routine |
fb186734 | 56 | .BR dbopen (3) |
fea681da MK |
57 | is the library interface to database files. |
58 | One of the supported file formats is btree files. | |
59 | The general description of the database access methods is in | |
31e9a9ec | 60 | .BR dbopen (3), |
76c637e1 | 61 | this manual page describes only the btree-specific information. |
fea681da MK |
62 | .PP |
63 | The btree data structure is a sorted, balanced tree structure storing | |
64 | associated key/data pairs. | |
65 | .PP | |
76c637e1 | 66 | The btree access-method-specific data structure provided to |
fb186734 | 67 | .BR dbopen (3) |
e5056894 MK |
68 | is defined in the |
69 | .I <db.h> | |
70 | include file as follows: | |
e646a1ba | 71 | .PP |
088a639b | 72 | .in +4n |
e646a1ba | 73 | .EX |
fea681da | 74 | typedef struct { |
aeb4b1fc MK |
75 | unsigned long flags; |
76 | unsigned int cachesize; | |
77 | int maxkeypage; | |
78 | int minkeypage; | |
79 | unsigned int psize; | |
80 | int (*compare)(const DBT *key1, const DBT *key2); | |
81 | size_t (*prefix)(const DBT *key1, const DBT *key2); | |
82 | int lorder; | |
fea681da | 83 | } BTREEINFO; |
b8302363 | 84 | .EE |
ce4b0e57 | 85 | .in |
fea681da MK |
86 | .PP |
87 | The elements of this structure are as follows: | |
88 | .TP | |
e5056894 | 89 | .I flags |
cebca1bd | 90 | The flag value is specified by ORing any of the following values: |
fea681da MK |
91 | .RS |
92 | .TP | |
628d8d62 | 93 | .B R_DUP |
75b94dc3 MK |
94 | Permit duplicate keys in the tree, that is, |
95 | permit insertion if the key to be | |
fea681da MK |
96 | inserted already exists in the tree. |
97 | The default behavior, as described in | |
31e9a9ec | 98 | .BR dbopen (3), |
fea681da | 99 | is to overwrite a matching key when inserting a new key or to fail if |
628d8d62 MK |
100 | the |
101 | .B R_NOOVERWRITE | |
102 | flag is specified. | |
103 | The | |
104 | .B R_DUP | |
105 | flag is overridden by the | |
106 | .B R_NOOVERWRITE | |
107 | flag, and if the | |
40d6f0f0 MK |
108 | .B R_NOOVERWRITE |
109 | flag is specified, attempts to insert duplicate keys into | |
fea681da MK |
110 | the tree will fail. |
111 | .IP | |
112 | If the database contains duplicate keys, the order of retrieval of | |
113 | key/data pairs is undefined if the | |
114 | .I get | |
115 | routine is used, however, | |
116 | .I seq | |
628d8d62 MK |
117 | routine calls with the |
118 | .B R_CURSOR | |
119 | flag set will always return the logical | |
40d6f0f0 | 120 | "first" of any group of duplicate keys. |
fea681da MK |
121 | .RE |
122 | .TP | |
e5056894 | 123 | .I cachesize |
fea681da MK |
124 | A suggested maximum size (in bytes) of the memory cache. |
125 | This value is | |
836f07c1 | 126 | .I only |
fea681da MK |
127 | advisory, and the access method will allocate more memory rather than fail. |
128 | Since every search examines the root page of the tree, caching the most | |
129 | recently used pages substantially improves access time. | |
130 | In addition, physical writes are delayed as long as possible, so a moderate | |
131 | cache can reduce the number of I/O operations significantly. | |
132 | Obviously, using a cache increases (but only increases) the likelihood of | |
133 | corruption or lost data if the system crashes while a tree is being modified. | |
134 | If | |
135 | .I cachesize | |
113839c3 | 136 | is 0 (no size is specified), a default cache is used. |
fea681da | 137 | .TP |
e5056894 | 138 | .I maxkeypage |
fea681da MK |
139 | The maximum number of keys which will be stored on any single page. |
140 | Not currently implemented. | |
141 | .\" The maximum number of keys which will be stored on any single page. | |
142 | .\" Because of the way the btree data structure works, | |
143 | .\" .I maxkeypage | |
144 | .\" must always be greater than or equal to 2. | |
145 | .\" If | |
146 | .\" .I maxkeypage | |
113839c3 | 147 | .\" is 0 (no maximum number of keys is specified), the page fill factor is |
fea681da MK |
148 | .\" made as large as possible (which is almost invariably what is wanted). |
149 | .TP | |
e5056894 | 150 | .I minkeypage |
fea681da MK |
151 | The minimum number of keys which will be stored on any single page. |
152 | This value is used to determine which keys will be stored on overflow | |
75b94dc3 | 153 | pages, that is, if a key or data item is longer than the pagesize divided |
fea681da MK |
154 | by the minkeypage value, it will be stored on overflow pages instead |
155 | of in the page itself. | |
156 | If | |
157 | .I minkeypage | |
113839c3 | 158 | is 0 (no minimum number of keys is specified), a value of 2 is used. |
fea681da | 159 | .TP |
e5056894 | 160 | .I psize |
fea681da | 161 | Page size is the size (in bytes) of the pages used for nodes in the tree. |
ab5736e9 | 162 | The minimum page size is 512 bytes and the maximum page size is 64\ KiB. |
fea681da MK |
163 | If |
164 | .I psize | |
113839c3 | 165 | is 0 (no page size is specified), a page size is chosen based on the |
9ee4a2b6 | 166 | underlying filesystem I/O block size. |
fea681da | 167 | .TP |
e5056894 | 168 | .I compare |
fea681da MK |
169 | Compare is the key comparison function. |
170 | It must return an integer less than, equal to, or greater than zero if the | |
171 | first key argument is considered to be respectively less than, equal to, | |
172 | or greater than the second key argument. | |
173 | The same comparison function must be used on a given tree every time it | |
174 | is opened. | |
175 | If | |
176 | .I compare | |
177 | is NULL (no comparison function is specified), the keys are compared | |
178 | lexically, with shorter keys considered less than longer keys. | |
179 | .TP | |
e5056894 | 180 | .I prefix |
fea681da MK |
181 | Prefix is the prefix comparison function. |
182 | If specified, this routine must return the number of bytes of the second key | |
183 | argument which are necessary to determine that it is greater than the first | |
184 | key argument. | |
185 | If the keys are equal, the key length should be returned. | |
a43eed0c | 186 | Note, the usefulness of this routine is very data-dependent, but, in some |
fea681da MK |
187 | data sets can produce significantly reduced tree sizes and search times. |
188 | If | |
189 | .I prefix | |
190 | is NULL (no prefix function is specified), | |
836f07c1 | 191 | .I and |
fea681da MK |
192 | no comparison function is specified, a default lexical comparison routine |
193 | is used. | |
194 | If | |
195 | .I prefix | |
196 | is NULL and a comparison routine is specified, no prefix comparison is | |
197 | done. | |
198 | .TP | |
e5056894 | 199 | .I lorder |
fea681da | 200 | The byte order for integers in the stored database metadata. |
c13182ef | 201 | The number should represent the order as an integer; for example, |
fea681da MK |
202 | big endian order would be the number 4,321. |
203 | If | |
204 | .I lorder | |
113839c3 | 205 | is 0 (no order is specified), the current host order is used. |
fea681da | 206 | .PP |
c8fe3fa2 MK |
207 | If the file already exists (and the |
208 | .B O_TRUNC | |
209 | flag is not specified), the | |
c4bb193f | 210 | values specified for the arguments |
e5056894 MK |
211 | .IR flags , |
212 | .I lorder | |
213 | and | |
214 | .I psize | |
215 | are ignored | |
fea681da MK |
216 | in favor of the values used when the tree was created. |
217 | .PP | |
218 | Forward sequential scans of a tree are from the least key to the greatest. | |
219 | .PP | |
220 | Space freed up by deleting key/data pairs from the tree is never reclaimed, | |
221 | although it is normally made available for reuse. | |
222 | This means that the btree 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 btree will all complete in | |
227 | O lg base N where base is the average fill factor. | |
228 | Often, inserting ordered data into btrees results in a low fill factor. | |
229 | This implementation has been modified to make ordered insertion the best | |
230 | case, resulting in a much better than normal page fill factor. | |
231 | .SH ERRORS | |
232 | The | |
233 | .I btree | |
234 | access method routines may fail and set | |
235 | .I errno | |
236 | for any of the errors specified for the library routine | |
31e9a9ec | 237 | .BR dbopen (3). |
e37e3282 MK |
238 | .SH BUGS |
239 | Only big and little endian byte order is supported. | |
47297adb | 240 | .SH SEE ALSO |
31e9a9ec MK |
241 | .BR dbopen (3), |
242 | .BR hash (3), | |
243 | .BR mpool (3), | |
244 | .BR recno (3) | |
847e0d88 | 245 | .PP |
fea681da MK |
246 | .IR "The Ubiquitous B-tree" , |
247 | Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121-138. | |
847e0d88 | 248 | .PP |
fea681da MK |
249 | .IR "Prefix B-trees" , |
250 | Bayer and Unterauer, ACM Transactions on Database Systems, Vol. 2, 1 | |
251 | (March 1977), 11-26. | |
847e0d88 | 252 | .PP |
c13182ef | 253 | .IR "The Art of Computer Programming Vol. 3: Sorting and Searching" , |
fea681da | 254 | D.E. Knuth, 1968, pp 471-480. |