MySQL  8.0.21
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.

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_MAX_LEVELS   100
 Maximum depth of a B-tree in InnoDB. More...
 
#define BTR_LATCH_MODE_WITHOUT_FLAGS(latch_mode)
 
#define BTR_LATCH_MODE_WITHOUT_INTENTION(latch_mode)
 
#define btr_assert_not_corrupted(block, index)
 Assert that a B-tree page is not corrupted. More...
 
#define btr_block_get(page_id, page_size, mode, index, mtr)   btr_block_get_func(page_id, page_size, mode, __FILE__, __LINE__, index, mtr)
 Gets a buffer page and declares its latching order level. More...
 
#define btr_page_get(page_id, page_size, mode, index, mtr)   buf_block_get_frame(btr_block_get(page_id, page_size, mode, index, mtr))
 Gets a buffer page and declares its latching order level. More...
 
#define btr_page_get_level(page, mtr)   btr_page_get_level_low(page)
 
#define btr_insert_on_non_leaf_level(f, i, l, t, m)   btr_insert_on_non_leaf_level_func(f, i, l, t, __FILE__, __LINE__, m)
 
#define BTR_N_LEAF_PAGES   1
 
#define BTR_TOTAL_SIZE   2
 

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

void btr_corruption_report (const buf_block_t *block, const dict_index_t *index) UNIV_COLD
 Report that an index page is 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...
 
UNIV_INLINE buf_block_tbtr_block_get_func (const page_id_t &page_id, const page_size_t &page_size, ulint mode, const char *file, ulint line, const dict_index_t *index, mtr_t *mtr)
 Gets a buffer page and declares its latching order level. More...
 
UNIV_INLINE space_index_t btr_page_get_index_id (const page_t *page)
 Gets the index id field of a page. More...
 
UNIV_INLINE ulint btr_page_get_level_low (const page_t *page)
 Gets the node level field in an index page. More...
 
UNIV_INLINE page_no_t btr_page_get_next (const page_t *page, mtr_t *mtr)
 Gets the next index page number. More...
 
UNIV_INLINE page_no_t btr_page_get_prev (const page_t *page, mtr_t *mtr)
 Gets the previous index page number. More...
 
UNIV_INLINE 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...
 
UNIV_INLINE 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, const page_size_t &page_size, 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...
 
ibool 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...
 
ibool 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_func (uint32_t flags, dict_index_t *index, ulint level, dtuple_t *tuple, const char *file, ulint line, 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_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...
 
ibool btr_check_node_ptr (dict_index_t *index, buf_block_t *block, mtr_t *mtr)
 Checks that the node pointer to a page is appropriate. More...
 
ibool btr_compress (btr_cur_t *cursor, ibool 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...
 
bytebtr_parse_set_min_rec_mark (byte *ptr, 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...
 
bytebtr_parse_page_reorganize (byte *ptr, 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 (dict_index_t *index, page_no_t hint_page_no, byte file_direction, ulint level, mtr_t *mtr, mtr_t *init_mtr)
 Allocates a new file page 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...
 
ibool btr_index_rec_validate (const rec_t *rec, const dict_index_t *index, ibool 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...
 

Variables

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

Detailed Description

The B-tree.

Created 6/2/1994 Heikki Tuuri

Macro Definition Documentation

◆ btr_assert_not_corrupted

#define btr_assert_not_corrupted (   block,
  index 
)
Value:
if ((ibool) !!page_is_comp(buf_block_get_frame(block)) != \
dict_table_is_comp((index)->table)) { \
btr_corruption_report(block, index); \
ut_error; \
}
UNIV_INLINE ulint page_is_comp(const page_t *page)
Determine whether the page is in new-style compact format.
UNIV_INLINE ibool dict_table_is_comp(const dict_table_t *table)
Check whether the table uses the compact page format.
UNIV_INLINE buf_frame_t * buf_block_get_frame(const buf_block_t *block)
Gets a pointer to the memory frame of a block.

Assert that a B-tree page is not corrupted.

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

◆ btr_block_get

#define btr_block_get (   page_id,
  page_size,
  mode,
  index,
  mtr 
)    btr_block_get_func(page_id, page_size, mode, __FILE__, __LINE__, index, mtr)

Gets a buffer page and declares its latching order level.

Parameters
page_idtablespace/page identifier
page_sizepage size
modelatch mode
indexindex tree, may be NULL if not the insert buffer tree
mtrmini-transaction handle
Returns
the block descriptor

◆ btr_insert_on_non_leaf_level

#define btr_insert_on_non_leaf_level (   f,
  i,
  l,
  t,
 
)    btr_insert_on_non_leaf_level_func(f, i, l, t, __FILE__, __LINE__, m)

◆ BTR_LATCH_MODE_WITHOUT_FLAGS

#define BTR_LATCH_MODE_WITHOUT_FLAGS (   latch_mode)
Value:
((latch_mode) & \
constexpr size_t BTR_LATCH_FOR_DELETE
In the case of BTR_MODIFY_TREE, the caller specifies the intention to delete record only...
Definition: btr0btr.h:116
constexpr size_t BTR_ALREADY_S_LATCHED
In the case of BTR_SEARCH_LEAF or BTR_MODIFY_LEAF, the caller is already holding an S latch on the in...
Definition: btr0btr.h:108
constexpr size_t BTR_IGNORE_SEC_UNIQUE
This flag ORed to BTR_INSERT says that we can ignore possible UNIQUE definition on secondary indexes ...
Definition: btr0btr.h:96
constexpr size_t BTR_MODIFY_EXTERNAL
In the case of BTR_MODIFY_LEAF, the caller intends to allocate or free the pages of externally stored...
Definition: btr0btr.h:124
constexpr size_t BTR_RTREE_UNDO_INS
This flag is for undo insert of rtree.
Definition: btr0btr.h:120
constexpr size_t BTR_DELETE
Try to purge the record at the searched position using the insert/delete buffer when the record is no...
Definition: btr0btr.h:104
constexpr size_t BTR_LATCH_FOR_INSERT
In the case of BTR_MODIFY_TREE, the caller specifies the intention to insert record only...
Definition: btr0btr.h:112
constexpr size_t BTR_DELETE_MARK
Try to delete mark the record at the searched position using the insert/delete buffer when the record...
Definition: btr0btr.h:100
constexpr size_t BTR_INSERT
If this is ORed to btr_latch_mode, it means that the search tuple will be inserted to the index...
Definition: btr0btr.h:87
constexpr size_t BTR_ESTIMATE
This flag ORed to btr_latch_mode says that we do the search in query optimization.
Definition: btr0btr.h:91
constexpr size_t BTR_RTREE_DELETE_MARK
Try to delete mark the record at the searched position when the record is in spatial index...
Definition: btr0btr.h:128

◆ BTR_LATCH_MODE_WITHOUT_INTENTION

#define BTR_LATCH_MODE_WITHOUT_INTENTION (   latch_mode)
Value:
((latch_mode) & \
constexpr size_t BTR_LATCH_FOR_DELETE
In the case of BTR_MODIFY_TREE, the caller specifies the intention to delete record only...
Definition: btr0btr.h:116
constexpr size_t BTR_MODIFY_EXTERNAL
In the case of BTR_MODIFY_LEAF, the caller intends to allocate or free the pages of externally stored...
Definition: btr0btr.h:124
constexpr size_t BTR_LATCH_FOR_INSERT
In the case of BTR_MODIFY_TREE, the caller specifies the intention to insert record only...
Definition: btr0btr.h:112

◆ BTR_MAX_LEVELS

#define BTR_MAX_LEVELS   100

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_N_LEAF_PAGES

#define BTR_N_LEAF_PAGES   1

◆ btr_page_get

#define btr_page_get (   page_id,
  page_size,
  mode,
  index,
  mtr 
)    buf_block_get_frame(btr_block_get(page_id, page_size, mode, index, mtr))

Gets a buffer page and declares its latching order level.

Parameters
page_idtablespace/page identifier
page_sizepage size
modelatch mode
indexindex tree, may be NULL if not the insert buffer tree
mtrmini-transaction handle
Returns
the uncompressed page frame

◆ btr_page_get_level

#define btr_page_get_level (   page,
  mtr 
)    btr_page_get_level_low(page)

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

◆ BTR_TOTAL_SIZE

#define BTR_TOTAL_SIZE   2

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

UNIV_INLINE buf_block_t* btr_block_get_func ( const page_id_t page_id,
const page_size_t page_size,
ulint  mode,
const char *  file,
ulint  line,
const dict_index_t index,
mtr_t mtr 
)

Gets a buffer page and declares its latching order level.

Parameters
[in]page_idpage id
[in]page_sizepage size
[in]modelatch mode
[in]filefile name
[in]lineline where 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()

ibool btr_check_node_ptr ( dict_index_t index,
buf_block_t block,
mtr_t mtr 
)

Checks that the node pointer to a page is appropriate.

Returns
true
Parameters
indexin: index tree
blockin: index page
mtrin: mtr

◆ btr_compress()

ibool btr_compress ( btr_cur_t cursor,
ibool  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.

Returns
true on success in/out: mini-transaction

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.

Returns
true on success
Parameters
cursorin/out: 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
adjustin: TRUE if should adjust the cursor position even if compression occurs
mtrin/out: mini-transaction

◆ 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,
const page_size_t page_size,
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]page_sizepage size
[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_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
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)
Parameters
indexin: index tree
mtrin/out: mini-transaction

◆ btr_index_rec_validate()

ibool btr_index_rec_validate ( const rec_t rec,
const dict_index_t index,
ibool  dump_on_error 
)

Checks the size and number of fields in a record based on the definition of the index.

Returns
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_func()

void btr_insert_on_non_leaf_level_func ( uint32_t  flags,
dict_index_t index,
ulint  level,
dtuple_t tuple,
const char *  file,
ulint  line,
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: mtr

It is assumed that mtr holds an x-latch on the tree.

Parameters
flagsin: undo logging and locking flags
indexin: index
levelin: level, must be > 0
tuplein: the record to be inserted
filein: file name
linein: line where called
mtrin: mtr

◆ btr_leaf_page_release()

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

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.

in: mtr

Parameters
indexin: index tree
blockin: page whose node pointer is deleted
mtrin: mtr

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

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

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

Returns
child node address
Parameters
recin: node pointer record
offsetsin: array returned by rec_get_offsets()

◆ btr_page_alloc()

buf_block_t* btr_page_alloc ( dict_index_t index,
page_no_t  hint_page_no,
byte  file_direction,
ulint  level,
mtr_t mtr,
mtr_t init_mtr 
)

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!

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)
block(not allocated or initialized) otherwise
Parameters
indexin: index
hint_page_noin: hint of a good page
file_directionin: direction where a possible page split is made
levelin: level where the page is placed in the tree
mtrin/out: mini-transaction for the allocation
init_mtrin/out: mini-transaction for x-latching and initializing the page

◆ 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. in: mtr

Can be used also to (BLOB) external storage pages.

Parameters
indexin: index tree
blockin: block to be freed, x-latched
levelin: page level (ULINT_UNDEFINED=BLOB)
mtrin: mtr

◆ btr_page_get_index_id()

UNIV_INLINE space_index_t btr_page_get_index_id ( const page_t page)

Gets the index id field of a page.

Returns
index id
Parameters
pagein: index page

◆ btr_page_get_level_low()

UNIV_INLINE ulint btr_page_get_level_low ( const page_t page)

Gets the node level field in an index page.

Returns
level, leaf level == 0
Parameters
pagein: index page

◆ btr_page_get_next()

UNIV_INLINE page_no_t btr_page_get_next ( const page_t page,
mtr_t mtr 
)

Gets the next index page number.

Returns
next page number
Parameters
pagein: index page
mtrin: mini-transaction handle

◆ btr_page_get_prev()

UNIV_INLINE page_no_t btr_page_get_prev ( const page_t page,
mtr_t mtr 
)

Gets the previous index page number.

Returns
prev page number
Parameters
pagein: index page
mtrin: mini-transaction handle

◆ btr_page_get_split_rec_to_left()

ibool 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

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

ibool 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

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.

Return values
trueif the operation was successful
falseif it is a compressed page, and recompression failed in/out: mini-transaction

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.

Return values
trueif the operation was successful
falseif it is a compressed page, and recompression failed
Parameters
cursorin/out: page cursor
indexin: the index tree of the page
mtrin/out: mini-transaction

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

Return values
trueif the operation was successful
falseif it is a compressed page, and recompression failed
Parameters
recoveryin: 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
z_levelin: compression level to be used if dealing with compressed page
cursorin/out: page cursor
indexin: the index tree of the page
mtrin/out: mini-transaction

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

byte* btr_parse_page_reorganize ( byte ptr,
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
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()

byte* btr_parse_set_min_rec_mark ( byte ptr,
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
Parameters
ptrin: buffer
end_ptrin: buffer end
compin: nonzero=compact page format
pagein: page or NULL
mtrin: mtr or NULL

◆ 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
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
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

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.

in: mtr

Parameters
recin: record
mtrin: mtr

◆ 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 implement recovery by calling btr_truncate_recover().

Parameters
[in]indexclustered index

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_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
Parameters
indexin: index
trxin: transaction or NULL
lockoutin: true if X-latch index is intended

Variable Documentation

◆ BTR_ALREADY_S_LATCHED

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.

◆ BTR_DELETE

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.

◆ BTR_DELETE_MARK

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.

◆ BTR_ESTIMATE

constexpr size_t BTR_ESTIMATE = 1024

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

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

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

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

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_MODIFY_EXTERNAL

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.

◆ BTR_RTREE_DELETE_MARK

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.

◆ BTR_RTREE_UNDO_INS

constexpr size_t BTR_RTREE_UNDO_INS = 131072

This flag is for undo insert of rtree.

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