MySQL 9.0.0
Source Code Documentation
|
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_t * | btr_root_block_get (const dict_index_t *index, ulint mode, mtr_t *mtr) |
Gets the root node of a tree and x- or s-latches it. More... | |
page_t * | btr_root_get (const dict_index_t *index, mtr_t *mtr) |
Gets the root node of a tree and sx-latches it for segment access. More... | |
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_t * | btr_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_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) |
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_t * | btr_page_alloc_priv (dict_index_t *index, page_no_t hint_page_no, byte file_direction, ulint level, mtr_t *mtr, mtr_t *init_mtr, const ut::Location &loc) |
Allocates a new file page to be used in an index tree. More... | |
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_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) |
Returns the child page of a node pointer and sx-latches it. More... | |
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) |
Returns the upper level node pointer to a page. More... | |
ulint * | btr_page_get_father_node_ptr (ulint *offsets, mem_heap_t *heap, btr_cur_t *cursor, ut::Location location, mtr_t *mtr) |
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) |
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) |
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_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) |
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 byte * | btr_parse_page_reorganize (const byte *ptr, const byte *end_ptr, dict_index_t *index, bool compressed, buf_block_t *block, mtr_t *mtr) |
Parses a redo log record of reorganizing a page. More... | |
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_t * | btr_root_raise_and_insert (uint32_t flags, btr_cur_t *cursor, ulint **offsets, mem_heap_t **heap, const dtuple_t *tuple, mtr_t *mtr) |
Makes tree one level higher by splitting the root, and inserts the tuple. More... | |
bool | btr_page_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_t * | btr_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_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) |
Insert the tuple into the right sibling page, if the cursor is at the end of a page. More... | |
rec_t * | btr_page_split_and_insert (uint32_t flags, btr_cur_t *cursor, ulint **offsets, mem_heap_t **heap, const dtuple_t *tuple, mtr_t *mtr) |
Splits an index page to halves and inserts the tuple. More... | |
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 byte * | btr_parse_set_min_rec_mark (const byte *ptr, const byte *end_ptr, ulint comp, page_t *page, mtr_t *mtr) |
Parses the redo log record for setting an index record as the predefined minimum record. More... | |
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_t * | btr_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... | |
The B-tree.
Created 6/2/1994 Heikki Tuuri
|
static |
Attaches the halves of an index page on the appropriate level in an index tree.
flags | in: undo logging and locking flags |
index | in: the index tree |
block | in/out: page to be split |
split_rec | in: first record on upper half page |
new_block | in/out: the new half page |
direction | in: FSP_UP or FSP_DOWN |
mtr | in: mtr |
|
static |
Checks if the page in the cursor can be merged with given page.
If necessary, re-organize the merge_page.
If necessary, re-organize the merge_page.
cursor | in: cursor on the page to merge |
page_no | in: a sibling page |
merge_block | out: the merge block |
mtr | in: mini-transaction |
bool btr_check_node_ptr | ( | dict_index_t * | index, |
buf_block_t * | block, | ||
mtr_t * | mtr | ||
) |
Asserts that the node pointer to a page is appropriate.
[in] | index | index tree |
[in] | block | index page |
[in] | mtr | mtr |
Tries to merge the page first to the left immediate brother if such a brother exists, and the node pointers to the current page and to the brother reside on the same page.
If the left brother does not satisfy these conditions, looks at the right brother. If the page is the only one on that level lifts the records of the page to the father page, thus reducing the tree height. It is assumed that mtr holds an x-latch on the tree and on the page. If cursor is on the leaf level, mtr must also hold x-latches to the brothers, if they exist.
[in,out] | cursor | cursor on the page to merge or lift; the page must not be empty: when deleting records, use btr_discard_page() if the page would become empty |
[in] | adjust | true if should adjust the cursor position even if compression occurs. |
[in,out] | mtr | mini-transaction |
void btr_corruption_report | ( | const buf_block_t * | block, |
const dict_index_t * | index | ||
) |
Report that an index page is corrupted.
block | in: corrupted block |
index | in: index tree |
ulint btr_create | ( | ulint | type, |
space_id_t | space, | ||
space_index_t | index_id, | ||
dict_index_t * | index, | ||
mtr_t * | mtr | ||
) |
Create the root node for a new index tree.
[in] | type | Type of the index |
[in] | space | Space where created |
[in] | index_id | Index id |
[in] | index | Index tree |
[in,out] | mtr | Mini-transaction |
FIL_NULL | if did not succeed |
|
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.
index | in: index tree |
block | in: page which is the only on its level |
mtr | in: mtr |
Discards a page from a B-tree.
This is used to remove the last record from a B-tree page: the whole page must be removed at the same time. This cannot be used for the root page, which is allowed to be empty.
cursor | in: cursor on the page to discard: not on the root page |
mtr | in: mtr |
dberr_t btr_extent_alloc | ( | const dict_index_t *const | index, |
bool | is_leaf, | ||
Page_range_t & | page_range, | ||
mtr_t * | mtr | ||
) |
Allocates all pages of one extent to be used in an index tree.
[in] | index | the index for which pages are allocated. |
[in] | is_leaf | true if leaf segment and false if non-leaf segment |
[out] | page_range | All pages within this pair of page numbers are allocated for this B-tree. The page_range.first is part of the range, while the page_range.second is not part of the range. |
[in] | mtr | mini transaction context for this operation. |
void btr_free | ( | const page_id_t & | page_id, |
const page_size_t & | page_size | ||
) |
Free an index tree in a temporary tablespace.
[in] | page_id | root page id |
[in] | page_size | page size |
|
static |
Free a B-tree except the root page.
The root page MUST be freed after this by calling btr_free_root.
[in,out] | block | root page |
[in] | log_mode | mtr logging mode |
void btr_free_if_exists | ( | const page_id_t & | page_id, |
const page_size_t & | page_size, | ||
space_index_t | index_id, | ||
mtr_t * | mtr | ||
) |
Free a persistent index tree if it exists.
[in] | page_id | Root page id |
[in] | page_size | Page size |
[in] | index_id | PAGE_INDEX_ID contents |
[in,out] | mtr | Mini-transaction |
|
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().
[in,out] | block | Index root page |
[in,out] | mtr | Mini-transaction |
|
static |
Prepare to free a B-tree.
[in] | page_id | Page id |
[in] | page_size | Page size |
[in] | index_id | PAGE_INDEX_ID contents |
[in,out] | mtr | Mini-transaction |
NULL | if the page is no longer a matching B-tree page |
|
static |
Invalidate an index root page so that btr_free_root_check() will not find it.
[in,out] | block | Index root page |
[in,out] | mtr | Mini-transaction |
ulint btr_get_size | ( | dict_index_t * | index, |
ulint | flag, | ||
mtr_t * | mtr | ||
) |
Gets the number of pages in a B-tree.
index | in: index |
flag | in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE |
mtr | in/out: mini-transaction where index is s-latched |
ulint btr_height_get | ( | dict_index_t * | index, |
mtr_t * | mtr | ||
) |
Gets the height of the B-tree (the level of the root, when the leaf level is assumed to be 0).
The caller must hold an S or X latch on the index.
index | in: index tree |
mtr | in/out: mini-transaction |
|
static |
Checks the size and number of fields in records based on the definition of the index.
block | in: index page |
index | in: index |
bool btr_index_rec_validate | ( | const rec_t * | rec, |
const dict_index_t * | index, | ||
bool | dump_on_error | ||
) |
Checks the size and number of fields in a record based on the definition of the index.
rec | in: index record |
index | in: index |
dump_on_error | in: true if the function should print hex dump of record and page on error |
|
static |
Display identification information for a record.
page | in: index page |
rec | in: index record |
index | in: index |
|
static |
Insert the tuple into the right sibling page, if the cursor is at the end of a page.
[in] | flags | Undo logging and locking flags |
[in,out] | cursor | Cursor at which to insert; when the function succeeds, the cursor is positioned before the insert point. |
[out] | offsets | Offsets on inserted record |
[in,out] | heap | Memory heap for allocating offsets |
[in] | tuple | Tuple to insert |
[in,out] | mtr | Mini-transaction |
NULL | if the operation was not performed |
void btr_insert_on_non_leaf_level | ( | uint32_t | flags, |
dict_index_t * | index, | ||
ulint | level, | ||
dtuple_t * | tuple, | ||
ut::Location | location, | ||
mtr_t * | mtr | ||
) |
Inserts a data tuple to a tree on a non-leaf level.
It is assumed that mtr holds an x-latch on the tree.
[in] | flags | undo logging and locking flags |
[in] | index | index |
[in] | level | level, must be > 0 |
[in] | tuple | the record to be inserted |
[in] | location | location where called |
[in] | mtr | mtr |
bool btr_is_index_empty | ( | const dict_index_t * | index | ) |
Check if the given index is empty.
An index is considered empty if it has only the root page with no user records, including del-marked records.
[in] | index | index |
|
static |
Removes a page from the level list of pages.
[in] | space | Space where removed |
[in] | page_size | Page size |
[in,out] | page | Page to remove |
[in] | index | Index tree |
[in,out] | mtr | Mini-transaction |
|
static |
If page is the only on its level, this function moves its records to the father page, thus reducing the tree height.
< last used index in blocks[]
index | in: index tree |
block | in: 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 |
mtr | in: mtr |
void btr_node_ptr_delete | ( | dict_index_t * | index, |
buf_block_t * | block, | ||
mtr_t * | mtr | ||
) |
Deletes on the upper level the node pointer to a page.
[in] | index | Index tree |
[in] | block | Page whose node pointer is deleted |
[in] | mtr | Mini-transaction |
buf_block_t * btr_node_ptr_get_child | ( | const rec_t * | node_ptr, |
dict_index_t * | index, | ||
const ulint * | offsets, | ||
mtr_t * | mtr, | ||
rw_lock_type_t | type = RW_SX_LATCH |
||
) |
Returns the child page of a node pointer and sx-latches it.
[in] | node_ptr | node pointer |
[in] | index | index |
[in] | offsets | array returned by rec_get_offsets() |
[in] | mtr | mtr |
[in] | type | latch type |
|
inlinestatic |
Sets the child node file address in a node pointer.
rec | in: node pointer record |
page_zip | in/out: compressed page whose uncompressed part will be updated, or NULL |
offsets | in: array returned by rec_get_offsets() |
page_no | in: child node address |
mtr | in: 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!
index | in: index tree |
mtr | in: 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!
NULL | if no page could be allocated |
block,rw_lock_x_lock_count(&block->lock) | == 1 if allocation succeeded (init_mtr == mtr, or the page was not previously freed in mtr), returned block is not allocated nor initialized otherwise |
index | in: index |
hint_page_no | in: hint of a good page |
file_direction | in: direction where a possible page split is made |
level | in: level where the page is placed in the tree |
mtr | in/out: mini-transaction for the allocation |
init_mtr | in/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. |
buf_block_t * btr_page_alloc_priv | ( | dict_index_t * | index, |
page_no_t | hint_page_no, | ||
byte | file_direction, | ||
ulint | level, | ||
mtr_t * | mtr, | ||
mtr_t * | init_mtr, | ||
const ut::Location & | loc | ||
) |
Allocates a new file page to be used in an index tree.
NOTE: we assume that the caller has made the reservation for free extents!
[in] | index | Index tree |
[in] | hint_page_no | Hint of a good page |
[in] | file_direction | Direction where a possible page split is made |
[in] | level | Level where the page is placed in the tree |
[in,out] | mtr | Mini-transaction for the allocation |
[in,out] | init_mtr | Mini-transaction for x-latching and initializing the page |
[in] | loc | debug only parameter providing caller source location. |
NULL | if no page could be allocated |
block,rw_lock_x_lock_count(&block->lock) | == 1 if allocation succeeded (init_mtr == mtr, or the page was not previously freed in mtr), returned block is not allocated nor initialized otherwise |
void btr_page_create | ( | buf_block_t * | block, |
page_zip_des_t * | page_zip, | ||
dict_index_t * | index, | ||
ulint | level, | ||
mtr_t * | mtr | ||
) |
Creates a new index page (not the root, and also not used in page reorganization).
block | in/out: page to be created |
page_zip | in/out: compressed page, or NULL |
index | in: index |
level | in: the B-tree level of the page |
mtr | in: mtr |
|
static |
Empties an index page.
block | in: page to be emptied |
page_zip | out: compressed page, or NULL |
index | in: index of the page |
level | in: the B-tree level of the page |
mtr | in: mtr |
void btr_page_free | ( | dict_index_t * | index, |
buf_block_t * | block, | ||
mtr_t * | mtr | ||
) |
Frees a file page used in an index tree.
NOTE: cannot free field external storage pages because the page must contain info on its level.
index | in: index tree |
block | in: block to be freed, x-latched |
mtr | in: mtr |
|
static |
Frees a page used in an ibuf tree.
Puts the page to the free list of the ibuf tree.
index | in: index tree |
block | in: block to be freed, x-latched |
mtr | in: mtr |
void btr_page_free_low | ( | dict_index_t * | index, |
buf_block_t * | block, | ||
ulint | level, | ||
mtr_t * | mtr | ||
) |
Frees a file page used in an index tree.
Can be used also to BLOB external storage pages.
[in] | index | the index to which the page belongs |
[in] | block | block to be freed, x-latched |
[in] | level | page level (ULINT_UNDEFINED=BLOB) |
[in] | mtr | mini transaction context. |
|
static |
Seeks to the upper level node pointer to a page.
It is assumed that mtr holds an x-latch on the tree.
index | in: b-tree index |
block | in: child page in the index |
mtr | in: mtr |
cursor | out: cursor on node pointer record, its page x-latched |
|
static |
Returns the upper level node pointer to a page.
It is assumed that mtr holds an x-latch on the tree.
offsets | in: work area for the return value |
heap | in: memory heap to use |
index | in: b-tree index |
block | in: child page in the index |
mtr | in: mtr |
cursor | out: cursor on node pointer record, its page x-latched |
|
inline |
|
inline |
|
static |
Returns the upper level node pointer to a page.
It is assumed that mtr holds an sx-latch on the tree.
[in] | offsets | work area for the return value |
[in] | heap | memory heap to use |
[in,out] | cursor | in: cursor pointing to user record, out: cursor on node pointer record, its page x-latched |
[in] | latch_mode | BTR_CONT_MODIFY_TREE or BTR_CONT_SEARCH_TREE |
[in] | location | location where called |
[in] | mtr | mtr |
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.
cursor | in: cursor at which insert should be made |
tuple | in: tuple to insert |
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.
cursor | in: cursor at which to insert |
split_rec | out: if split recommended, the first record on upper half page, or NULL if tuple to be inserted should be first |
Decides if the page should be split at the convergence point of inserts converging to the right.
Decides if the page should be split at the convergence point of inserts converging to right.
cursor | in: cursor at which to insert |
split_rec | out: if split recommended, the first record on upper half page, or NULL if tuple to be inserted should be first |
|
static |
Returns true if the insert fits on the appropriate half-page with the chosen split_rec.
cursor | in: cursor at which insert should be made |
split_rec | in: suggestion for first record on upper half-page, or NULL if tuple to be inserted should be first |
offsets | in: rec_get_offsets( split_rec, cursor->index); out: garbage |
tuple | in: tuple to insert |
heap | in: temporary memory heap |
bool btr_page_reorganize | ( | page_cur_t * | cursor, |
dict_index_t * | index, | ||
mtr_t * | mtr | ||
) |
Reorganizes an index page.
IMPORTANT: On success, the caller will have to update IBUF_BITMAP_FREE if this is a compressed leaf page in a secondary index. This has to be done either within the same mini-transaction, or by invoking ibuf_reset_free_bits() before mtr_commit(). On uncompressed pages, IBUF_BITMAP_FREE is unaffected by reorganization.
[in,out] | cursor | Page cursor |
[in] | index | The index tree of the page |
[in,out] | mtr | Mini-transaction |
true | if the operation was successful |
false | if it is a compressed page, and recompression failed |
|
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.
true | if the operation was successful |
false | if it is a compressed page, and recompression failed |
recovery | in: 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_level | in: compression level to be used if dealing with compressed page |
block | in/out: B-tree page |
index | in: the index tree of the page |
mtr | in/out: mini-transaction |
bool btr_page_reorganize_low | ( | bool | recovery, |
ulint | z_level, | ||
page_cur_t * | cursor, | ||
dict_index_t * | index, | ||
mtr_t * | mtr | ||
) |
Reorganizes an index page.
IMPORTANT: On success, the caller will have to update IBUF_BITMAP_FREE if this is a compressed leaf page in a secondary index. This has to be done either within the same mini-transaction, or by invoking ibuf_reset_free_bits() before mtr_commit(). On uncompressed pages, IBUF_BITMAP_FREE is unaffected by reorganization.
[in] | recovery | True if called in recovery: locks should not be updated, i.e., there cannot exist locks on the page, and a hash index should not be dropped: it cannot exist. |
[in] | z_level | Compression level to be used if dealing with compressed page. |
[in,out] | cursor | Page cursor. |
[in] | index | The index tree of the page. |
[in,out] | mtr | Mini-transaction |
true | if the operation was successful |
false | if it is a compressed page, and re-compression failed |
rec_t * btr_page_split_and_insert | ( | uint32_t | flags, |
btr_cur_t * | cursor, | ||
ulint ** | offsets, | ||
mem_heap_t ** | heap, | ||
const dtuple_t * | tuple, | ||
mtr_t * | mtr | ||
) |
Splits an index page to halves and inserts the tuple.
It is assumed that mtr holds an x-latch to the index tree. NOTE: the tree x-latch is released within this function! NOTE that the operation of this function must always succeed, we cannot reverse it: therefore enough free disk space (2 pages) must be guaranteed to be available before this function is called.
flags | in: undo logging and locking flags |
cursor | in: cursor at which to insert; when the function returns, the cursor is positioned on the predecessor of the inserted record |
offsets | out: offsets on inserted record |
heap | in/out: pointer to memory heap, or NULL |
tuple | in: tuple to insert |
mtr | in: mtr |
|
static |
Determine if a tuple is smaller than any record on the page.
cursor | in: b-tree cursor |
tuple | in: tuple to consider |
offsets | in/out: temporary storage |
n_uniq | in: number of unique fields in the index page records |
heap | in/out: heap for offsets |
const byte * btr_parse_page_reorganize | ( | const byte * | ptr, |
const byte * | end_ptr, | ||
dict_index_t * | index, | ||
bool | compressed, | ||
buf_block_t * | block, | ||
mtr_t * | mtr | ||
) |
Parses a redo log record of reorganizing a page.
ptr | in: buffer |
end_ptr | in: buffer end |
index | in: record descriptor |
compressed | in: true if compressed page |
block | in: page to be reorganized, or NULL |
mtr | in: mtr or NULL |
const byte * btr_parse_set_min_rec_mark | ( | const byte * | ptr, |
const byte * | end_ptr, | ||
ulint | comp, | ||
page_t * | page, | ||
mtr_t * | mtr | ||
) |
Parses the redo log record for setting an index record as the predefined minimum record.
ptr | in: buffer |
end_ptr | in: buffer end |
comp | in: nonzero=compact page format |
page | in: page or NULL |
mtr | in: mtr or NULL |
dberr_t btr_root_adjust_on_import | ( | const dict_index_t * | index | ) |
Checks and adjusts the root node of a tree during IMPORT TABLESPACE.
index | in: index tree |
buf_block_t * btr_root_block_get | ( | const dict_index_t * | index, |
ulint | mode, | ||
mtr_t * | mtr | ||
) |
Gets the root node of a tree and x- or s-latches it.
index | in: index tree |
mode | in: either RW_S_LATCH or RW_X_LATCH |
mtr | in: mtr |
|
static |
Checks a file segment header within a B-tree root page and updates the segment header space id.
seg_header | in/out: segment header |
page_zip | in/out: compressed page, or NULL |
space | in: tablespace identifier |
mtr | in/out: mini-transaction |
page_t * btr_root_get | ( | const dict_index_t * | index, |
mtr_t * | mtr | ||
) |
Gets the root node of a tree and sx-latches it for segment access.
index | in: index tree |
mtr | in: mtr |
rec_t * btr_root_raise_and_insert | ( | uint32_t | flags, |
btr_cur_t * | cursor, | ||
ulint ** | offsets, | ||
mem_heap_t ** | heap, | ||
const dtuple_t * | tuple, | ||
mtr_t * | mtr | ||
) |
Makes tree one level higher by splitting the root, and inserts the tuple.
It is assumed that mtr contains an x-latch on the tree. NOTE that the operation of this function must always succeed, we cannot reverse it: therefore enough free disk space must be guaranteed to be available before this function is called.
flags | in: undo logging and locking flags |
cursor | in: cursor at which to insert: must be on the root page; when the function returns, the cursor is positioned on the predecessor of the inserted record |
offsets | out: offsets on inserted record |
heap | in/out: pointer to memory heap, or NULL |
tuple | in: tuple to insert |
mtr | in: mtr |
|
static |
Create an SDI Index.
[in] | space_id | Tablespace id |
[in,out] | mtr | Mini-transaction |
[in,out] | table | SDI table |
dberr_t btr_sdi_create_index | ( | space_id_t | space_id, |
bool | dict_locked | ||
) |
Creates SDI index and stores the root page numbers in page 1 & 2.
[in] | space_id | tablespace id |
[in] | dict_locked | true if dict_sys mutex is acquired |
Sets a record as the predefined minimum record.
[in,out] | rec | Record |
[in] | mtr | Mini-transaction |
Writes the redo log record for setting an index record as the predefined minimum record.
rec | in: record |
type | in: MLOG_COMP_REC_MIN_MARK or MLOG_REC_MIN_MARK |
mtr | in: mtr |
void btr_truncate | ( | const dict_index_t * | index | ) |
Truncate an index tree.
We just free all except the root. Currently, this function is only specific for clustered indexes and the only caller is DDTableBuffer which manages a table with only a clustered index. It is up to the caller to ensure atomicity and to ensure correct recovery by calling btr_truncate_recover().
[in] | index | clustered index |
void btr_truncate_recover | ( | const dict_index_t * | index | ) |
Recovery function for btr_truncate.
We will check if there is a crash during btr_truncate, if so, do recover it, if not, do nothing.
[in] | index | clustered index |
void btr_unset_min_rec_mark | ( | buf_block_t * | block, |
rec_t * | rec, | ||
mtr_t * | mtr | ||
) |
Removes a record as the predefined minimum record.
[in] | block | buffer block containing the record. |
[in] | rec | the record who info bits will be modified by clearing the REC_INFO_MIN_REC_FLAG bit. |
[in] | mtr | mini transaction context. |
bool btr_validate_index | ( | dict_index_t * | index, |
const trx_t * | trx, | ||
bool | lockout | ||
) |
Checks the consistency of an index tree.
index | in: index |
trx | in: transaction or NULL |
lockout | in: true if X-latch index is intended |
|
static |
Validates index tree level.
[in] | index | index dictionary object. |
[in] | trx | transaction or nullptr |
[in] | level | level number to validate |
[in] | lockout | true if X-latch index is intended |
[in] | index_details | debug only argument to collect index details. |
|
static |
Report an error on one page of an index tree.
index | in: index |
level | in: B-tree level |
block | in: index page |
|
static |
Report an error on two pages of an index tree.
index | in: index |
level | in: B-tree level |
block1 | in: first index page |
block2 | in: second index page |
|
static |
Do an index level validation of spaital index tree.
index | in: index |
trx | in: transaction or NULL |
|
static |
PAGE_INDEX_ID value for freed index B-trees.