Debian Codegraph @

upstream/debian-unstable/man3/btree.3

raw
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.