gitweb.dragonflybsd.org Git - dragonfly.git/blob

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.