/****************************************************** The B-tree (c) 1994-1996 Innobase Oy Created 6/2/1994 Heikki Tuuri *******************************************************/ #ifndef btr0btr_h #define btr0btr_h #include "univ.i" #include "dict0dict.h" #include "data0data.h" #include "page0cur.h" #include "rem0rec.h" #include "mtr0mtr.h" #include "btr0types.h" /* Maximum record size which can be stored on a page, without using the special big record storage structure */ #define BTR_PAGE_MAX_REC_SIZE (UNIV_PAGE_SIZE / 2 - 200) /* Maximum key size in a B-tree: the records on non-leaf levels must be shorter than this */ #define BTR_PAGE_MAX_KEY_SIZE 1024 /* If data in page drops below this limit, we try to compress it. NOTE! The value has to be > 2 * BTR_MAX_KEY_SIZE */ #define BTR_COMPRESS_LIMIT (UNIV_PAGE_SIZE / 4 + 1); /* Latching modes for the search function (in btr0cur.*) */ #define BTR_SEARCH_LEAF RW_S_LATCH #define BTR_MODIFY_LEAF RW_X_LATCH #define BTR_NO_LATCHES RW_NO_LATCH #define BTR_MODIFY_TREE 33 #define BTR_CONT_MODIFY_TREE 34 #define BTR_SEARCH_PREV 35 #define BTR_MODIFY_PREV 36 /* If this is ORed to the latch mode, it means that the search tuple will be inserted to the index, at the searched position */ #define BTR_INSERT 512 /* This flag ORed to latch mode says that we do the search in query optimization */ #define BTR_ESTIMATE 1024 /****************************************************************** Gets a buffer page and declares its latching order level. */ UNIV_INLINE page_t* btr_page_get( /*=========*/ ulint space, /* in: space id */ ulint page_no, /* in: page number */ ulint mode, /* in: latch mode */ mtr_t* mtr); /* in: mtr */ /****************************************************************** Gets the index id field of a page. */ UNIV_INLINE dulint btr_page_get_index_id( /*==================*/ /* out: index id */ page_t* page); /* in: index page */ /************************************************************ Gets the node level field in an index page. */ UNIV_INLINE ulint btr_page_get_level_low( /*===================*/ /* out: level, leaf level == 0 */ page_t* page); /* in: index page */ /************************************************************ Gets the node level field in an index page. */ UNIV_INLINE ulint btr_page_get_level( /*===============*/ /* out: level, leaf level == 0 */ page_t* page, /* in: index page */ mtr_t* mtr); /* in: mini-transaction handle */ /************************************************************ Gets the next index page number. */ UNIV_INLINE ulint btr_page_get_next( /*==============*/ /* out: next page number */ page_t* page, /* in: index page */ mtr_t* mtr); /* in: mini-transaction handle */ /************************************************************ Gets the previous index page number. */ UNIV_INLINE ulint btr_page_get_prev( /*==============*/ /* out: prev page number */ page_t* page, /* in: index page */ mtr_t* mtr); /* in: mini-transaction handle */ /***************************************************************** Gets pointer to the previous user record in the tree. It is assumed that the caller has appropriate latches on the page and its neighbor. */ rec_t* btr_get_prev_user_rec( /*==================*/ /* out: previous user record, NULL if there is none */ rec_t* rec, /* in: record on leaf level */ mtr_t* mtr); /* in: mtr holding a latch on the page, and if needed, also to the previous page */ /***************************************************************** Gets pointer to the next user record in the tree. It is assumed that the caller has appropriate latches on the page and its neighbor. */ rec_t* btr_get_next_user_rec( /*==================*/ /* out: next user record, NULL if there is none */ rec_t* rec, /* in: record on leaf level */ mtr_t* mtr); /* in: mtr holding a latch on the page, and if needed, also to the next page */ /****************************************************************** Releases the latch on a leaf page and bufferunfixes it. */ UNIV_INLINE void btr_leaf_page_release( /*==================*/ page_t* page, /* in: page */ ulint latch_mode, /* in: BTR_SEARCH_LEAF or BTR_MODIFY_LEAF */ mtr_t* mtr); /* in: mtr */ /****************************************************************** Gets the child node file address in a node pointer. */ UNIV_INLINE ulint btr_node_ptr_get_child_page_no( /*===========================*/ /* out: child node address */ rec_t* rec); /* in: node pointer record */ /**************************************************************** Creates the root node for a new index tree. */ ulint btr_create( /*=======*/ /* out: page number of the created root, FIL_NULL if did not succeed */ ulint type, /* in: type of the index */ ulint space, /* in: space where created */ dulint index_id,/* in: index id */ mtr_t* mtr); /* in: mini-transaction handle */ /**************************************************************** Frees a B-tree except the root page, which MUST be freed after this by calling btr_free_root. */ void btr_free_but_not_root( /*==================*/ ulint space, /* in: space where created */ ulint root_page_no); /* in: root page number */ /**************************************************************** Frees the B-tree root page. Other tree MUST already have been freed. */ void btr_free_root( /*==========*/ ulint space, /* in: space where created */ ulint root_page_no, /* in: root page number */ mtr_t* mtr); /* in: a mini-transaction which has already been started */ /***************************************************************** Makes tree one level higher by splitting the root, and inserts the tuple. It is assumed that mtr contains an x-latch on the tree. NOTE that the operation of this function must always succeed, we cannot reverse it: therefore enough free disk space must be guaranteed to be available before this function is called. */ rec_t* btr_root_raise_and_insert( /*======================*/ /* out: inserted record */ btr_cur_t* cursor, /* in: cursor at which to insert: must be on the root page; when the function returns, the cursor is positioned on the predecessor of the inserted record */ dtuple_t* tuple, /* in: tuple to insert */ mtr_t* mtr); /* in: mtr */ /***************************************************************** Reorganizes an index page. */ void btr_page_reorganize( /*================*/ page_t* page, /* in: page to be reorganized */ mtr_t* mtr); /* in: mtr */ /***************************************************************** Reorganizes an index page. */ void btr_page_reorganize_low( /*====================*/ ibool low, /* in: TRUE if locks should not be updated, i.e., there cannot exist locks on the page */ page_t* page, /* in: page to be reorganized */ mtr_t* mtr); /* in: mtr */ /***************************************************************** Decides if the page should be split at the convergence point of inserts converging to left. */ ibool btr_page_get_split_rec_to_left( /*===========================*/ /* out: TRUE if split recommended */ btr_cur_t* cursor, /* in: cursor at which to insert */ rec_t** split_rec);/* out: if split recommended, the first record on upper half page, or NULL if tuple should be first */ /***************************************************************** Decides if the page should be split at the convergence point of inserts converging to right. */ ibool btr_page_get_split_rec_to_right( /*============================*/ /* out: TRUE if split recommended */ btr_cur_t* cursor, /* in: cursor at which to insert */ rec_t** split_rec);/* out: if split recommended, the first record on upper half page, or NULL if tuple should be first */ /***************************************************************** Splits an index page to halves and inserts the tuple. It is assumed that mtr holds an x-latch to the index tree. NOTE: the tree x-latch is released within this function! NOTE that the operation of this function must always succeed, we cannot reverse it: therefore enough free disk space must be guaranteed to be available before this function is called. */ rec_t* btr_page_split_and_insert( /*======================*/ /* out: inserted record; NOTE: the tree x-latch is released! NOTE: 2 free disk pages must be available! */ btr_cur_t* cursor, /* in: cursor at which to insert; when the function returns, the cursor is positioned on the predecessor of the inserted record */ dtuple_t* tuple, /* in: tuple to insert */ mtr_t* mtr); /* in: mtr */ /*********************************************************** Inserts a data tuple to a tree on a non-leaf level. It is assumed that mtr holds an x-latch on the tree. */ void btr_insert_on_non_leaf_level( /*=========================*/ dict_tree_t* tree, /* in: tree */ ulint level, /* in: level, must be > 0 */ dtuple_t* tuple, /* in: the record to be inserted */ mtr_t* mtr); /* in: mtr */ /******************************************************************** Sets a record as the predefined minimum record. */ void btr_set_min_rec_mark( /*=================*/ rec_t* rec, /* in: record */ mtr_t* mtr); /* in: mtr */ /***************************************************************** Deletes on the upper level the node pointer to a page. */ void btr_node_ptr_delete( /*================*/ dict_tree_t* tree, /* in: index tree */ page_t* page, /* in: page whose node pointer is deleted */ mtr_t* mtr); /* in: mtr */ /**************************************************************** Checks that the node pointer to a page is appropriate. */ ibool btr_check_node_ptr( /*===============*/ /* out: TRUE */ dict_tree_t* tree, /* in: index tree */ page_t* page, /* in: index page */ mtr_t* mtr); /* in: mtr */ /***************************************************************** Tries to merge the page first to the left immediate brother if such a brother exists, and the node pointers to the current page and to the brother reside on the same page. If the left brother does not satisfy these conditions, looks at the right brother. If the page is the only one on that level lifts the records of the page to the father page, thus reducing the tree height. It is assumed that mtr holds an x-latch on the tree and on the page. If cursor is on the leaf level, mtr must also hold x-latches to the brothers, if they exist. NOTE: it is assumed that the caller has reserved enough free extents so that the compression will always succeed if done! */ void btr_compress( /*=========*/ btr_cur_t* cursor, /* in: cursor on the page to merge or lift; the page must not be empty: in record delete use btr_discard_page if the page would become empty */ mtr_t* mtr); /* in: mtr */ /***************************************************************** Discards a page from a B-tree. This is used to remove the last record from a B-tree page: the whole page must be removed at the same time. This cannot be used for the root page, which is allowed to be empty. */ void btr_discard_page( /*=============*/ btr_cur_t* cursor, /* in: cursor on the page to discard: not on the root page */ mtr_t* mtr); /* in: mtr */ /************************************************************************ Declares the latching order level for the page latch in the debug version. */ UNIV_INLINE void btr_declare_page_latch( /*===================*/ page_t* page, /* in: page */ ibool leaf); /* in: TRUE if a leaf */ /******************************************************************** Parses the redo log record for setting an index record as the predefined minimum record. */ byte* btr_parse_set_min_rec_mark( /*=======================*/ /* out: end of log record or NULL */ byte* ptr, /* in: buffer */ byte* end_ptr,/* in: buffer end */ page_t* page, /* in: page or NULL */ mtr_t* mtr); /* in: mtr or NULL */ /*************************************************************** Parses a redo log record of reorganizing a page. */ byte* btr_parse_page_reorganize( /*======================*/ /* out: end of log record or NULL */ byte* ptr, /* in: buffer */ byte* end_ptr,/* in: buffer end */ page_t* page, /* in: page or NULL */ mtr_t* mtr); /* in: mtr or NULL */ /****************************************************************** Gets the number of pages in a B-tree. */ ulint btr_get_size( /*=========*/ /* out: number of pages */ dict_index_t* index, /* in: index */ ulint flag); /* in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */ /***************************************************************** Prints size info of a B-tree. */ void btr_print_size( /*===========*/ dict_tree_t* tree); /* in: index tree */ /****************************************************************** Prints directories and other info of all nodes in the tree. */ void btr_print_tree( /*===========*/ dict_tree_t* tree, /* in: tree */ ulint width); /* in: print this many entries from start and end */ /****************************************************************** Checks the consistency of an index tree. */ ibool btr_validate_tree( /*==============*/ /* out: TRUE if ok */ dict_tree_t* tree); /* in: tree */ #define BTR_N_LEAF_PAGES 1 #define BTR_TOTAL_SIZE 2 #ifndef UNIV_NONINL #include "btr0btr.ic" #endif #endif