The world's most popular open source database
mysql/src/5.1-dbg/storage/innobase/include/btr0btr.h
Go to the documentation of this file.00001 /****************************************************** 00002 The B-tree 00003 00004 (c) 1994-1996 Innobase Oy 00005 00006 Created 6/2/1994 Heikki Tuuri 00007 *******************************************************/ 00008 00009 #ifndef btr0btr_h 00010 #define btr0btr_h 00011 00012 #include "univ.i" 00013 00014 #include "dict0dict.h" 00015 #include "data0data.h" 00016 #include "page0cur.h" 00017 #include "rem0rec.h" 00018 #include "mtr0mtr.h" 00019 #include "btr0types.h" 00020 00021 /* Maximum record size which can be stored on a page, without using the 00022 special big record storage structure */ 00023 00024 #define BTR_PAGE_MAX_REC_SIZE (UNIV_PAGE_SIZE / 2 - 200) 00025 00026 /* Latching modes for the search function (in btr0cur.*) */ 00027 #define BTR_SEARCH_LEAF RW_S_LATCH 00028 #define BTR_MODIFY_LEAF RW_X_LATCH 00029 #define BTR_NO_LATCHES RW_NO_LATCH 00030 #define BTR_MODIFY_TREE 33 00031 #define BTR_CONT_MODIFY_TREE 34 00032 #define BTR_SEARCH_PREV 35 00033 #define BTR_MODIFY_PREV 36 00034 00035 /* If this is ORed to the latch mode, it means that the search tuple will be 00036 inserted to the index, at the searched position */ 00037 #define BTR_INSERT 512 00038 00039 /* This flag ORed to latch mode says that we do the search in query 00040 optimization */ 00041 #define BTR_ESTIMATE 1024 00042 00043 /* This flag ORed to latch mode says that we can ignore possible 00044 UNIQUE definition on secondary indexes when we decide if we can use the 00045 insert buffer to speed up inserts */ 00046 #define BTR_IGNORE_SEC_UNIQUE 2048 00047 00048 /****************************************************************** 00049 Gets the root node of a tree and x-latches it. */ 00050 00051 page_t* 00052 btr_root_get( 00053 /*=========*/ 00054 /* out: root page, x-latched */ 00055 dict_tree_t* tree, /* in: index tree */ 00056 mtr_t* mtr); /* in: mtr */ 00057 /****************************************************************** 00058 Gets a buffer page and declares its latching order level. */ 00059 UNIV_INLINE 00060 page_t* 00061 btr_page_get( 00062 /*=========*/ 00063 ulint space, /* in: space id */ 00064 ulint page_no, /* in: page number */ 00065 ulint mode, /* in: latch mode */ 00066 mtr_t* mtr); /* in: mtr */ 00067 /****************************************************************** 00068 Gets the index id field of a page. */ 00069 UNIV_INLINE 00070 dulint 00071 btr_page_get_index_id( 00072 /*==================*/ 00073 /* out: index id */ 00074 page_t* page); /* in: index page */ 00075 /************************************************************ 00076 Gets the node level field in an index page. */ 00077 UNIV_INLINE 00078 ulint 00079 btr_page_get_level_low( 00080 /*===================*/ 00081 /* out: level, leaf level == 0 */ 00082 page_t* page); /* in: index page */ 00083 /************************************************************ 00084 Gets the node level field in an index page. */ 00085 UNIV_INLINE 00086 ulint 00087 btr_page_get_level( 00088 /*===============*/ 00089 /* out: level, leaf level == 0 */ 00090 page_t* page, /* in: index page */ 00091 mtr_t* mtr); /* in: mini-transaction handle */ 00092 /************************************************************ 00093 Gets the next index page number. */ 00094 UNIV_INLINE 00095 ulint 00096 btr_page_get_next( 00097 /*==============*/ 00098 /* out: next page number */ 00099 page_t* page, /* in: index page */ 00100 mtr_t* mtr); /* in: mini-transaction handle */ 00101 /************************************************************ 00102 Gets the previous index page number. */ 00103 UNIV_INLINE 00104 ulint 00105 btr_page_get_prev( 00106 /*==============*/ 00107 /* out: prev page number */ 00108 page_t* page, /* in: index page */ 00109 mtr_t* mtr); /* in: mini-transaction handle */ 00110 /***************************************************************** 00111 Gets pointer to the previous user record in the tree. It is assumed 00112 that the caller has appropriate latches on the page and its neighbor. */ 00113 00114 rec_t* 00115 btr_get_prev_user_rec( 00116 /*==================*/ 00117 /* out: previous user record, NULL if there is none */ 00118 rec_t* rec, /* in: record on leaf level */ 00119 mtr_t* mtr); /* in: mtr holding a latch on the page, and if 00120 needed, also to the previous page */ 00121 /***************************************************************** 00122 Gets pointer to the next user record in the tree. It is assumed 00123 that the caller has appropriate latches on the page and its neighbor. */ 00124 00125 rec_t* 00126 btr_get_next_user_rec( 00127 /*==================*/ 00128 /* out: next user record, NULL if there is none */ 00129 rec_t* rec, /* in: record on leaf level */ 00130 mtr_t* mtr); /* in: mtr holding a latch on the page, and if 00131 needed, also to the next page */ 00132 /****************************************************************** 00133 Releases the latch on a leaf page and bufferunfixes it. */ 00134 UNIV_INLINE 00135 void 00136 btr_leaf_page_release( 00137 /*==================*/ 00138 page_t* page, /* in: page */ 00139 ulint latch_mode, /* in: BTR_SEARCH_LEAF or BTR_MODIFY_LEAF */ 00140 mtr_t* mtr); /* in: mtr */ 00141 /****************************************************************** 00142 Gets the child node file address in a node pointer. */ 00143 UNIV_INLINE 00144 ulint 00145 btr_node_ptr_get_child_page_no( 00146 /*===========================*/ 00147 /* out: child node address */ 00148 rec_t* rec, /* in: node pointer record */ 00149 const ulint* offsets);/* in: array returned by rec_get_offsets() */ 00150 /**************************************************************** 00151 Creates the root node for a new index tree. */ 00152 00153 ulint 00154 btr_create( 00155 /*=======*/ 00156 /* out: page number of the created root, FIL_NULL if 00157 did not succeed */ 00158 ulint type, /* in: type of the index */ 00159 ulint space, /* in: space where created */ 00160 dulint index_id,/* in: index id */ 00161 ulint comp, /* in: nonzero=compact page format */ 00162 mtr_t* mtr); /* in: mini-transaction handle */ 00163 /**************************************************************** 00164 Frees a B-tree except the root page, which MUST be freed after this 00165 by calling btr_free_root. */ 00166 00167 void 00168 btr_free_but_not_root( 00169 /*==================*/ 00170 ulint space, /* in: space where created */ 00171 ulint root_page_no); /* in: root page number */ 00172 /**************************************************************** 00173 Frees the B-tree root page. Other tree MUST already have been freed. */ 00174 00175 void 00176 btr_free_root( 00177 /*==========*/ 00178 ulint space, /* in: space where created */ 00179 ulint root_page_no, /* in: root page number */ 00180 mtr_t* mtr); /* in: a mini-transaction which has already 00181 been started */ 00182 /***************************************************************** 00183 Makes tree one level higher by splitting the root, and inserts 00184 the tuple. It is assumed that mtr contains an x-latch on the tree. 00185 NOTE that the operation of this function must always succeed, 00186 we cannot reverse it: therefore enough free disk space must be 00187 guaranteed to be available before this function is called. */ 00188 00189 rec_t* 00190 btr_root_raise_and_insert( 00191 /*======================*/ 00192 /* out: inserted record */ 00193 btr_cur_t* cursor, /* in: cursor at which to insert: must be 00194 on the root page; when the function returns, 00195 the cursor is positioned on the predecessor 00196 of the inserted record */ 00197 dtuple_t* tuple, /* in: tuple to insert */ 00198 mtr_t* mtr); /* in: mtr */ 00199 /***************************************************************** 00200 Reorganizes an index page. */ 00201 00202 void 00203 btr_page_reorganize( 00204 /*================*/ 00205 page_t* page, /* in: page to be reorganized */ 00206 dict_index_t* index, /* in: record descriptor */ 00207 mtr_t* mtr); /* in: mtr */ 00208 /***************************************************************** 00209 Decides if the page should be split at the convergence point of 00210 inserts converging to left. */ 00211 00212 ibool 00213 btr_page_get_split_rec_to_left( 00214 /*===========================*/ 00215 /* out: TRUE if split recommended */ 00216 btr_cur_t* cursor, /* in: cursor at which to insert */ 00217 rec_t** split_rec);/* out: if split recommended, 00218 the first record on upper half page, 00219 or NULL if tuple should be first */ 00220 /***************************************************************** 00221 Decides if the page should be split at the convergence point of 00222 inserts converging to right. */ 00223 00224 ibool 00225 btr_page_get_split_rec_to_right( 00226 /*============================*/ 00227 /* out: TRUE if split recommended */ 00228 btr_cur_t* cursor, /* in: cursor at which to insert */ 00229 rec_t** split_rec);/* out: if split recommended, 00230 the first record on upper half page, 00231 or NULL if tuple should be first */ 00232 /***************************************************************** 00233 Splits an index page to halves and inserts the tuple. It is assumed 00234 that mtr holds an x-latch to the index tree. NOTE: the tree x-latch 00235 is released within this function! NOTE that the operation of this 00236 function must always succeed, we cannot reverse it: therefore 00237 enough free disk space must be guaranteed to be available before 00238 this function is called. */ 00239 00240 rec_t* 00241 btr_page_split_and_insert( 00242 /*======================*/ 00243 /* out: inserted record; NOTE: the tree 00244 x-latch is released! NOTE: 2 free disk 00245 pages must be available! */ 00246 btr_cur_t* cursor, /* in: cursor at which to insert; when the 00247 function returns, the cursor is positioned 00248 on the predecessor of the inserted record */ 00249 dtuple_t* tuple, /* in: tuple to insert */ 00250 mtr_t* mtr); /* in: mtr */ 00251 /*********************************************************** 00252 Inserts a data tuple to a tree on a non-leaf level. It is assumed 00253 that mtr holds an x-latch on the tree. */ 00254 00255 void 00256 btr_insert_on_non_leaf_level( 00257 /*=========================*/ 00258 dict_tree_t* tree, /* in: tree */ 00259 ulint level, /* in: level, must be > 0 */ 00260 dtuple_t* tuple, /* in: the record to be inserted */ 00261 mtr_t* mtr); /* in: mtr */ 00262 /******************************************************************** 00263 Sets a record as the predefined minimum record. */ 00264 00265 void 00266 btr_set_min_rec_mark( 00267 /*=================*/ 00268 rec_t* rec, /* in: record */ 00269 ulint comp, /* in: nonzero=compact page format */ 00270 mtr_t* mtr); /* in: mtr */ 00271 /***************************************************************** 00272 Deletes on the upper level the node pointer to a page. */ 00273 00274 void 00275 btr_node_ptr_delete( 00276 /*================*/ 00277 dict_tree_t* tree, /* in: index tree */ 00278 page_t* page, /* in: page whose node pointer is deleted */ 00279 mtr_t* mtr); /* in: mtr */ 00280 #ifdef UNIV_DEBUG 00281 /**************************************************************** 00282 Checks that the node pointer to a page is appropriate. */ 00283 00284 ibool 00285 btr_check_node_ptr( 00286 /*===============*/ 00287 /* out: TRUE */ 00288 dict_tree_t* tree, /* in: index tree */ 00289 page_t* page, /* in: index page */ 00290 mtr_t* mtr); /* in: mtr */ 00291 #endif /* UNIV_DEBUG */ 00292 /***************************************************************** 00293 Tries to merge the page first to the left immediate brother if such a 00294 brother exists, and the node pointers to the current page and to the 00295 brother reside on the same page. If the left brother does not satisfy these 00296 conditions, looks at the right brother. If the page is the only one on that 00297 level lifts the records of the page to the father page, thus reducing the 00298 tree height. It is assumed that mtr holds an x-latch on the tree and on the 00299 page. If cursor is on the leaf level, mtr must also hold x-latches to 00300 the brothers, if they exist. NOTE: it is assumed that the caller has reserved 00301 enough free extents so that the compression will always succeed if done! */ 00302 void 00303 btr_compress( 00304 /*=========*/ 00305 btr_cur_t* cursor, /* in: cursor on the page to merge or lift; 00306 the page must not be empty: in record delete 00307 use btr_discard_page if the page would become 00308 empty */ 00309 mtr_t* mtr); /* in: mtr */ 00310 /***************************************************************** 00311 Discards a page from a B-tree. This is used to remove the last record from 00312 a B-tree page: the whole page must be removed at the same time. This cannot 00313 be used for the root page, which is allowed to be empty. */ 00314 00315 void 00316 btr_discard_page( 00317 /*=============*/ 00318 btr_cur_t* cursor, /* in: cursor on the page to discard: not on 00319 the root page */ 00320 mtr_t* mtr); /* in: mtr */ 00321 /******************************************************************** 00322 Parses the redo log record for setting an index record as the predefined 00323 minimum record. */ 00324 00325 byte* 00326 btr_parse_set_min_rec_mark( 00327 /*=======================*/ 00328 /* out: end of log record or NULL */ 00329 byte* ptr, /* in: buffer */ 00330 byte* end_ptr,/* in: buffer end */ 00331 ulint comp, /* in: nonzero=compact page format */ 00332 page_t* page, /* in: page or NULL */ 00333 mtr_t* mtr); /* in: mtr or NULL */ 00334 /*************************************************************** 00335 Parses a redo log record of reorganizing a page. */ 00336 00337 byte* 00338 btr_parse_page_reorganize( 00339 /*======================*/ 00340 /* out: end of log record or NULL */ 00341 byte* ptr, /* in: buffer */ 00342 byte* end_ptr,/* in: buffer end */ 00343 dict_index_t* index, /* in: record descriptor */ 00344 page_t* page, /* in: page or NULL */ 00345 mtr_t* mtr); /* in: mtr or NULL */ 00346 /****************************************************************** 00347 Gets the number of pages in a B-tree. */ 00348 00349 ulint 00350 btr_get_size( 00351 /*=========*/ 00352 /* out: number of pages */ 00353 dict_index_t* index, /* in: index */ 00354 ulint flag); /* in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */ 00355 /****************************************************************** 00356 Allocates a new file page to be used in an index tree. NOTE: we assume 00357 that the caller has made the reservation for free extents! */ 00358 00359 page_t* 00360 btr_page_alloc( 00361 /*===========*/ 00362 /* out: new allocated page, x-latched; 00363 NULL if out of space */ 00364 dict_tree_t* tree, /* in: index tree */ 00365 ulint hint_page_no, /* in: hint of a good page */ 00366 byte file_direction, /* in: direction where a possible 00367 page split is made */ 00368 ulint level, /* in: level where the page is placed 00369 in the tree */ 00370 mtr_t* mtr); /* in: mtr */ 00371 /****************************************************************** 00372 Frees a file page used in an index tree. NOTE: cannot free field external 00373 storage pages because the page must contain info on its level. */ 00374 00375 void 00376 btr_page_free( 00377 /*==========*/ 00378 dict_tree_t* tree, /* in: index tree */ 00379 page_t* page, /* in: page to be freed, x-latched */ 00380 mtr_t* mtr); /* in: mtr */ 00381 /****************************************************************** 00382 Frees a file page used in an index tree. Can be used also to BLOB 00383 external storage pages, because the page level 0 can be given as an 00384 argument. */ 00385 00386 void 00387 btr_page_free_low( 00388 /*==============*/ 00389 dict_tree_t* tree, /* in: index tree */ 00390 page_t* page, /* in: page to be freed, x-latched */ 00391 ulint level, /* in: page level */ 00392 mtr_t* mtr); /* in: mtr */ 00393 #ifdef UNIV_BTR_PRINT 00394 /***************************************************************** 00395 Prints size info of a B-tree. */ 00396 00397 void 00398 btr_print_size( 00399 /*===========*/ 00400 dict_tree_t* tree); /* in: index tree */ 00401 /****************************************************************** 00402 Prints directories and other info of all nodes in the tree. */ 00403 00404 void 00405 btr_print_tree( 00406 /*===========*/ 00407 dict_tree_t* tree, /* in: tree */ 00408 ulint width); /* in: print this many entries from start 00409 and end */ 00410 #endif /* UNIV_BTR_PRINT */ 00411 /**************************************************************** 00412 Checks the size and number of fields in a record based on the definition of 00413 the index. */ 00414 00415 ibool 00416 btr_index_rec_validate( 00417 /*===================*/ 00418 /* out: TRUE if ok */ 00419 rec_t* rec, /* in: index record */ 00420 dict_index_t* index, /* in: index */ 00421 ibool dump_on_error); /* in: TRUE if the function 00422 should print hex dump of record 00423 and page on error */ 00424 /****************************************************************** 00425 Checks the consistency of an index tree. */ 00426 00427 ibool 00428 btr_validate_tree( 00429 /*==============*/ 00430 /* out: TRUE if ok */ 00431 dict_tree_t* tree, /* in: tree */ 00432 trx_t* trx); /* in: transaction or NULL */ 00433 00434 #define BTR_N_LEAF_PAGES 1 00435 #define BTR_TOTAL_SIZE 2 00436 00437 #ifndef UNIV_NONINL 00438 #include "btr0btr.ic" 00439 #endif 00440 00441 #endif
Generated on Sat Sep 9 00:50:26 2006 for MySQL 5.1 by
1.4.7
© 1995-2008 MySQL AB, 2008- Sun Microsystems, Inc.