MySQL 8.4.3
Source Code Documentation
|
The B-tree. More...
#include "btr0types.h"
#include "data0data.h"
#include "dict0dict.h"
#include "gis0type.h"
#include "mtr0mtr.h"
#include "page0cur.h"
#include "univ.i"
#include "btr0btr.ic"
Go to the source code of this file.
Classes | |
struct | BFT |
Does a breadth first traversal (BFT) of the B-tree, and invokes the callback for each of the B-tree nodes. More... | |
struct | BFT::Callback |
struct | BFT::Callback::Page_details |
Macros | |
#define | BTR_PAGE_MAX_REC_SIZE (UNIV_PAGE_SIZE / 2 - 200) |
Maximum record size which can be stored on a page, without using the special big record storage structure. More... | |
#define | btr_page_alloc(index, hint_page_no, file_direction, level, mtr, init_mtr) |
Typedefs | |
using | Page_range_t = std::pair< page_no_t, page_no_t > |
Enumerations | |
enum | btr_latch_mode : size_t { BTR_SEARCH_LEAF = RW_S_LATCH , BTR_MODIFY_LEAF = RW_X_LATCH , BTR_NO_LATCHES = RW_NO_LATCH , BTR_MODIFY_TREE = 33 , BTR_CONT_MODIFY_TREE = 34 , BTR_SEARCH_PREV = 35 , BTR_MODIFY_PREV = 36 , BTR_SEARCH_TREE = 37 , BTR_CONT_SEARCH_TREE = 38 } |
Latching modes for btr_cur_search_to_nth_level(). More... | |
Functions | |
constexpr ulint | BTR_LATCH_MODE_WITHOUT_FLAGS (ulint latch_mode) |
ulint | BTR_LATCH_MODE_WITHOUT_INTENTION (ulint latch_mode) |
void | btr_corruption_report (const buf_block_t *block, const dict_index_t *index) UNIV_COLD |
Report that an index page is corrupted. More... | |
void | btr_assert_not_corrupted (const buf_block_t *block, const dict_index_t *index) |
Assert that a B-tree page is not corrupted. More... | |
page_t * | btr_root_get (const dict_index_t *index, mtr_t *mtr) |
Gets the root node of a tree and sx-latches it for segment access. More... | |
dberr_t | btr_root_adjust_on_import (const dict_index_t *index) |
Checks and adjusts the root node of a tree during IMPORT TABLESPACE. More... | |
ulint | btr_height_get (dict_index_t *index, mtr_t *mtr) |
Gets the height of the B-tree (the level of the root, when the leaf level is assumed to be 0). More... | |
static buf_block_t * | btr_block_get_func (const page_id_t &page_id, const page_size_t &page_size, ulint mode, ut::Location location, const dict_index_t *index, mtr_t *mtr) |
Gets a buffer page and declares its latching order level. More... | |
static buf_block_t * | btr_block_get (const page_id_t &page_id, const page_size_t &page_size, ulint mode, ut::Location location, const dict_index_t *index, mtr_t *mtr) |
Gets a buffer page and declares its latching order level. More... | |
static space_index_t | btr_page_get_index_id (const page_t *page) |
Gets the index id field of a page. More... | |
static ulint | btr_page_get_level (const page_t *page) |
Gets the node level field in an index page. More... | |
static page_no_t | btr_page_get_next (const page_t *page, mtr_t *mtr) |
Gets the next index page number. More... | |
static page_no_t | btr_page_get_prev (const page_t *page, mtr_t *mtr) |
Gets the previous index page number. More... | |
static void | btr_leaf_page_release (buf_block_t *block, ulint latch_mode, mtr_t *mtr) |
Releases the latch on a leaf page and bufferunfixes it. More... | |
static page_no_t | btr_node_ptr_get_child_page_no (const rec_t *rec, const ulint *offsets) |
Gets the child node file address in a node pointer. More... | |
buf_block_t * | btr_node_ptr_get_child (const rec_t *node_ptr, dict_index_t *index, const ulint *offsets, mtr_t *mtr, rw_lock_type_t type=RW_SX_LATCH) |
Returns the child page of a node pointer and sx-latches it. More... | |
ulint | btr_create (ulint type, space_id_t space, space_index_t index_id, dict_index_t *index, mtr_t *mtr) |
Create the root node for a new index tree. More... | |
void | btr_free_if_exists (const page_id_t &page_id, const page_size_t &page_size, space_index_t index_id, mtr_t *mtr) |
Free a persistent index tree if it exists. More... | |
void | btr_free (const page_id_t &page_id, const page_size_t &page_size) |
Free an index tree in a temporary tablespace. More... | |
void | btr_truncate (const dict_index_t *index) |
Truncate an index tree. More... | |
void | btr_truncate_recover (const dict_index_t *index) |
Recovery function for btr_truncate. More... | |
rec_t * | btr_root_raise_and_insert (uint32_t flags, btr_cur_t *cursor, ulint **offsets, mem_heap_t **heap, const dtuple_t *tuple, mtr_t *mtr) |
Makes tree one level higher by splitting the root, and inserts the tuple. More... | |
bool | btr_page_reorganize_low (bool recovery, ulint z_level, page_cur_t *cursor, dict_index_t *index, mtr_t *mtr) |
Reorganizes an index page. More... | |
bool | btr_page_reorganize (page_cur_t *cursor, dict_index_t *index, mtr_t *mtr) |
Reorganizes an index page. More... | |
bool | btr_page_get_split_rec_to_left (btr_cur_t *cursor, rec_t **split_rec) |
Decides if the page should be split at the convergence point of inserts converging to left. More... | |
bool | btr_page_get_split_rec_to_right (btr_cur_t *cursor, rec_t **split_rec) |
Decides if the page should be split at the convergence point of inserts converging to right. More... | |
rec_t * | btr_page_split_and_insert (uint32_t flags, btr_cur_t *cursor, ulint **offsets, mem_heap_t **heap, const dtuple_t *tuple, mtr_t *mtr) |
Splits an index page to halves and inserts the tuple. More... | |
void | btr_insert_on_non_leaf_level (uint32_t flags, dict_index_t *index, ulint level, dtuple_t *tuple, ut::Location location, mtr_t *mtr) |
Inserts a data tuple to a tree on a non-leaf level. More... | |
void | btr_set_min_rec_mark (rec_t *rec, mtr_t *mtr) |
Sets a record as the predefined minimum record. More... | |
void | btr_unset_min_rec_mark (buf_block_t *block, rec_t *rec, mtr_t *mtr) |
Removes a record as the predefined minimum record. More... | |
void | btr_node_ptr_delete (dict_index_t *index, buf_block_t *block, mtr_t *mtr) |
Deletes on the upper level the node pointer to a page. More... | |
bool | btr_check_node_ptr (dict_index_t *index, buf_block_t *block, mtr_t *mtr) |
Asserts that the node pointer to a page is appropriate. More... | |
bool | btr_compress (btr_cur_t *cursor, bool adjust, mtr_t *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. More... | |
void | btr_discard_page (btr_cur_t *cursor, mtr_t *mtr) |
Discards a page from a B-tree. More... | |
const byte * | btr_parse_set_min_rec_mark (const byte *ptr, const byte *end_ptr, ulint comp, page_t *page, mtr_t *mtr) |
Parses the redo log record for setting an index record as the predefined minimum record. More... | |
const byte * | btr_parse_page_reorganize (const byte *ptr, const byte *end_ptr, dict_index_t *index, bool compressed, buf_block_t *block, mtr_t *mtr) |
Parses a redo log record of reorganizing a page. More... | |
ulint | btr_get_size (dict_index_t *index, ulint flag, mtr_t *mtr) |
Gets the number of pages in a B-tree. More... | |
buf_block_t * | btr_page_alloc_priv (dict_index_t *index, page_no_t hint_page_no, byte file_direction, ulint level, mtr_t *mtr, mtr_t *init_mtr, const ut::Location &loc) |
Allocates a new file page to be used in an index tree. More... | |
dberr_t | btr_extent_alloc (const dict_index_t *const index, bool is_leaf, Page_range_t &page_range, mtr_t *mtr) |
Allocates all pages of one extent to be used in an index tree. More... | |
void | btr_page_free (dict_index_t *index, buf_block_t *block, mtr_t *mtr) |
Frees a file page used in an index tree. More... | |
void | btr_page_create (buf_block_t *block, page_zip_des_t *page_zip, dict_index_t *index, ulint level, mtr_t *mtr) |
Creates a new index page (not the root, and also not used in page reorganization). More... | |
void | btr_page_free_low (dict_index_t *index, buf_block_t *block, ulint level, mtr_t *mtr) |
Frees a file page used in an index tree. More... | |
buf_block_t * | btr_root_block_get (const dict_index_t *index, ulint mode, mtr_t *mtr) |
Gets the root node of a tree and x- or s-latches it. More... | |
void | btr_print_size (dict_index_t *index) |
Prints size info of a B-tree. More... | |
void | btr_print_index (dict_index_t *index, ulint width) |
Prints directories and other info of all nodes in the index. More... | |
bool | btr_index_rec_validate (const rec_t *rec, const dict_index_t *index, bool dump_on_error) |
Checks the size and number of fields in a record based on the definition of the index. More... | |
bool | btr_validate_index (dict_index_t *index, const trx_t *trx, bool lockout) |
Checks the consistency of an index tree. More... | |
dberr_t | btr_sdi_create_index (space_id_t space_id, bool dict_locked) |
Creates SDI index and stores the root page numbers in page 1 & 2. More... | |
bool | btr_is_index_empty (const dict_index_t *index) |
Check if the given index is empty. More... | |
std::ostream & | operator<< (std::ostream &out, const BFT::Callback::Page_details &obj) |
std::ostream & | operator<< (std::ostream &out, const BFT::Callback &obj) |
Variables | |
constexpr uint32_t | BTR_MAX_LEVELS = 100 |
Maximum depth of a B-tree in InnoDB. More... | |
constexpr size_t | BTR_INSERT = 512 |
If this is ORed to btr_latch_mode, it means that the search tuple will be inserted to the index, at the searched position. More... | |
constexpr size_t | BTR_ESTIMATE = 1024 |
This flag ORed to btr_latch_mode says that we do the search in query optimization. More... | |
constexpr size_t | BTR_IGNORE_SEC_UNIQUE = 2048 |
This flag ORed to BTR_INSERT says that we can ignore possible UNIQUE definition on secondary indexes when we decide if we can use the insert buffer to speed up inserts. More... | |
constexpr size_t | BTR_DELETE_MARK = 4096 |
Try to delete mark the record at the searched position using the insert/delete buffer when the record is not in the buffer pool. More... | |
constexpr size_t | BTR_DELETE = 8192 |
Try to purge the record at the searched position using the insert/delete buffer when the record is not in the buffer pool. More... | |
constexpr size_t | BTR_ALREADY_S_LATCHED = 16384 |
In the case of BTR_SEARCH_LEAF or BTR_MODIFY_LEAF, the caller is already holding an S latch on the index tree. More... | |
constexpr size_t | BTR_LATCH_FOR_INSERT = 32768 |
In the case of BTR_MODIFY_TREE, the caller specifies the intention to insert record only. More... | |
constexpr size_t | BTR_LATCH_FOR_DELETE = 65536 |
In the case of BTR_MODIFY_TREE, the caller specifies the intention to delete record only. More... | |
constexpr size_t | BTR_RTREE_UNDO_INS = 131072 |
This flag is for undo insert of rtree. More... | |
constexpr size_t | BTR_MODIFY_EXTERNAL = 262144 |
In the case of BTR_MODIFY_LEAF, the caller intends to allocate or free the pages of externally stored fields. More... | |
constexpr size_t | BTR_RTREE_DELETE_MARK = 524288 |
Try to delete mark the record at the searched position when the record is in spatial index. More... | |
constexpr uint32_t | BTR_N_LEAF_PAGES = 1 |
constexpr uint32_t | BTR_TOTAL_SIZE = 2 |
constexpr uint32_t | BTR_MAX_NODE_LEVEL = 45 |
NOTE - Changing this from the original number of 50 to 45 as insert_debug.test was failing in ASAN build because of a stack overflow issue. More... | |
The B-tree.
Created 6/2/1994 Heikki Tuuri
#define btr_page_alloc | ( | index, | |
hint_page_no, | |||
file_direction, | |||
level, | |||
mtr, | |||
init_mtr | |||
) |
#define BTR_PAGE_MAX_REC_SIZE (UNIV_PAGE_SIZE / 2 - 200) |
Maximum record size which can be stored on a page, without using the special big record storage structure.
using Page_range_t = std::pair<page_no_t, page_no_t> |
enum btr_latch_mode : size_t |
Latching modes for btr_cur_search_to_nth_level().
|
inline |
Assert that a B-tree page is not corrupted.
block | buffer block containing a B-tree page |
index | the B-tree index |
|
inlinestatic |
Gets a buffer page and declares its latching order level.
page_id | Tablespace/page identifier | |
page_size | Page size | |
mode | Latch mode | |
[in] | location | Location from where this method is called. |
index | Index tree, may be NULL if not the insert buffer tree | |
mtr | Mini-transaction handle |
|
inlinestatic |
Gets a buffer page and declares its latching order level.
[in] | page_id | Page id |
[in] | page_size | Page size |
[in] | mode | Latch mode |
[in] | location | Location from where this method is called. |
[in] | index | Index tree, may be NULL if it is not an insert buffer tree |
[in,out] | mtr | Mini-transaction |
bool btr_check_node_ptr | ( | dict_index_t * | index, |
buf_block_t * | block, | ||
mtr_t * | mtr | ||
) |
Asserts that the node pointer to a page is appropriate.
[in] | index | index tree |
[in] | block | index page |
[in] | mtr | 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.
[in,out] | cursor | cursor on the page to merge or lift; the page must not be empty: when deleting records, use btr_discard_page() if the page would become empty |
[in] | adjust | true if should adjust the cursor position even if compression occurs. |
[in,out] | mtr | mini-transaction |
void btr_corruption_report | ( | const buf_block_t * | block, |
const dict_index_t * | index | ||
) |
Report that an index page is corrupted.
block | in: corrupted block |
index | in: index tree |
ulint btr_create | ( | ulint | type, |
space_id_t | space, | ||
space_index_t | index_id, | ||
dict_index_t * | index, | ||
mtr_t * | mtr | ||
) |
Create the root node for a new index tree.
[in] | type | Type of the index |
[in] | space | Space where created |
[in] | index_id | Index id |
[in] | index | Index tree |
[in,out] | mtr | Mini-transaction |
FIL_NULL | if did not succeed |
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. in: mtr
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.
cursor | in: cursor on the page to discard: not on the root page |
mtr | in: mtr |
dberr_t btr_extent_alloc | ( | const dict_index_t *const | index, |
bool | is_leaf, | ||
Page_range_t & | page_range, | ||
mtr_t * | mtr | ||
) |
Allocates all pages of one extent to be used in an index tree.
[in] | index | the index for which pages are allocated. |
[in] | is_leaf | true if leaf segment and false if non-leaf segment |
[out] | page_range | All pages within this pair of page numbers are allocated for this B-tree. The page_range.first is part of the range, while the page_range.second is not part of the range. |
[in] | mtr | mini transaction context for this operation. |
void btr_free | ( | const page_id_t & | page_id, |
const page_size_t & | page_size | ||
) |
Free an index tree in a temporary tablespace.
[in] | page_id | root page id |
[in] | page_size | page size |
void btr_free_if_exists | ( | const page_id_t & | page_id, |
const page_size_t & | page_size, | ||
space_index_t | index_id, | ||
mtr_t * | mtr | ||
) |
Free a persistent index tree if it exists.
[in] | page_id | Root page id |
[in] | page_size | Page size |
[in] | index_id | PAGE_INDEX_ID contents |
[in,out] | mtr | Mini-transaction |
ulint btr_get_size | ( | dict_index_t * | index, |
ulint | flag, | ||
mtr_t * | mtr | ||
) |
Gets the number of pages in a B-tree.
index | in: index |
flag | in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE |
mtr | in/out: mini-transaction where index is s-latched |
ulint btr_height_get | ( | dict_index_t * | index, |
mtr_t * | mtr | ||
) |
Gets the height of the B-tree (the level of the root, when the leaf level is assumed to be 0).
The caller must hold an S or X latch on the index.
The caller must hold an S or X latch on the index.
index | in: index tree |
mtr | in/out: mini-transaction |
bool btr_index_rec_validate | ( | const rec_t * | rec, |
const dict_index_t * | index, | ||
bool | dump_on_error | ||
) |
Checks the size and number of fields in a record based on the definition of the index.
rec | in: index record |
index | in: index |
dump_on_error | in: true if the function should print hex dump of record and page on error |
void btr_insert_on_non_leaf_level | ( | uint32_t | flags, |
dict_index_t * | index, | ||
ulint | level, | ||
dtuple_t * | tuple, | ||
ut::Location | location, | ||
mtr_t * | 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.
[in] | flags | undo logging and locking flags |
[in] | index | index |
[in] | level | level, must be > 0 |
[in] | tuple | the record to be inserted |
[in] | location | location where called |
[in] | mtr | mtr |
bool btr_is_index_empty | ( | const dict_index_t * | index | ) |
Check if the given index is empty.
An index is considered empty if it has only the root page with no user records, including del-marked records.
[in] | index | index |
|
inlinestatic |
Releases the latch on a leaf page and bufferunfixes it.
[in] | block | buffer block |
[in] | latch_mode | BTR_SEARCH_LEAF or BTR_MODIFY_LEAF |
[in] | mtr | mtr |
void btr_node_ptr_delete | ( | dict_index_t * | index, |
buf_block_t * | block, | ||
mtr_t * | mtr | ||
) |
Deletes on the upper level the node pointer to a page.
[in] | index | Index tree |
[in] | block | Page whose node pointer is deleted |
[in] | mtr | Mini-transaction |
buf_block_t * btr_node_ptr_get_child | ( | const rec_t * | node_ptr, |
dict_index_t * | index, | ||
const ulint * | offsets, | ||
mtr_t * | mtr, | ||
rw_lock_type_t | type = RW_SX_LATCH |
||
) |
Returns the child page of a node pointer and sx-latches it.
[in] | node_ptr | node pointer |
[in] | index | index |
[in] | offsets | array returned by rec_get_offsets() |
[in] | mtr | mtr |
[in] | type | latch type |
|
inlinestatic |
Gets the child node file address in a node pointer.
NOTE: the offsets array must contain all offsets for the record since we read the last field according to offsets and assume that it contains the child page number. In other words offsets must have been retrieved with rec_get_offsets(n_fields=ULINT_UNDEFINED).
[in] | rec | node Pointer record |
[in] | offsets | Array returned by rec_get_offsets() |
buf_block_t * btr_page_alloc_priv | ( | dict_index_t * | index, |
page_no_t | hint_page_no, | ||
byte | file_direction, | ||
ulint | level, | ||
mtr_t * | mtr, | ||
mtr_t * | init_mtr, | ||
const ut::Location & | loc | ||
) |
Allocates a new file page to be used in an index tree.
NOTE: we assume that the caller has made the reservation for free extents!
[in] | index | Index tree |
[in] | hint_page_no | Hint of a good page |
[in] | file_direction | Direction where a possible page split is made |
[in] | level | Level where the page is placed in the tree |
[in,out] | mtr | Mini-transaction for the allocation |
[in,out] | init_mtr | Mini-transaction for x-latching and initializing the page |
[in] | loc | debug only parameter providing caller source location. |
NULL | if no page could be allocated |
block,rw_lock_x_lock_count(&block->lock) | == 1 if allocation succeeded (init_mtr == mtr, or the page was not previously freed in mtr), returned block is not allocated nor initialized otherwise |
void btr_page_create | ( | buf_block_t * | block, |
page_zip_des_t * | page_zip, | ||
dict_index_t * | index, | ||
ulint | level, | ||
mtr_t * | mtr | ||
) |
Creates a new index page (not the root, and also not used in page reorganization).
block | in/out: page to be created |
page_zip | in/out: compressed page, or NULL |
index | in: index |
level | in: the B-tree level of the page |
mtr | in: mtr |
void btr_page_free | ( | dict_index_t * | index, |
buf_block_t * | block, | ||
mtr_t * | mtr | ||
) |
Frees a file page used in an index tree.
NOTE: cannot free field external storage pages because the page must contain info on its level. in: mtr
NOTE: cannot free field external storage pages because the page must contain info on its level.
index | in: index tree |
block | in: block to be freed, x-latched |
mtr | in: mtr |
void btr_page_free_low | ( | dict_index_t * | index, |
buf_block_t * | block, | ||
ulint | level, | ||
mtr_t * | mtr | ||
) |
Frees a file page used in an index tree.
Can be used also to BLOB external storage pages.
[in] | index | the index to which the page belongs |
[in] | block | block to be freed, x-latched |
[in] | level | page level (ULINT_UNDEFINED=BLOB) |
[in] | mtr | mini transaction context. |
|
inlinestatic |
Gets the index id field of a page.
Gets the node level field in an index page.
[in] | page | index page |
Gets the next index page number.
[in] | page | Index page. |
[in] | mtr | Mini-transaction handle. |
Gets the previous index page number.
[in] | page | Index page. |
[in] | mtr | Mini-transaction handle. |
Decides if the page should be split at the convergence point of inserts converging to left.
Decides if the page should be split at the convergence point of inserts converging to left.
cursor | in: cursor at which to insert |
split_rec | out: if split recommended, the first record on upper half page, or NULL if tuple to be inserted should be first |
Decides if the page should be split at the convergence point of inserts converging to right.
Decides if the page should be split at the convergence point of inserts converging to right.
cursor | in: cursor at which to insert |
split_rec | out: if split recommended, the first record on upper half page, or NULL if tuple to be inserted should be first |
bool btr_page_reorganize | ( | page_cur_t * | cursor, |
dict_index_t * | index, | ||
mtr_t * | mtr | ||
) |
Reorganizes an index page.
IMPORTANT: On success, the caller will have to update IBUF_BITMAP_FREE if this is a compressed leaf page in a secondary index. This has to be done either within the same mini-transaction, or by invoking ibuf_reset_free_bits() before mtr_commit(). On uncompressed pages, IBUF_BITMAP_FREE is unaffected by reorganization.
[in,out] | cursor | Page cursor |
[in] | index | The index tree of the page |
[in,out] | mtr | Mini-transaction |
true | if the operation was successful |
false | if it is a compressed page, and recompression failed |
bool btr_page_reorganize_low | ( | bool | recovery, |
ulint | z_level, | ||
page_cur_t * | cursor, | ||
dict_index_t * | index, | ||
mtr_t * | mtr | ||
) |
Reorganizes an index page.
IMPORTANT: On success, the caller will have to update IBUF_BITMAP_FREE if this is a compressed leaf page in a secondary index. This has to be done either within the same mini-transaction, or by invoking ibuf_reset_free_bits() before mtr_commit(). On uncompressed pages, IBUF_BITMAP_FREE is unaffected by reorganization.
[in] | recovery | True if called in recovery: locks should not be updated, i.e., there cannot exist locks on the page, and a hash index should not be dropped: it cannot exist. |
[in] | z_level | Compression level to be used if dealing with compressed page. |
[in,out] | cursor | Page cursor. |
[in] | index | The index tree of the page. |
[in,out] | mtr | Mini-transaction |
true | if the operation was successful |
false | if it is a compressed page, and re-compression failed |
rec_t * btr_page_split_and_insert | ( | uint32_t | flags, |
btr_cur_t * | cursor, | ||
ulint ** | offsets, | ||
mem_heap_t ** | heap, | ||
const dtuple_t * | tuple, | ||
mtr_t * | mtr | ||
) |
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 (2 pages) must be guaranteed to be available before this function is called.
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 (2 pages) must be guaranteed to be available before this function is called.
flags | in: undo logging and locking flags |
cursor | in: cursor at which to insert; when the function returns, the cursor is positioned on the predecessor of the inserted record |
offsets | out: offsets on inserted record |
heap | in/out: pointer to memory heap, or NULL |
tuple | in: tuple to insert |
mtr | in: mtr |
const byte * btr_parse_page_reorganize | ( | const byte * | ptr, |
const byte * | end_ptr, | ||
dict_index_t * | index, | ||
bool | compressed, | ||
buf_block_t * | block, | ||
mtr_t * | mtr | ||
) |
Parses a redo log record of reorganizing a page.
ptr | in: buffer |
end_ptr | in: buffer end |
index | in: record descriptor |
compressed | in: true if compressed page |
block | in: page to be reorganized, or NULL |
mtr | in: mtr or NULL |
const byte * btr_parse_set_min_rec_mark | ( | const byte * | ptr, |
const byte * | end_ptr, | ||
ulint | comp, | ||
page_t * | page, | ||
mtr_t * | mtr | ||
) |
Parses the redo log record for setting an index record as the predefined minimum record.
ptr | in: buffer |
end_ptr | in: buffer end |
comp | in: nonzero=compact page format |
page | in: page or NULL |
mtr | in: mtr or NULL |
void btr_print_index | ( | dict_index_t * | index, |
ulint | width | ||
) |
Prints directories and other info of all nodes in the index.
[in] | index | the index to be printed. |
[in] | width | number of entries to print from start and end. |
void btr_print_size | ( | dict_index_t * | index | ) |
Prints size info of a B-tree.
in: index tree
dberr_t btr_root_adjust_on_import | ( | const dict_index_t * | index | ) |
Checks and adjusts the root node of a tree during IMPORT TABLESPACE.
index | in: index tree |
buf_block_t * btr_root_block_get | ( | const dict_index_t * | index, |
ulint | mode, | ||
mtr_t * | mtr | ||
) |
Gets the root node of a tree and x- or s-latches it.
index | in: index tree |
mode | in: either RW_S_LATCH or RW_X_LATCH |
mtr | in: mtr |
page_t * btr_root_get | ( | const dict_index_t * | index, |
mtr_t * | mtr | ||
) |
Gets the root node of a tree and sx-latches it for segment access.
index | in: index tree |
mtr | in: mtr |
rec_t * btr_root_raise_and_insert | ( | uint32_t | flags, |
btr_cur_t * | cursor, | ||
ulint ** | offsets, | ||
mem_heap_t ** | heap, | ||
const dtuple_t * | tuple, | ||
mtr_t * | mtr | ||
) |
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.
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.
flags | in: undo logging and locking flags |
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 |
offsets | out: offsets on inserted record |
heap | in/out: pointer to memory heap, or NULL |
tuple | in: tuple to insert |
mtr | in: mtr |
dberr_t btr_sdi_create_index | ( | space_id_t | space_id, |
bool | dict_locked | ||
) |
Creates SDI index and stores the root page numbers in page 1 & 2.
[in] | space_id | tablespace id |
[in] | dict_locked | true if dict_sys mutex is acquired |
Sets a record as the predefined minimum record.
[in,out] | rec | Record |
[in] | mtr | Mini-transaction |
void btr_truncate | ( | const dict_index_t * | index | ) |
Truncate an index tree.
We just free all except the root. Currently, this function is only specific for clustered indexes and the only caller is DDTableBuffer which manages a table with only a clustered index. It is up to the caller to ensure atomicity and to ensure correct recovery by calling btr_truncate_recover().
[in] | index | clustered index |
void btr_truncate_recover | ( | const dict_index_t * | index | ) |
Recovery function for btr_truncate.
We will check if there is a crash during btr_truncate, if so, do recover it, if not, do nothing.
[in] | index | clustered index |
void btr_unset_min_rec_mark | ( | buf_block_t * | block, |
rec_t * | rec, | ||
mtr_t * | mtr | ||
) |
Removes a record as the predefined minimum record.
[in] | block | buffer block containing the record. |
[in] | rec | the record who info bits will be modified by clearing the REC_INFO_MIN_REC_FLAG bit. |
[in] | mtr | mini transaction context. |
bool btr_validate_index | ( | dict_index_t * | index, |
const trx_t * | trx, | ||
bool | lockout | ||
) |
Checks the consistency of an index tree.
index | in: index |
trx | in: transaction or NULL |
lockout | in: true if X-latch index is intended |
|
inline |
|
inline |
|
constexpr |
In the case of BTR_SEARCH_LEAF or BTR_MODIFY_LEAF, the caller is already holding an S latch on the index tree.
|
constexpr |
Try to purge the record at the searched position using the insert/delete buffer when the record is not in the buffer pool.
|
constexpr |
Try to delete mark the record at the searched position using the insert/delete buffer when the record is not in the buffer pool.
|
constexpr |
This flag ORed to btr_latch_mode says that we do the search in query optimization.
|
constexpr |
This flag ORed to BTR_INSERT says that we can ignore possible UNIQUE definition on secondary indexes when we decide if we can use the insert buffer to speed up inserts.
|
constexpr |
If this is ORed to btr_latch_mode, it means that the search tuple will be inserted to the index, at the searched position.
When the record is not in the buffer pool, try to use the insert buffer.
|
constexpr |
In the case of BTR_MODIFY_TREE, the caller specifies the intention to delete record only.
It is used to optimize block->lock range.
|
constexpr |
In the case of BTR_MODIFY_TREE, the caller specifies the intention to insert record only.
It is used to optimize block->lock range.
|
constexpr |
Maximum depth of a B-tree in InnoDB.
Note that this isn't a maximum as such; none of the tree operations avoid producing trees bigger than this. It is instead a "max depth that other code must work with", useful for e.g. fixed-size arrays that must store some information about each level in a tree. In other words: if a B-tree with bigger depth than this is encountered, it is not acceptable for it to lead to mysterious memory corruption, but it is acceptable for the program to die with a clear assert failure.
|
constexpr |
NOTE - Changing this from the original number of 50 to 45 as insert_debug.test was failing in ASAN build because of a stack overflow issue.
It was found that rtr_info_t was taking up a lot of stack space in the function btr_insert_on_non_leaf_level_func which is part of the recursive stack trace. Maximum B-tree page level (not really a hard limit). Used in debug assertions in btr_page_set_level and btr_page_get_level
|
constexpr |
In the case of BTR_MODIFY_LEAF, the caller intends to allocate or free the pages of externally stored fields.
|
constexpr |
|
constexpr |
Try to delete mark the record at the searched position when the record is in spatial index.
|
constexpr |
This flag is for undo insert of rtree.
For rtree, we need this flag to find proper rec to undo insert.
|
constexpr |