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