1 /***************************************************************************** 2 3 Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved. 4 Copyright (c) 2012, Facebook Inc. 5 6 This program is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License, version 2.0, 8 as published by the Free Software Foundation. 9 10 This program is also distributed with certain software (including 11 but not limited to OpenSSL) that is licensed under separate terms, 12 as designated in a particular file or component or in included license 13 documentation. The authors of MySQL hereby grant you an additional 14 permission to link the program and your derivative works with the 15 separately licensed software that they have included with MySQL. 16 17 This program is distributed in the hope that it will be useful, 18 but WITHOUT ANY WARRANTY; without even the implied warranty of 19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 20 GNU General Public License, version 2.0, for more details. 21 22 You should have received a copy of the GNU General Public License along with 23 this program; if not, write to the Free Software Foundation, Inc., 24 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA 25 26 *****************************************************************************/ 27 28 /**************************************************//** 29 @file include/btr0btr.h 30 The B-tree 31 32 Created 6/2/1994 Heikki Tuuri 33 *******************************************************/ 34 35 #ifndef btr0btr_h 36 #define btr0btr_h 37 38 #include "univ.i" 39 40 #include "dict0dict.h" 41 #include "data0data.h" 42 #include "page0cur.h" 43 #include "mtr0mtr.h" 44 #include "btr0types.h" 45 46 #ifndef UNIV_HOTBACKUP 47 /** Maximum record size which can be stored on a page, without using the 48 special big record storage structure */ 49 #define BTR_PAGE_MAX_REC_SIZE (UNIV_PAGE_SIZE / 2 - 200) 50 51 /** @brief Maximum depth of a B-tree in InnoDB. 52 53 Note that this isn't a maximum as such; none of the tree operations 54 avoid producing trees bigger than this. It is instead a "max depth 55 that other code must work with", useful for e.g. fixed-size arrays 56 that must store some information about each level in a tree. In other 57 words: if a B-tree with bigger depth than this is encountered, it is 58 not acceptable for it to lead to mysterious memory corruption, but it 59 is acceptable for the program to die with a clear assert failure. */ 60 #define BTR_MAX_LEVELS 100 61 62 /** Latching modes for btr_cur_search_to_nth_level(). */ 63 enum btr_latch_mode { 64 /** Search a record on a leaf page and S-latch it. */ 65 BTR_SEARCH_LEAF = RW_S_LATCH, 66 /** (Prepare to) modify a record on a leaf page and X-latch it. */ 67 BTR_MODIFY_LEAF = RW_X_LATCH, 68 /** Obtain no latches. */ 69 BTR_NO_LATCHES = RW_NO_LATCH, 70 /** Start modifying the entire B-tree. */ 71 BTR_MODIFY_TREE = 33, 72 /** Continue modifying the entire B-tree. */ 73 BTR_CONT_MODIFY_TREE = 34, 74 /** Search the previous record. */ 75 BTR_SEARCH_PREV = 35, 76 /** Modify the previous record. */ 77 BTR_MODIFY_PREV = 36 78 }; 79 80 /* BTR_INSERT, BTR_DELETE and BTR_DELETE_MARK are mutually exclusive. */ 81 82 /** If this is ORed to btr_latch_mode, it means that the search tuple 83 will be inserted to the index, at the searched position. 84 When the record is not in the buffer pool, try to use the insert buffer. */ 85 #define BTR_INSERT 512 86 87 /** This flag ORed to btr_latch_mode says that we do the search in query 88 optimization */ 89 #define BTR_ESTIMATE 1024 90 91 /** This flag ORed to BTR_INSERT says that we can ignore possible 92 UNIQUE definition on secondary indexes when we decide if we can use 93 the insert buffer to speed up inserts */ 94 #define BTR_IGNORE_SEC_UNIQUE 2048 95 96 /** Try to delete mark the record at the searched position using the 97 insert/delete buffer when the record is not in the buffer pool. */ 98 #define BTR_DELETE_MARK 4096 99 100 /** Try to purge the record at the searched position using the insert/delete 101 buffer when the record is not in the buffer pool. */ 102 #define BTR_DELETE 8192 103 104 /** In the case of BTR_SEARCH_LEAF or BTR_MODIFY_LEAF, the caller is 105 already holding an S latch on the index tree */ 106 #define BTR_ALREADY_S_LATCHED 16384 107 108 #define BTR_LATCH_MODE_WITHOUT_FLAGS(latch_mode) \ 109 ((latch_mode) & ~(BTR_INSERT \ 110 | BTR_DELETE_MARK \ 111 | BTR_DELETE \ 112 | BTR_ESTIMATE \ 113 | BTR_IGNORE_SEC_UNIQUE \ 114 | BTR_ALREADY_S_LATCHED)) 115 #endif /* UNIV_HOTBACKUP */ 116 117 /**************************************************************//** 118 Report that an index page is corrupted. */ 119 UNIV_INTERN 120 void 121 btr_corruption_report( 122 /*==================*/ 123 const buf_block_t* block, /*!< in: corrupted block */ 124 const dict_index_t* index) /*!< in: index tree */ 125 UNIV_COLD MY_ATTRIBUTE((nonnull)); 126 127 /** Assert that a B-tree page is not corrupted. 128 @param block buffer block containing a B-tree page 129 @param index the B-tree index */ 130 #define btr_assert_not_corrupted(block, index) \ 131 if ((ibool) !!page_is_comp(buf_block_get_frame(block)) \ 132 != dict_table_is_comp((index)->table)) { \ 133 btr_corruption_report(block, index); \ 134 ut_error; \ 135 } 136 137 #ifndef UNIV_HOTBACKUP 138 #ifdef UNIV_BLOB_DEBUG 139 # include "ut0rbt.h" 140 /** An index->blobs entry for keeping track of off-page column references */ 141 struct btr_blob_dbg_t 142 { 143 unsigned blob_page_no:32; /*!< first BLOB page number */ 144 unsigned ref_page_no:32; /*!< referring page number */ 145 unsigned ref_heap_no:16; /*!< referring heap number */ 146 unsigned ref_field_no:10; /*!< referring field number */ 147 unsigned owner:1; /*!< TRUE if BLOB owner */ 148 unsigned always_owner:1; /*!< TRUE if always 149 has been the BLOB owner; 150 reset to TRUE on B-tree 151 page splits and merges */ 152 unsigned del:1; /*!< TRUE if currently 153 delete-marked */ 154 }; 155 156 /**************************************************************//** 157 Add a reference to an off-page column to the index->blobs map. */ 158 UNIV_INTERN 159 void 160 btr_blob_dbg_add_blob( 161 /*==================*/ 162 const rec_t* rec, /*!< in: clustered index record */ 163 ulint field_no, /*!< in: number of off-page column */ 164 ulint page_no, /*!< in: start page of the column */ 165 dict_index_t* index, /*!< in/out: index tree */ 166 const char* ctx) /*!< in: context (for logging) */ 167 MY_ATTRIBUTE((nonnull)); 168 /**************************************************************//** 169 Display the references to off-page columns. 170 This function is to be called from a debugger, 171 for example when a breakpoint on ut_dbg_assertion_failed is hit. */ 172 UNIV_INTERN 173 void 174 btr_blob_dbg_print( 175 /*===============*/ 176 const dict_index_t* index) /*!< in: index tree */ 177 MY_ATTRIBUTE((nonnull)); 178 /**************************************************************//** 179 Check that there are no references to off-page columns from or to 180 the given page. Invoked when freeing or clearing a page. 181 @return TRUE when no orphan references exist */ 182 UNIV_INTERN 183 ibool 184 btr_blob_dbg_is_empty( 185 /*==================*/ 186 dict_index_t* index, /*!< in: index */ 187 ulint page_no) /*!< in: page number */ 188 MY_ATTRIBUTE((nonnull, warn_unused_result)); 189 190 /**************************************************************//** 191 Modify the 'deleted' flag of a record. */ 192 UNIV_INTERN 193 void 194 btr_blob_dbg_set_deleted_flag( 195 /*==========================*/ 196 const rec_t* rec, /*!< in: record */ 197 dict_index_t* index, /*!< in/out: index */ 198 const ulint* offsets,/*!< in: rec_get_offs(rec, index) */ 199 ibool del) /*!< in: TRUE=deleted, FALSE=exists */ 200 MY_ATTRIBUTE((nonnull)); 201 /**************************************************************//** 202 Change the ownership of an off-page column. */ 203 UNIV_INTERN 204 void 205 btr_blob_dbg_owner( 206 /*===============*/ 207 const rec_t* rec, /*!< in: record */ 208 dict_index_t* index, /*!< in/out: index */ 209 const ulint* offsets,/*!< in: rec_get_offs(rec, index) */ 210 ulint i, /*!< in: ith field in rec */ 211 ibool own) /*!< in: TRUE=owned, FALSE=disowned */ 212 MY_ATTRIBUTE((nonnull)); 213 /** Assert that there are no BLOB references to or from the given page. */ 214 # define btr_blob_dbg_assert_empty(index, page_no) \ 215 ut_a(btr_blob_dbg_is_empty(index, page_no)) 216 #else /* UNIV_BLOB_DEBUG */ 217 # define btr_blob_dbg_add_blob(rec, field_no, page, index, ctx) ((void) 0) 218 # define btr_blob_dbg_set_deleted_flag(rec, index, offsets, del)((void) 0) 219 # define btr_blob_dbg_owner(rec, index, offsets, i, val) ((void) 0) 220 # define btr_blob_dbg_assert_empty(index, page_no) ((void) 0) 221 #endif /* UNIV_BLOB_DEBUG */ 222 223 /**************************************************************//** 224 Gets the root node of a tree and x-latches it. 225 @return root page, x-latched */ 226 UNIV_INTERN 227 page_t* 228 btr_root_get( 229 /*=========*/ 230 const dict_index_t* index, /*!< in: index tree */ 231 mtr_t* mtr) /*!< in: mtr */ 232 MY_ATTRIBUTE((nonnull)); 233 234 /**************************************************************//** 235 Checks and adjusts the root node of a tree during IMPORT TABLESPACE. 236 @return error code, or DB_SUCCESS */ 237 UNIV_INTERN 238 dberr_t 239 btr_root_adjust_on_import( 240 /*======================*/ 241 const dict_index_t* index) /*!< in: index tree */ 242 MY_ATTRIBUTE((nonnull, warn_unused_result)); 243 244 /**************************************************************//** 245 Gets the height of the B-tree (the level of the root, when the leaf 246 level is assumed to be 0). The caller must hold an S or X latch on 247 the index. 248 @return tree height (level of the root) */ 249 UNIV_INTERN 250 ulint 251 btr_height_get( 252 /*===========*/ 253 dict_index_t* index, /*!< in: index tree */ 254 mtr_t* mtr) /*!< in/out: mini-transaction */ 255 MY_ATTRIBUTE((nonnull, warn_unused_result)); 256 /**************************************************************//** 257 Gets a buffer page and declares its latching order level. */ 258 UNIV_INLINE 259 buf_block_t* 260 btr_block_get_func( 261 /*===============*/ 262 ulint space, /*!< in: space id */ 263 ulint zip_size, /*!< in: compressed page size in bytes 264 or 0 for uncompressed pages */ 265 ulint page_no, /*!< in: page number */ 266 ulint mode, /*!< in: latch mode */ 267 const char* file, /*!< in: file name */ 268 ulint line, /*!< in: line where called */ 269 # ifdef UNIV_SYNC_DEBUG 270 const dict_index_t* index, /*!< in: index tree, may be NULL 271 if it is not an insert buffer tree */ 272 # endif /* UNIV_SYNC_DEBUG */ 273 mtr_t* mtr); /*!< in/out: mini-transaction */ 274 # ifdef UNIV_SYNC_DEBUG 275 /** Gets a buffer page and declares its latching order level. 276 @param space tablespace identifier 277 @param zip_size compressed page size in bytes or 0 for uncompressed pages 278 @param page_no page number 279 @param mode latch mode 280 @param index index tree, may be NULL if not the insert buffer tree 281 @param mtr mini-transaction handle 282 @return the block descriptor */ 283 # define btr_block_get(space,zip_size,page_no,mode,index,mtr) \ 284 btr_block_get_func(space,zip_size,page_no,mode, \ 285 __FILE__,__LINE__,index,mtr) 286 # else /* UNIV_SYNC_DEBUG */ 287 /** Gets a buffer page and declares its latching order level. 288 @param space tablespace identifier 289 @param zip_size compressed page size in bytes or 0 for uncompressed pages 290 @param page_no page number 291 @param mode latch mode 292 @param idx index tree, may be NULL if not the insert buffer tree 293 @param mtr mini-transaction handle 294 @return the block descriptor */ 295 # define btr_block_get(space,zip_size,page_no,mode,idx,mtr) \ 296 btr_block_get_func(space,zip_size,page_no,mode,__FILE__,__LINE__,mtr) 297 # endif /* UNIV_SYNC_DEBUG */ 298 /** Gets a buffer page and declares its latching order level. 299 @param space tablespace identifier 300 @param zip_size compressed page size in bytes or 0 for uncompressed pages 301 @param page_no page number 302 @param mode latch mode 303 @param idx index tree, may be NULL if not the insert buffer tree 304 @param mtr mini-transaction handle 305 @return the uncompressed page frame */ 306 # define btr_page_get(space,zip_size,page_no,mode,idx,mtr) \ 307 buf_block_get_frame(btr_block_get(space,zip_size,page_no,mode,idx,mtr)) 308 #endif /* !UNIV_HOTBACKUP */ 309 /**************************************************************//** 310 Gets the index id field of a page. 311 @return index id */ 312 UNIV_INLINE 313 index_id_t 314 btr_page_get_index_id( 315 /*==================*/ 316 const page_t* page) /*!< in: index page */ 317 MY_ATTRIBUTE((nonnull, pure, warn_unused_result)); 318 #ifndef UNIV_HOTBACKUP 319 /********************************************************//** 320 Gets the node level field in an index page. 321 @return level, leaf level == 0 */ 322 UNIV_INLINE 323 ulint 324 btr_page_get_level_low( 325 /*===================*/ 326 const page_t* page) /*!< in: index page */ 327 MY_ATTRIBUTE((nonnull, pure, warn_unused_result)); 328 #define btr_page_get_level(page, mtr) btr_page_get_level_low(page) 329 /********************************************************//** 330 Gets the next index page number. 331 @return next page number */ 332 UNIV_INLINE 333 ulint 334 btr_page_get_next( 335 /*==============*/ 336 const page_t* page, /*!< in: index page */ 337 mtr_t* mtr) /*!< in: mini-transaction handle */ 338 MY_ATTRIBUTE((nonnull, warn_unused_result)); 339 /********************************************************//** 340 Gets the previous index page number. 341 @return prev page number */ 342 UNIV_INLINE 343 ulint 344 btr_page_get_prev( 345 /*==============*/ 346 const page_t* page, /*!< in: index page */ 347 mtr_t* mtr) /*!< in: mini-transaction handle */ 348 MY_ATTRIBUTE((nonnull, warn_unused_result)); 349 /*************************************************************//** 350 Gets pointer to the previous user record in the tree. It is assumed 351 that the caller has appropriate latches on the page and its neighbor. 352 @return previous user record, NULL if there is none */ 353 UNIV_INTERN 354 rec_t* 355 btr_get_prev_user_rec( 356 /*==================*/ 357 rec_t* rec, /*!< in: record on leaf level */ 358 mtr_t* mtr) /*!< in: mtr holding a latch on the page, and if 359 needed, also to the previous page */ 360 MY_ATTRIBUTE((nonnull, warn_unused_result)); 361 /*************************************************************//** 362 Gets pointer to the next user record in the tree. It is assumed 363 that the caller has appropriate latches on the page and its neighbor. 364 @return next user record, NULL if there is none */ 365 UNIV_INTERN 366 rec_t* 367 btr_get_next_user_rec( 368 /*==================*/ 369 rec_t* rec, /*!< in: record on leaf level */ 370 mtr_t* mtr) /*!< in: mtr holding a latch on the page, and if 371 needed, also to the next page */ 372 MY_ATTRIBUTE((nonnull, warn_unused_result)); 373 /**************************************************************//** 374 Releases the latch on a leaf page and bufferunfixes it. */ 375 UNIV_INLINE 376 void 377 btr_leaf_page_release( 378 /*==================*/ 379 buf_block_t* block, /*!< in: buffer block */ 380 ulint latch_mode, /*!< in: BTR_SEARCH_LEAF or 381 BTR_MODIFY_LEAF */ 382 mtr_t* mtr) /*!< in: mtr */ 383 MY_ATTRIBUTE((nonnull)); 384 /**************************************************************//** 385 Gets the child node file address in a node pointer. 386 NOTE: the offsets array must contain all offsets for the record since 387 we read the last field according to offsets and assume that it contains 388 the child page number. In other words offsets must have been retrieved 389 with rec_get_offsets(n_fields=ULINT_UNDEFINED). 390 @return child node address */ 391 UNIV_INLINE 392 ulint 393 btr_node_ptr_get_child_page_no( 394 /*===========================*/ 395 const rec_t* rec, /*!< in: node pointer record */ 396 const ulint* offsets)/*!< in: array returned by rec_get_offsets() */ 397 MY_ATTRIBUTE((nonnull, pure, warn_unused_result)); 398 /************************************************************//** 399 Creates the root node for a new index tree. 400 @return page number of the created root, FIL_NULL if did not succeed */ 401 UNIV_INTERN 402 ulint 403 btr_create( 404 /*=======*/ 405 ulint type, /*!< in: type of the index */ 406 ulint space, /*!< in: space where created */ 407 ulint zip_size,/*!< in: compressed page size in bytes 408 or 0 for uncompressed pages */ 409 index_id_t index_id,/*!< in: index id */ 410 dict_index_t* index, /*!< in: index */ 411 mtr_t* mtr) /*!< in: mini-transaction handle */ 412 MY_ATTRIBUTE((nonnull)); 413 /************************************************************//** 414 Frees a B-tree except the root page, which MUST be freed after this 415 by calling btr_free_root. */ 416 UNIV_INTERN 417 void 418 btr_free_but_not_root( 419 /*==================*/ 420 ulint space, /*!< in: space where created */ 421 ulint zip_size, /*!< in: compressed page size in bytes 422 or 0 for uncompressed pages */ 423 ulint root_page_no); /*!< in: root page number */ 424 /************************************************************//** 425 Frees the B-tree root page. Other tree MUST already have been freed. */ 426 UNIV_INTERN 427 void 428 btr_free_root( 429 /*==========*/ 430 ulint space, /*!< in: space where created */ 431 ulint zip_size, /*!< in: compressed page size in bytes 432 or 0 for uncompressed pages */ 433 ulint root_page_no, /*!< in: root page number */ 434 mtr_t* mtr) /*!< in/out: mini-transaction */ 435 MY_ATTRIBUTE((nonnull)); 436 /*************************************************************//** 437 Makes tree one level higher by splitting the root, and inserts 438 the tuple. It is assumed that mtr contains an x-latch on the tree. 439 NOTE that the operation of this function must always succeed, 440 we cannot reverse it: therefore enough free disk space must be 441 guaranteed to be available before this function is called. 442 @return inserted record */ 443 UNIV_INTERN 444 rec_t* 445 btr_root_raise_and_insert( 446 /*======================*/ 447 ulint flags, /*!< in: undo logging and locking flags */ 448 btr_cur_t* cursor, /*!< in: cursor at which to insert: must be 449 on the root page; when the function returns, 450 the cursor is positioned on the predecessor 451 of the inserted record */ 452 ulint** offsets,/*!< out: offsets on inserted record */ 453 mem_heap_t** heap, /*!< in/out: pointer to memory heap 454 that can be emptied, or NULL */ 455 const dtuple_t* tuple, /*!< in: tuple to insert */ 456 ulint n_ext, /*!< in: number of externally stored columns */ 457 mtr_t* mtr) /*!< in: mtr */ 458 MY_ATTRIBUTE((nonnull, warn_unused_result)); 459 /*************************************************************//** 460 Reorganizes an index page. 461 462 IMPORTANT: On success, the caller will have to update IBUF_BITMAP_FREE 463 if this is a compressed leaf page in a secondary index. This has to 464 be done either within the same mini-transaction, or by invoking 465 ibuf_reset_free_bits() before mtr_commit(). On uncompressed pages, 466 IBUF_BITMAP_FREE is unaffected by reorganization. 467 468 @retval true if the operation was successful 469 @retval false if it is a compressed page, and recompression failed */ 470 UNIV_INTERN 471 bool 472 btr_page_reorganize_low( 473 /*====================*/ 474 bool recovery,/*!< in: true if called in recovery: 475 locks should not be updated, i.e., 476 there cannot exist locks on the 477 page, and a hash index should not be 478 dropped: it cannot exist */ 479 ulint z_level,/*!< in: compression level to be used 480 if dealing with compressed page */ 481 page_cur_t* cursor, /*!< in/out: page cursor */ 482 dict_index_t* index, /*!< in: the index tree of the page */ 483 mtr_t* mtr) /*!< in/out: mini-transaction */ 484 MY_ATTRIBUTE((nonnull, warn_unused_result)); 485 /*************************************************************//** 486 Reorganizes an index page. 487 488 IMPORTANT: On success, the caller will have to update IBUF_BITMAP_FREE 489 if this is a compressed leaf page in a secondary index. This has to 490 be done either within the same mini-transaction, or by invoking 491 ibuf_reset_free_bits() before mtr_commit(). On uncompressed pages, 492 IBUF_BITMAP_FREE is unaffected by reorganization. 493 494 @retval true if the operation was successful 495 @retval false if it is a compressed page, and recompression failed */ 496 UNIV_INTERN 497 bool 498 btr_page_reorganize( 499 /*================*/ 500 page_cur_t* cursor, /*!< in/out: page cursor */ 501 dict_index_t* index, /*!< in: the index tree of the page */ 502 mtr_t* mtr) /*!< in/out: mini-transaction */ 503 MY_ATTRIBUTE((nonnull)); 504 /*************************************************************//** 505 Decides if the page should be split at the convergence point of 506 inserts converging to left. 507 @return TRUE if split recommended */ 508 UNIV_INTERN 509 ibool 510 btr_page_get_split_rec_to_left( 511 /*===========================*/ 512 btr_cur_t* cursor, /*!< in: cursor at which to insert */ 513 rec_t** split_rec)/*!< out: if split recommended, 514 the first record on upper half page, 515 or NULL if tuple should be first */ 516 MY_ATTRIBUTE((nonnull, warn_unused_result)); 517 /*************************************************************//** 518 Decides if the page should be split at the convergence point of 519 inserts converging to right. 520 @return TRUE if split recommended */ 521 UNIV_INTERN 522 ibool 523 btr_page_get_split_rec_to_right( 524 /*============================*/ 525 btr_cur_t* cursor, /*!< in: cursor at which to insert */ 526 rec_t** split_rec)/*!< out: if split recommended, 527 the first record on upper half page, 528 or NULL if tuple should be first */ 529 MY_ATTRIBUTE((nonnull, warn_unused_result)); 530 /*************************************************************//** 531 Splits an index page to halves and inserts the tuple. It is assumed 532 that mtr holds an x-latch to the index tree. NOTE: the tree x-latch is 533 released within this function! NOTE that the operation of this 534 function must always succeed, we cannot reverse it: therefore enough 535 free disk space (2 pages) must be guaranteed to be available before 536 this function is called. 537 538 @return inserted record */ 539 UNIV_INTERN 540 rec_t* 541 btr_page_split_and_insert( 542 /*======================*/ 543 ulint flags, /*!< in: undo logging and locking flags */ 544 btr_cur_t* cursor, /*!< in: cursor at which to insert; when the 545 function returns, the cursor is positioned 546 on the predecessor of the inserted record */ 547 ulint** offsets,/*!< out: offsets on inserted record */ 548 mem_heap_t** heap, /*!< in/out: pointer to memory heap 549 that can be emptied, or NULL */ 550 const dtuple_t* tuple, /*!< in: tuple to insert */ 551 ulint n_ext, /*!< in: number of externally stored columns */ 552 mtr_t* mtr) /*!< in: mtr */ 553 MY_ATTRIBUTE((nonnull, warn_unused_result)); 554 /*******************************************************//** 555 Inserts a data tuple to a tree on a non-leaf level. It is assumed 556 that mtr holds an x-latch on the tree. */ 557 UNIV_INTERN 558 void 559 btr_insert_on_non_leaf_level_func( 560 /*==============================*/ 561 ulint flags, /*!< in: undo logging and locking flags */ 562 dict_index_t* index, /*!< in: index */ 563 ulint level, /*!< in: level, must be > 0 */ 564 dtuple_t* tuple, /*!< in: the record to be inserted */ 565 const char* file, /*!< in: file name */ 566 ulint line, /*!< in: line where called */ 567 mtr_t* mtr) /*!< in: mtr */ 568 MY_ATTRIBUTE((nonnull)); 569 # define btr_insert_on_non_leaf_level(f,i,l,t,m) \ 570 btr_insert_on_non_leaf_level_func(f,i,l,t,__FILE__,__LINE__,m) 571 #endif /* !UNIV_HOTBACKUP */ 572 /****************************************************************//** 573 Sets a record as the predefined minimum record. */ 574 UNIV_INTERN 575 void 576 btr_set_min_rec_mark( 577 /*=================*/ 578 rec_t* rec, /*!< in/out: record */ 579 mtr_t* mtr) /*!< in: mtr */ 580 MY_ATTRIBUTE((nonnull)); 581 #ifndef UNIV_HOTBACKUP 582 /*************************************************************//** 583 Deletes on the upper level the node pointer to a page. */ 584 UNIV_INTERN 585 void 586 btr_node_ptr_delete( 587 /*================*/ 588 dict_index_t* index, /*!< in: index tree */ 589 buf_block_t* block, /*!< in: page whose node pointer is deleted */ 590 mtr_t* mtr) /*!< in: mtr */ 591 MY_ATTRIBUTE((nonnull)); 592 #ifdef UNIV_DEBUG 593 /************************************************************//** 594 Checks that the node pointer to a page is appropriate. 595 @return TRUE */ 596 UNIV_INTERN 597 ibool 598 btr_check_node_ptr( 599 /*===============*/ 600 dict_index_t* index, /*!< in: index tree */ 601 buf_block_t* block, /*!< in: index page */ 602 mtr_t* mtr) /*!< in: mtr */ 603 MY_ATTRIBUTE((nonnull, warn_unused_result)); 604 #endif /* UNIV_DEBUG */ 605 /*************************************************************//** 606 Tries to merge the page first to the left immediate brother if such a 607 brother exists, and the node pointers to the current page and to the 608 brother reside on the same page. If the left brother does not satisfy these 609 conditions, looks at the right brother. If the page is the only one on that 610 level lifts the records of the page to the father page, thus reducing the 611 tree height. It is assumed that mtr holds an x-latch on the tree and on the 612 page. If cursor is on the leaf level, mtr must also hold x-latches to 613 the brothers, if they exist. 614 @return TRUE on success */ 615 UNIV_INTERN 616 ibool 617 btr_compress( 618 /*=========*/ 619 btr_cur_t* cursor, /*!< in/out: cursor on the page to merge 620 or lift; the page must not be empty: 621 when deleting records, use btr_discard_page() 622 if the page would become empty */ 623 ibool adjust, /*!< in: TRUE if should adjust the 624 cursor position even if compression occurs */ 625 mtr_t* mtr) /*!< in/out: mini-transaction */ 626 MY_ATTRIBUTE((nonnull)); 627 /*************************************************************//** 628 Discards a page from a B-tree. This is used to remove the last record from 629 a B-tree page: the whole page must be removed at the same time. This cannot 630 be used for the root page, which is allowed to be empty. */ 631 UNIV_INTERN 632 void 633 btr_discard_page( 634 /*=============*/ 635 btr_cur_t* cursor, /*!< in: cursor on the page to discard: not on 636 the root page */ 637 mtr_t* mtr) /*!< in: mtr */ 638 MY_ATTRIBUTE((nonnull)); 639 #endif /* !UNIV_HOTBACKUP */ 640 /****************************************************************//** 641 Parses the redo log record for setting an index record as the predefined 642 minimum record. 643 @return end of log record or NULL */ 644 UNIV_INTERN 645 byte* 646 btr_parse_set_min_rec_mark( 647 /*=======================*/ 648 byte* ptr, /*!< in: buffer */ 649 byte* end_ptr,/*!< in: buffer end */ 650 ulint comp, /*!< in: nonzero=compact page format */ 651 page_t* page, /*!< in: page or NULL */ 652 mtr_t* mtr) /*!< in: mtr or NULL */ 653 MY_ATTRIBUTE((nonnull(1,2), warn_unused_result)); 654 /***********************************************************//** 655 Parses a redo log record of reorganizing a page. 656 @return end of log record or NULL */ 657 UNIV_INTERN 658 byte* 659 btr_parse_page_reorganize( 660 /*======================*/ 661 byte* ptr, /*!< in: buffer */ 662 byte* end_ptr,/*!< in: buffer end */ 663 dict_index_t* index, /*!< in: record descriptor */ 664 bool compressed,/*!< in: true if compressed page */ 665 buf_block_t* block, /*!< in: page to be reorganized, or NULL */ 666 mtr_t* mtr) /*!< in: mtr or NULL */ 667 MY_ATTRIBUTE((nonnull(1,2,3), warn_unused_result)); 668 #ifndef UNIV_HOTBACKUP 669 /**************************************************************//** 670 Gets the number of pages in a B-tree. 671 @return number of pages, or ULINT_UNDEFINED if the index is unavailable */ 672 UNIV_INTERN 673 ulint 674 btr_get_size( 675 /*=========*/ 676 dict_index_t* index, /*!< in: index */ 677 ulint flag, /*!< in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */ 678 mtr_t* mtr) /*!< in/out: mini-transaction where index 679 is s-latched */ 680 MY_ATTRIBUTE((nonnull, warn_unused_result)); 681 /**************************************************************//** 682 Allocates a new file page to be used in an index tree. NOTE: we assume 683 that the caller has made the reservation for free extents! 684 @retval NULL if no page could be allocated 685 @retval block, rw_lock_x_lock_count(&block->lock) == 1 if allocation succeeded 686 (init_mtr == mtr, or the page was not previously freed in mtr) 687 @retval block (not allocated or initialized) otherwise */ 688 UNIV_INTERN 689 buf_block_t* 690 btr_page_alloc( 691 /*===========*/ 692 dict_index_t* index, /*!< in: index tree */ 693 ulint hint_page_no, /*!< in: hint of a good page */ 694 byte file_direction, /*!< in: direction where a possible 695 page split is made */ 696 ulint level, /*!< in: level where the page is placed 697 in the tree */ 698 mtr_t* mtr, /*!< in/out: mini-transaction 699 for the allocation */ 700 mtr_t* init_mtr) /*!< in/out: mini-transaction 701 for x-latching and initializing 702 the page */ 703 MY_ATTRIBUTE((nonnull, warn_unused_result)); 704 /**************************************************************//** 705 Frees a file page used in an index tree. NOTE: cannot free field external 706 storage pages because the page must contain info on its level. */ 707 UNIV_INTERN 708 void 709 btr_page_free( 710 /*==========*/ 711 dict_index_t* index, /*!< in: index tree */ 712 buf_block_t* block, /*!< in: block to be freed, x-latched */ 713 mtr_t* mtr) /*!< in: mtr */ 714 MY_ATTRIBUTE((nonnull)); 715 /**************************************************************//** 716 Frees a file page used in an index tree. Can be used also to BLOB 717 external storage pages, because the page level 0 can be given as an 718 argument. */ 719 UNIV_INTERN 720 void 721 btr_page_free_low( 722 /*==============*/ 723 dict_index_t* index, /*!< in: index tree */ 724 buf_block_t* block, /*!< in: block to be freed, x-latched */ 725 ulint level, /*!< in: page level */ 726 mtr_t* mtr) /*!< in: mtr */ 727 MY_ATTRIBUTE((nonnull)); 728 #ifdef UNIV_BTR_PRINT 729 /*************************************************************//** 730 Prints size info of a B-tree. */ 731 UNIV_INTERN 732 void 733 btr_print_size( 734 /*===========*/ 735 dict_index_t* index) /*!< in: index tree */ 736 MY_ATTRIBUTE((nonnull)); 737 /**************************************************************//** 738 Prints directories and other info of all nodes in the index. */ 739 UNIV_INTERN 740 void 741 btr_print_index( 742 /*============*/ 743 dict_index_t* index, /*!< in: index */ 744 ulint width) /*!< in: print this many entries from start 745 and end */ 746 MY_ATTRIBUTE((nonnull)); 747 #endif /* UNIV_BTR_PRINT */ 748 /************************************************************//** 749 Checks the size and number of fields in a record based on the definition of 750 the index. 751 @return TRUE if ok */ 752 UNIV_INTERN 753 ibool 754 btr_index_rec_validate( 755 /*===================*/ 756 const rec_t* rec, /*!< in: index record */ 757 const dict_index_t* index, /*!< in: index */ 758 ibool dump_on_error) /*!< in: TRUE if the function 759 should print hex dump of record 760 and page on error */ 761 MY_ATTRIBUTE((nonnull, warn_unused_result)); 762 /**************************************************************//** 763 Checks the consistency of an index tree. 764 @return TRUE if ok */ 765 UNIV_INTERN 766 bool 767 btr_validate_index( 768 /*===============*/ 769 dict_index_t* index, /*!< in: index */ 770 const trx_t* trx) /*!< in: transaction or 0 */ 771 MY_ATTRIBUTE((nonnull(1), warn_unused_result)); 772 773 #define BTR_N_LEAF_PAGES 1 774 #define BTR_TOTAL_SIZE 2 775 #endif /* !UNIV_HOTBACKUP */ 776 777 #ifndef UNIV_NONINL 778 #include "btr0btr.ic" 779 #endif 780 781 #endif 782