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