MySQL 9.0.0
Source Code Documentation
btr0btr.cc File Reference

The B-tree. More...

#include "btr0btr.h"
#include <sys/types.h>
#include "btr0cur.h"
#include "btr0pcur.h"
#include "btr0sea.h"
#include "buf0stats.h"
#include "dict0boot.h"
#include "fsp0sysspace.h"
#include "gis0geo.h"
#include "gis0rtree.h"
#include "ibuf0ibuf.h"
#include "lock0lock.h"
#include "my_dbug.h"
#include "page0page.h"
#include "page0zip.h"
#include "rem0cmp.h"
#include "srv0mon.h"
#include "trx0trx.h"
#include "ut0new.h"

Classes

struct  Index_details
 

Functions

static bool btr_can_merge_with_page (btr_cur_t *cursor, page_no_t page_no, buf_block_t **merge_block, mtr_t *mtr)
 Checks if the page in the cursor can be merged with given page. More...
 
void btr_corruption_report (const buf_block_t *block, const dict_index_t *index)
 Report that an index page is corrupted. 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...
 
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...
 
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 bool btr_root_fseg_adjust_on_import (fseg_header_t *seg_header, page_zip_des_t *page_zip, space_id_t space, mtr_t *mtr)
 Checks a file segment header within a B-tree root page and updates the segment header space id. 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...
 
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...
 
static buf_block_tbtr_page_alloc_for_ibuf (dict_index_t *index, mtr_t *mtr)
 Allocates a new file page to be used in an ibuf tree. More...
 
static buf_block_tbtr_page_alloc_low (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...
 
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...
 
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...
 
ulint btr_get_size (dict_index_t *index, ulint flag, mtr_t *mtr)
 Gets the number of pages in a B-tree. More...
 
static void btr_page_free_for_ibuf (dict_index_t *index, buf_block_t *block, mtr_t *mtr)
 Frees a page used in an ibuf tree. 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...
 
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...
 
static void btr_node_ptr_set_child_page_no (rec_t *rec, page_zip_des_t *page_zip, const ulint *offsets, page_no_t page_no, mtr_t *mtr)
 Sets 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)
 Returns the child page of a node pointer and sx-latches it. More...
 
static ulintbtr_page_get_father_node_ptr_func (ulint *offsets, mem_heap_t *heap, btr_cur_t *cursor, ulint latch_mode, ut::Location location, mtr_t *mtr)
 Returns the upper level node pointer to a page. More...
 
ulintbtr_page_get_father_node_ptr (ulint *offsets, mem_heap_t *heap, btr_cur_t *cursor, ut::Location location, mtr_t *mtr)
 
ulintbtr_page_get_father_node_ptr_for_validate (ulint *offsets, mem_heap_t *heap, btr_cur_t *cursor, ut::Location location, mtr_t *mtr)
 
static ulintbtr_page_get_father_block (ulint *offsets, mem_heap_t *heap, dict_index_t *index, buf_block_t *block, mtr_t *mtr, btr_cur_t *cursor)
 Returns the upper level node pointer to a page. More...
 
static void btr_page_get_father (dict_index_t *index, buf_block_t *block, mtr_t *mtr, btr_cur_t *cursor)
 Seeks to the upper level node pointer to a page. More...
 
static void btr_free_root (buf_block_t *block, mtr_t *mtr)
 Free a B-tree root page. More...
 
static void btr_free_root_invalidate (buf_block_t *block, mtr_t *mtr)
 Invalidate an index root page so that btr_free_root_check() will not find it. More...
 
static buf_block_tbtr_free_root_check (const page_id_t &page_id, const page_size_t &page_size, space_index_t index_id, mtr_t *mtr)
 Prepare to free a B-tree. 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...
 
static void btr_free_but_not_root (buf_block_t *block, mtr_log_t log_mode)
 Free a B-tree except the root page. 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...
 
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...
 
static bool btr_page_reorganize_block (bool recovery, ulint z_level, buf_block_t *block, 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...
 
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...
 
static void btr_page_empty (buf_block_t *block, page_zip_des_t *page_zip, dict_index_t *index, ulint level, mtr_t *mtr)
 Empties an index page. 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_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 the 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 the right. More...
 
static rec_tbtr_page_get_split_rec (btr_cur_t *cursor, const dtuple_t *tuple)
 Calculates a split record such that the tuple will certainly fit on its half-page when the split is performed. More...
 
static bool btr_page_insert_fits (btr_cur_t *cursor, const rec_t *split_rec, ulint **offsets, const dtuple_t *tuple, mem_heap_t **heap)
 Returns true if the insert fits on the appropriate half-page with the chosen split_rec. 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...
 
static void btr_attach_half_pages (uint32_t flags, dict_index_t *index, buf_block_t *block, const rec_t *split_rec, buf_block_t *new_block, ulint direction, mtr_t *mtr)
 Attaches the halves of an index page on the appropriate level in an index tree. More...
 
static bool btr_page_tuple_smaller (btr_cur_t *cursor, const dtuple_t *tuple, ulint **offsets, ulint n_uniq, mem_heap_t **heap)
 Determine if a tuple is smaller than any record on the page. More...
 
static rec_tbtr_insert_into_right_sibling (uint32_t flags, btr_cur_t *cursor, ulint **offsets, mem_heap_t *heap, const dtuple_t *tuple, mtr_t *mtr)
 Insert the tuple into the right sibling page, if the cursor is at the end of a page. 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...
 
static void btr_level_list_remove (space_id_t space, const page_size_t &page_size, page_t *page, const dict_index_t *index, mtr_t *mtr)
 Removes a page from the level list of pages. More...
 
static void btr_set_min_rec_mark_log (rec_t *rec, mlog_id_t type, mtr_t *mtr)
 Writes the redo log record for setting an index record as the predefined minimum record. 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...
 
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...
 
bool btr_is_index_empty (const dict_index_t *index)
 Check if the given index is empty. 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...
 
static buf_block_tbtr_lift_page_up (dict_index_t *index, buf_block_t *block, mtr_t *mtr)
 If page is the only on its level, this function moves its records to the father page, thus reducing the tree height. 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...
 
static void btr_discard_only_page_on_level (dict_index_t *index, buf_block_t *block, mtr_t *mtr)
 Discards a page that is the only page on its level. More...
 
void btr_discard_page (btr_cur_t *cursor, mtr_t *mtr)
 Discards a page from a B-tree. 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...
 
static void btr_index_rec_validate_report (const page_t *page, const rec_t *rec, const dict_index_t *index)
 Display identification information for a record. 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...
 
static bool btr_index_page_validate (buf_block_t *block, dict_index_t *index)
 Checks the size and number of fields in records based on the definition of the index. More...
 
static void btr_validate_report1 (dict_index_t *index, ulint level, const buf_block_t *block)
 Report an error on one page of an index tree. More...
 
static void btr_validate_report2 (const dict_index_t *index, ulint level, const buf_block_t *block1, const buf_block_t *block2)
 Report an error on two pages of an index tree. More...
 
static bool btr_validate_level (dict_index_t *index, const trx_t *trx, ulint level, bool lockout, Index_details &index_details)
 Validates index tree level. More...
 
static bool btr_validate_spatial_index (dict_index_t *index, const trx_t *trx)
 Do an index level validation of spaital index tree. More...
 
bool btr_validate_index (dict_index_t *index, const trx_t *trx, bool lockout)
 Checks the consistency of an index tree. More...
 
static page_no_t btr_sdi_create (space_id_t space_id, mtr_t *mtr, dict_table_t *table)
 Create an SDI Index. 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

static const space_index_t BTR_FREED_INDEX_ID = 0
 PAGE_INDEX_ID value for freed index B-trees. More...
 

Detailed Description

The B-tree.

Created 6/2/1994 Heikki Tuuri

Function Documentation

◆ btr_attach_half_pages()

static void btr_attach_half_pages ( uint32_t  flags,
dict_index_t index,
buf_block_t block,
const rec_t split_rec,
buf_block_t new_block,
ulint  direction,
mtr_t mtr 
)
static

Attaches the halves of an index page on the appropriate level in an index tree.

Parameters
flagsin: undo logging and locking flags
indexin: the index tree
blockin/out: page to be split
split_recin: first record on upper half page
new_blockin/out: the new half page
directionin: FSP_UP or FSP_DOWN
mtrin: mtr

◆ btr_can_merge_with_page()

static bool btr_can_merge_with_page ( btr_cur_t cursor,
page_no_t  page_no,
buf_block_t **  merge_block,
mtr_t mtr 
)
static

Checks if the page in the cursor can be merged with given page.

If necessary, re-organize the merge_page.

Returns
true if possible to merge. in: mini-transaction

If necessary, re-organize the merge_page.

Returns
true if possible to merge.
Parameters
cursorin: cursor on the page to merge
page_noin: a sibling page
merge_blockout: the merge block
mtrin: mini-transaction

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

static void btr_discard_only_page_on_level ( dict_index_t index,
buf_block_t block,
mtr_t mtr 
)
static

Discards a page that is the only page on its level.

This will empty the whole B-tree, leaving just an empty root page. This function should never be reached, because btr_compress(), which is invoked in delete operations, calls btr_lift_page_up() to flatten the B-tree.

Parameters
indexin: index tree
blockin: page which is the only on its level
mtrin: mtr

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

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

static void btr_free_but_not_root ( buf_block_t block,
mtr_log_t  log_mode 
)
static

Free a B-tree except the root page.

The root page MUST be freed after this by calling btr_free_root.

Parameters
[in,out]blockroot page
[in]log_modemtr logging mode

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

static void btr_free_root ( buf_block_t block,
mtr_t mtr 
)
static

Free a B-tree root page.

btr_free_but_not_root() must already have been called. In a persistent tablespace, the caller must invoke fsp_init_file_page() before mtr.commit().

Parameters
[in,out]blockIndex root page
[in,out]mtrMini-transaction

◆ btr_free_root_check()

static buf_block_t * btr_free_root_check ( const page_id_t page_id,
const page_size_t page_size,
space_index_t  index_id,
mtr_t mtr 
)
static

Prepare to free a B-tree.

Parameters
[in]page_idPage id
[in]page_sizePage size
[in]index_idPAGE_INDEX_ID contents
[in,out]mtrMini-transaction
Returns
root block, to invoke btr_free_but_not_root() and btr_free_root()
Return values
NULLif the page is no longer a matching B-tree page

◆ btr_free_root_invalidate()

static void btr_free_root_invalidate ( buf_block_t block,
mtr_t mtr 
)
static

Invalidate an index root page so that btr_free_root_check() will not find it.

Parameters
[in,out]blockIndex root page
[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_page_validate()

static bool btr_index_page_validate ( buf_block_t block,
dict_index_t index 
)
static

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

Returns
true if ok
Parameters
blockin: index page
indexin: index

◆ 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
Parameters
recin: index record
indexin: index
dump_on_errorin: true if the function should print hex dump of record and page on error

◆ btr_index_rec_validate_report()

static void btr_index_rec_validate_report ( const page_t page,
const rec_t rec,
const dict_index_t index 
)
static

Display identification information for a record.

Parameters
pagein: index page
recin: index record
indexin: index

◆ btr_insert_into_right_sibling()

static rec_t * btr_insert_into_right_sibling ( uint32_t  flags,
btr_cur_t cursor,
ulint **  offsets,
mem_heap_t heap,
const dtuple_t tuple,
mtr_t mtr 
)
static

Insert the tuple into the right sibling page, if the cursor is at the end of a page.

Parameters
[in]flagsUndo logging and locking flags
[in,out]cursorCursor at which to insert; when the function succeeds, the cursor is positioned before the insert point.
[out]offsetsOffsets on inserted record
[in,out]heapMemory heap for allocating offsets
[in]tupleTuple to insert
[in,out]mtrMini-transaction
Returns
inserted record (first record on the right sibling page); the cursor will be positioned on the page infimum
Return values
NULLif the operation was not performed

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

static void btr_level_list_remove ( space_id_t  space,
const page_size_t page_size,
page_t page,
const dict_index_t index,
mtr_t mtr 
)
static

Removes a page from the level list of pages.

Parameters
[in]spaceSpace where removed
[in]page_sizePage size
[in,out]pagePage to remove
[in]indexIndex tree
[in,out]mtrMini-transaction

◆ btr_lift_page_up()

static buf_block_t * btr_lift_page_up ( dict_index_t index,
buf_block_t block,
mtr_t mtr 
)
static

If page is the only on its level, this function moves its records to the father page, thus reducing the tree height.

Returns
father block

< last used index in blocks[]

Parameters
indexin: index tree
blockin: page which is the only on its level; must not be empty: use btr_discard_only_page_on_level if the last record from the page should be removed
mtrin: mtr

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

static void btr_node_ptr_set_child_page_no ( rec_t rec,
page_zip_des_t page_zip,
const ulint offsets,
page_no_t  page_no,
mtr_t mtr 
)
inlinestatic

Sets the child node file address in a node pointer.

Parameters
recin: node pointer record
page_zipin/out: compressed page whose uncompressed part will be updated, or NULL
offsetsin: array returned by rec_get_offsets()
page_noin: child node address
mtrin: mtr

◆ btr_page_alloc_for_ibuf()

static buf_block_t * btr_page_alloc_for_ibuf ( dict_index_t index,
mtr_t mtr 
)
static

Allocates a new file page to be used in an ibuf tree.

Takes the page from the free list of the tree, which must contain pages!

Returns
new allocated block, x-latched
Parameters
indexin: index tree
mtrin: mtr

◆ btr_page_alloc_low()

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

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), returned block is not allocated nor 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: mtr or another mini-transaction in which the page should be initialized. If init_mtr!=mtr, but the page is already X-latched in mtr, do not initialize the page.

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

static void btr_page_empty ( buf_block_t block,
page_zip_des_t page_zip,
dict_index_t index,
ulint  level,
mtr_t mtr 
)
static

Empties an index page.

See also
btr_page_create().
Parameters
blockin: page to be emptied
page_zipout: compressed page, or NULL
indexin: index of the page
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.

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

◆ btr_page_free_for_ibuf()

static void btr_page_free_for_ibuf ( dict_index_t index,
buf_block_t block,
mtr_t mtr 
)
static

Frees a page used in an ibuf tree.

Puts the page to the free list of the ibuf tree.

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

static void btr_page_get_father ( dict_index_t index,
buf_block_t block,
mtr_t mtr,
btr_cur_t cursor 
)
static

Seeks to the upper level node pointer to a page.

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

Parameters
indexin: b-tree index
blockin: child page in the index
mtrin: mtr
cursorout: cursor on node pointer record, its page x-latched

◆ btr_page_get_father_block()

static ulint * btr_page_get_father_block ( ulint offsets,
mem_heap_t heap,
dict_index_t index,
buf_block_t block,
mtr_t mtr,
btr_cur_t cursor 
)
static

Returns the upper level node pointer to a page.

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

Returns
rec_get_offsets() of the node pointer record
Parameters
offsetsin: work area for the return value
heapin: memory heap to use
indexin: b-tree index
blockin: child page in the index
mtrin: mtr
cursorout: cursor on node pointer record, its page x-latched

◆ btr_page_get_father_node_ptr()

ulint * btr_page_get_father_node_ptr ( ulint offsets,
mem_heap_t heap,
btr_cur_t cursor,
ut::Location  location,
mtr_t mtr 
)
inline

◆ btr_page_get_father_node_ptr_for_validate()

ulint * btr_page_get_father_node_ptr_for_validate ( ulint offsets,
mem_heap_t heap,
btr_cur_t cursor,
ut::Location  location,
mtr_t mtr 
)
inline

◆ btr_page_get_father_node_ptr_func()

static ulint * btr_page_get_father_node_ptr_func ( ulint offsets,
mem_heap_t heap,
btr_cur_t cursor,
ulint  latch_mode,
ut::Location  location,
mtr_t mtr 
)
static

Returns the upper level node pointer to a page.

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

Parameters
[in]offsetswork area for the return value
[in]heapmemory heap to use
[in,out]cursorin: cursor pointing to user record, out: cursor on node pointer record, its page x-latched
[in]latch_modeBTR_CONT_MODIFY_TREE or BTR_CONT_SEARCH_TREE
[in]locationlocation where called
[in]mtrmtr
Returns
rec_get_offsets() of the node pointer record

◆ btr_page_get_split_rec()

static rec_t * btr_page_get_split_rec ( btr_cur_t cursor,
const dtuple_t tuple 
)
static

Calculates a split record such that the tuple will certainly fit on its half-page when the split is performed.

We assume in this function only that the cursor page has at least one user record.

Returns
split record, or NULL if tuple will be the first record on the lower or upper half-page (determined by btr_page_tuple_smaller())
Parameters
cursorin: cursor at which insert should be made
tuplein: tuple to insert

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

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

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

static bool btr_page_insert_fits ( btr_cur_t cursor,
const rec_t split_rec,
ulint **  offsets,
const dtuple_t tuple,
mem_heap_t **  heap 
)
static

Returns true if the insert fits on the appropriate half-page with the chosen split_rec.

Returns
true if fits
Parameters
cursorin: cursor at which insert should be made
split_recin: suggestion for first record on upper half-page, or NULL if tuple to be inserted should be first
offsetsin: rec_get_offsets( split_rec, cursor->index); out: garbage
tuplein: tuple to insert
heapin: temporary memory heap

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

static bool btr_page_reorganize_block ( bool  recovery,
ulint  z_level,
buf_block_t block,
dict_index_t index,
mtr_t mtr 
)
static

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
blockin/out: B-tree page
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.

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

static bool btr_page_tuple_smaller ( btr_cur_t cursor,
const dtuple_t tuple,
ulint **  offsets,
ulint  n_uniq,
mem_heap_t **  heap 
)
static

Determine if a tuple is smaller than any record on the page.

Returns
true if smaller
Parameters
cursorin: b-tree cursor
tuplein: tuple to consider
offsetsin/out: temporary storage
n_uniqin: number of unique fields in the index page records
heapin/out: heap for offsets

◆ 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
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
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
Parameters
indexin: index tree
modein: either RW_S_LATCH or RW_X_LATCH
mtrin: mtr

◆ btr_root_fseg_adjust_on_import()

static bool btr_root_fseg_adjust_on_import ( fseg_header_t seg_header,
page_zip_des_t page_zip,
space_id_t  space,
mtr_t mtr 
)
static

Checks a file segment header within a B-tree root page and updates the segment header space id.

Returns
true if valid
Parameters
seg_headerin/out: segment header
page_zipin/out: compressed page, or NULL
spacein: tablespace identifier
mtrin/out: mini-transaction

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

static page_no_t btr_sdi_create ( space_id_t  space_id,
mtr_t mtr,
dict_table_t table 
)
static

Create an SDI Index.

Parameters
[in]space_idTablespace id
[in,out]mtrMini-transaction
[in,out]tableSDI table
Returns
root page number of the SDI index created or FIL_NULL on failure

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

static void btr_set_min_rec_mark_log ( rec_t rec,
mlog_id_t  type,
mtr_t mtr 
)
inlinestatic

Writes the redo log record for setting an index record as the predefined minimum record.

Parameters
recin: record
typein: MLOG_COMP_REC_MIN_MARK or MLOG_REC_MIN_MARK
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 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
Parameters
indexin: index
trxin: transaction or NULL
lockoutin: true if X-latch index is intended

◆ btr_validate_level()

static bool btr_validate_level ( dict_index_t index,
const trx_t trx,
ulint  level,
bool  lockout,
Index_details index_details 
)
static

Validates index tree level.

Parameters
[in]indexindex dictionary object.
[in]trxtransaction or nullptr
[in]levellevel number to validate
[in]lockouttrue if X-latch index is intended
[in]index_detailsdebug only argument to collect index details.
Returns
true if ok

◆ btr_validate_report1()

static void btr_validate_report1 ( dict_index_t index,
ulint  level,
const buf_block_t block 
)
static

Report an error on one page of an index tree.

Parameters
indexin: index
levelin: B-tree level
blockin: index page

◆ btr_validate_report2()

static void btr_validate_report2 ( const dict_index_t index,
ulint  level,
const buf_block_t block1,
const buf_block_t block2 
)
static

Report an error on two pages of an index tree.

Parameters
indexin: index
levelin: B-tree level
block1in: first index page
block2in: second index page

◆ btr_validate_spatial_index()

static bool btr_validate_spatial_index ( dict_index_t index,
const trx_t trx 
)
static

Do an index level validation of spaital index tree.

Returns
true if no error found
Parameters
indexin: index
trxin: transaction or NULL

Variable Documentation

◆ BTR_FREED_INDEX_ID

const space_index_t BTR_FREED_INDEX_ID = 0
static

PAGE_INDEX_ID value for freed index B-trees.