MySQL 9.1.0
Source Code Documentation
btr0btr.h File Reference

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_tbtr_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_tbtr_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_tbtr_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_tbtr_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_tbtr_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_tbtr_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 bytebtr_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 bytebtr_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_tbtr_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_tbtr_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...
 

Detailed Description

The B-tree.

Created 6/2/1994 Heikki Tuuri

Macro Definition Documentation

◆ btr_page_alloc

#define btr_page_alloc (   index,
  hint_page_no,
  file_direction,
  level,
  mtr,
  init_mtr 
)
Value:
btr_page_alloc_priv(index, hint_page_no, file_direction, level, mtr, \
init_mtr, UT_LOCATION_HERE)
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.
Definition: btr0btr.cc:470
#define UT_LOCATION_HERE
Definition: ut0core.h:73

◆ BTR_PAGE_MAX_REC_SIZE

#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.

Typedef Documentation

◆ Page_range_t

using Page_range_t = std::pair<page_no_t, page_no_t>

Enumeration Type Documentation

◆ btr_latch_mode

enum btr_latch_mode : size_t

Latching modes for btr_cur_search_to_nth_level().

Enumerator
BTR_SEARCH_LEAF 

Search a record on a leaf page and S-latch it.

BTR_MODIFY_LEAF 

(Prepare to) modify a record on a leaf page and X-latch it.

BTR_NO_LATCHES 

Obtain no latches.

BTR_MODIFY_TREE 

Start modifying the entire B-tree.

BTR_CONT_MODIFY_TREE 

Continue modifying the entire B-tree.

BTR_SEARCH_PREV 

Search the previous record.

BTR_MODIFY_PREV 

Modify the previous record.

BTR_SEARCH_TREE 

Start searching the entire B-tree.

BTR_CONT_SEARCH_TREE 

Continue searching the entire B-tree.

Function Documentation

◆ btr_assert_not_corrupted()

void btr_assert_not_corrupted ( const buf_block_t block,
const dict_index_t index 
)
inline

Assert that a B-tree page is not corrupted.

Parameters
blockbuffer block containing a B-tree page
indexthe B-tree index

◆ btr_block_get()

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 
)
inlinestatic

Gets a buffer page and declares its latching order level.

Parameters
page_idTablespace/page identifier
page_sizePage size
modeLatch mode
[in]locationLocation from where this method is called.
indexIndex tree, may be NULL if not the insert buffer tree
mtrMini-transaction handle
Returns
the block descriptor

◆ btr_block_get_func()

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 
)
inlinestatic

Gets a buffer page and declares its latching order level.

Parameters
[in]page_idPage id
[in]page_sizePage size
[in]modeLatch mode
[in]locationLocation from where this method is called.
[in]indexIndex tree, may be NULL if it is not an insert buffer tree
[in,out]mtrMini-transaction
Returns
block

◆ btr_check_node_ptr()

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.

Parameters
[in]indexindex tree
[in]blockindex page
[in]mtrmtr
Returns
true

◆ btr_compress()

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.

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.

Parameters
[in,out]cursorcursor 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]adjusttrue if should adjust the cursor position even if compression occurs.
[in,out]mtrmini-transaction
Returns
true on success

◆ btr_corruption_report()

void btr_corruption_report ( const buf_block_t block,
const dict_index_t index 
)

Report that an index page is corrupted.

Parameters
blockin: corrupted block
indexin: index tree

◆ btr_create()

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.

Parameters
[in]typeType of the index
[in]spaceSpace where created
[in]index_idIndex id
[in]indexIndex tree
[in,out]mtrMini-transaction
Returns
page number of the created root
Return values
FIL_NULLif did not succeed

◆ btr_discard_page()

void btr_discard_page ( btr_cur_t cursor,
mtr_t 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. 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.

Parameters
cursorin: cursor on the page to discard: not on the root page
mtrin: mtr

◆ btr_extent_alloc()

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.

Parameters
[in]indexthe index for which pages are allocated.
[in]is_leaftrue if leaf segment and false if non-leaf segment
[out]page_rangeAll 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]mtrmini transaction context for this operation.
Returns
DB_SUCCESS on success, error code on failure.

◆ btr_free()

void btr_free ( const page_id_t page_id,
const page_size_t page_size 
)

Free an index tree in a temporary tablespace.

Parameters
[in]page_idroot page id
[in]page_sizepage size

◆ btr_free_if_exists()

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.

Parameters
[in]page_idRoot page id
[in]page_sizePage size
[in]index_idPAGE_INDEX_ID contents
[in,out]mtrMini-transaction

◆ btr_get_size()

ulint btr_get_size ( dict_index_t index,
ulint  flag,
mtr_t mtr 
)

Gets the number of pages in a B-tree.

Returns
number of pages, or ULINT_UNDEFINED if the index is unavailable in/out: mini-transaction where index is s-latched
number of pages, or ULINT_UNDEFINED if the index is unavailable
Parameters
indexin: index
flagin: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE
mtrin/out: mini-transaction where index is s-latched

◆ btr_height_get()

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.

Returns
tree height (level of the root) in/out: mini-transaction

The caller must hold an S or X latch on the index.

Returns
tree height (level of the root)
Parameters
indexin: index tree
mtrin/out: mini-transaction

◆ btr_index_rec_validate()

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.

Returns
true if ok in: true if the function should print hex dump of record and page on error
true if ok
Parameters
recin: index record
indexin: index
dump_on_errorin: true if the function should print hex dump of record and page on error

◆ btr_insert_on_non_leaf_level()

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.

Parameters
[in]flagsundo logging and locking flags
[in]indexindex
[in]levellevel, must be > 0
[in]tuplethe record to be inserted
[in]locationlocation where called
[in]mtrmtr

◆ btr_is_index_empty()

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.

Parameters
[in]indexindex
Returns
true if index is empty, false otherwise.

◆ BTR_LATCH_MODE_WITHOUT_FLAGS()

constexpr ulint BTR_LATCH_MODE_WITHOUT_FLAGS ( ulint  latch_mode)
constexpr

◆ BTR_LATCH_MODE_WITHOUT_INTENTION()

ulint BTR_LATCH_MODE_WITHOUT_INTENTION ( ulint  latch_mode)
inline

◆ btr_leaf_page_release()

static void btr_leaf_page_release ( buf_block_t block,
ulint  latch_mode,
mtr_t mtr 
)
inlinestatic

Releases the latch on a leaf page and bufferunfixes it.

Parameters
[in]blockbuffer block
[in]latch_modeBTR_SEARCH_LEAF or BTR_MODIFY_LEAF
[in]mtrmtr

◆ btr_node_ptr_delete()

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.

Parameters
[in]indexIndex tree
[in]blockPage whose node pointer is deleted
[in]mtrMini-transaction

◆ btr_node_ptr_get_child()

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.

Parameters
[in]node_ptrnode pointer
[in]indexindex
[in]offsetsarray returned by rec_get_offsets()
[in]mtrmtr
[in]typelatch type
Returns
child page, latched as per the type

◆ btr_node_ptr_get_child_page_no()

static page_no_t btr_node_ptr_get_child_page_no ( const rec_t rec,
const ulint offsets 
)
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).

Parameters
[in]recnode Pointer record
[in]offsetsArray returned by rec_get_offsets()
Returns
child node address

◆ btr_page_alloc_priv()

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!

Parameters
[in]indexIndex tree
[in]hint_page_noHint of a good page
[in]file_directionDirection where a possible page split is made
[in]levelLevel where the page is placed in the tree
[in,out]mtrMini-transaction for the allocation
[in,out]init_mtrMini-transaction for x-latching and initializing the page
[in]locdebug only parameter providing caller source location.
Return values
NULLif 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

◆ btr_page_create()

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).

See also
btr_page_empty(). in: mtr
btr_page_empty().
Parameters
blockin/out: page to be created
page_zipin/out: compressed page, or NULL
indexin: index
levelin: the B-tree level of the page
mtrin: mtr

◆ btr_page_free()

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.

Parameters
indexin: index tree
blockin: block to be freed, x-latched
mtrin: mtr

◆ btr_page_free_low()

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.

Parameters
[in]indexthe index to which the page belongs
[in]blockblock to be freed, x-latched
[in]levelpage level (ULINT_UNDEFINED=BLOB)
[in]mtrmini transaction context.

◆ btr_page_get_index_id()

static space_index_t btr_page_get_index_id ( const page_t page)
inlinestatic

Gets the index id field of a page.

Returns
index id in: index page

◆ btr_page_get_level()

static ulint btr_page_get_level ( const page_t page)
inlinestatic

Gets the node level field in an index page.

Parameters
[in]pageindex page
Returns
level, leaf level == 0

◆ btr_page_get_next()

static page_no_t btr_page_get_next ( const page_t page,
mtr_t mtr 
)
inlinestatic

Gets the next index page number.

Parameters
[in]pageIndex page.
[in]mtrMini-transaction handle.
Returns
next page number

◆ btr_page_get_prev()

static page_no_t btr_page_get_prev ( const page_t page,
mtr_t mtr 
)
inlinestatic

Gets the previous index page number.

Parameters
[in]pageIndex page.
[in]mtrMini-transaction handle.
Returns
prev page number

◆ btr_page_get_split_rec_to_left()

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.

Returns
true if split recommended 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 left.

Returns
true if split recommended
Parameters
cursorin: cursor at which to insert
split_recout: if split recommended, the first record on upper half page, or NULL if tuple to be inserted should be first

◆ btr_page_get_split_rec_to_right()

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.

Returns
true if split recommended 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.

Returns
true if split recommended
Parameters
cursorin: cursor at which to insert
split_recout: if split recommended, the first record on upper half page, or NULL if tuple to be inserted should be first

◆ btr_page_reorganize()

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.

Parameters
[in,out]cursorPage cursor
[in]indexThe index tree of the page
[in,out]mtrMini-transaction
Return values
trueif the operation was successful
falseif it is a compressed page, and recompression failed

◆ btr_page_reorganize_low()

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.

Parameters
[in]recoveryTrue 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_levelCompression level to be used if dealing with compressed page.
[in,out]cursorPage cursor.
[in]indexThe index tree of the page.
[in,out]mtrMini-transaction
Return values
trueif the operation was successful
falseif it is a compressed page, and re-compression failed

◆ btr_page_split_and_insert()

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.

Returns
inserted record in: mtr

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.

Returns
inserted record
Parameters
flagsin: undo logging and locking flags
cursorin: cursor at which to insert; when the function returns, the cursor is positioned on the predecessor of the inserted record
offsetsout: offsets on inserted record
heapin/out: pointer to memory heap, or NULL
tuplein: tuple to insert
mtrin: mtr

◆ btr_parse_page_reorganize()

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.

Returns
end of log record or NULL in: mtr or NULL
end of log record or NULL
Parameters
ptrin: buffer
end_ptrin: buffer end
indexin: record descriptor
compressedin: true if compressed page
blockin: page to be reorganized, or NULL
mtrin: mtr or NULL

◆ btr_parse_set_min_rec_mark()

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.

Returns
end of log record or NULL in: mtr or NULL
end of log record or NULL
Parameters
ptrin: buffer
end_ptrin: buffer end
compin: nonzero=compact page format
pagein: page or NULL
mtrin: mtr or NULL

◆ btr_print_index()

void btr_print_index ( dict_index_t index,
ulint  width 
)

Prints directories and other info of all nodes in the index.

Parameters
[in]indexthe index to be printed.
[in]widthnumber of entries to print from start and end.

◆ btr_print_size()

void btr_print_size ( dict_index_t index)

Prints size info of a B-tree.

in: index tree

◆ btr_root_adjust_on_import()

dberr_t btr_root_adjust_on_import ( const dict_index_t index)

Checks and adjusts the root node of a tree during IMPORT TABLESPACE.

Returns
error code, or DB_SUCCESS in: index tree
error code, or DB_SUCCESS
Parameters
indexin: index tree

◆ btr_root_block_get()

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.

Returns
root page, x- or s-latched in: mtr
root page, x- or s-latched
Parameters
indexin: index tree
modein: either RW_S_LATCH or RW_X_LATCH
mtrin: mtr

◆ btr_root_get()

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.

Returns
root page, sx-latched in: mtr
root page, sx-latched
Parameters
indexin: index tree
mtrin: mtr

◆ btr_root_raise_and_insert()

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.

Returns
inserted record in: mtr

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.

Returns
inserted record
Parameters
flagsin: undo logging and locking flags
cursorin: 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
offsetsout: offsets on inserted record
heapin/out: pointer to memory heap, or NULL
tuplein: tuple to insert
mtrin: mtr

◆ btr_sdi_create_index()

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.

Parameters
[in]space_idtablespace id
[in]dict_lockedtrue if dict_sys mutex is acquired
Returns
DB_SUCCESS on success, else DB_ERROR on failure

◆ btr_set_min_rec_mark()

void btr_set_min_rec_mark ( rec_t rec,
mtr_t mtr 
)

Sets a record as the predefined minimum record.

Parameters
[in,out]recRecord
[in]mtrMini-transaction

◆ btr_truncate()

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().

Parameters
[in]indexclustered index

◆ btr_truncate_recover()

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.

Parameters
[in]indexclustered index

◆ btr_unset_min_rec_mark()

void btr_unset_min_rec_mark ( buf_block_t block,
rec_t rec,
mtr_t mtr 
)

Removes a record as the predefined minimum record.

Parameters
[in]blockbuffer block containing the record.
[in]recthe record who info bits will be modified by clearing the REC_INFO_MIN_REC_FLAG bit.
[in]mtrmini transaction context.

◆ btr_validate_index()

bool btr_validate_index ( dict_index_t index,
const trx_t trx,
bool  lockout 
)

Checks the consistency of an index tree.

Returns
true if ok in: true if X-latch index is intended
true if ok
Parameters
indexin: index
trxin: transaction or NULL
lockoutin: true if X-latch index is intended

◆ operator<<() [1/2]

std::ostream & operator<< ( std::ostream &  out,
const BFT::Callback obj 
)
inline

◆ operator<<() [2/2]

std::ostream & operator<< ( std::ostream &  out,
const BFT::Callback::Page_details obj 
)
inline

Variable Documentation

◆ BTR_ALREADY_S_LATCHED

constexpr size_t BTR_ALREADY_S_LATCHED = 16384
constexpr

In the case of BTR_SEARCH_LEAF or BTR_MODIFY_LEAF, the caller is already holding an S latch on the index tree.

◆ BTR_DELETE

constexpr size_t BTR_DELETE = 8192
constexpr

Try to purge the record at the searched position using the insert/delete buffer when the record is not in the buffer pool.

◆ BTR_DELETE_MARK

constexpr size_t BTR_DELETE_MARK = 4096
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.

◆ BTR_ESTIMATE

constexpr size_t BTR_ESTIMATE = 1024
constexpr

This flag ORed to btr_latch_mode says that we do the search in query optimization.

◆ BTR_IGNORE_SEC_UNIQUE

constexpr size_t BTR_IGNORE_SEC_UNIQUE = 2048
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.

◆ BTR_INSERT

constexpr size_t BTR_INSERT = 512
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.

◆ BTR_LATCH_FOR_DELETE

constexpr size_t BTR_LATCH_FOR_DELETE = 65536
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.

◆ BTR_LATCH_FOR_INSERT

constexpr size_t BTR_LATCH_FOR_INSERT = 32768
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.

◆ BTR_MAX_LEVELS

constexpr uint32_t BTR_MAX_LEVELS = 100
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.

◆ BTR_MAX_NODE_LEVEL

constexpr uint32_t BTR_MAX_NODE_LEVEL = 45
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

◆ BTR_MODIFY_EXTERNAL

constexpr size_t BTR_MODIFY_EXTERNAL = 262144
constexpr

In the case of BTR_MODIFY_LEAF, the caller intends to allocate or free the pages of externally stored fields.

◆ BTR_N_LEAF_PAGES

constexpr uint32_t BTR_N_LEAF_PAGES = 1
constexpr

◆ BTR_RTREE_DELETE_MARK

constexpr size_t BTR_RTREE_DELETE_MARK = 524288
constexpr

Try to delete mark the record at the searched position when the record is in spatial index.

◆ BTR_RTREE_UNDO_INS

constexpr size_t BTR_RTREE_UNDO_INS = 131072
constexpr

This flag is for undo insert of rtree.

For rtree, we need this flag to find proper rec to undo insert.

◆ BTR_TOTAL_SIZE

constexpr uint32_t BTR_TOTAL_SIZE = 2
constexpr