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