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"

Classes
struct	BFT
	Does a breadth first traversal (BFT) of the B-tree, and invokes the callback for each of the B-tree nodes. More...

struct	BFT::Callback

struct	BFT::Callback::Page_details

Macros
#define	BTR_PAGE_MAX_REC_SIZE (UNIV_PAGE_SIZE / 2 - 200)
	Maximum record size which can be stored on a page, without using the special big record storage structure. More...

#define	btr_page_alloc(index, hint_page_no, file_direction, level, mtr, init_mtr)

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

Enumerations
enum	btr_latch_mode : size_t { BTR_SEARCH_LEAF = RW_S_LATCH , BTR_MODIFY_LEAF = RW_X_LATCH , BTR_NO_LATCHES = RW_NO_LATCH , BTR_MODIFY_TREE = 33 , BTR_CONT_MODIFY_TREE = 34 , BTR_SEARCH_PREV = 35 , BTR_MODIFY_PREV = 36 , BTR_SEARCH_TREE = 37 , BTR_CONT_SEARCH_TREE = 38 }
	Latching modes for btr_cur_search_to_nth_level(). More...

Functions
constexpr ulint	BTR_LATCH_MODE_WITHOUT_FLAGS (ulint latch_mode)

ulint	BTR_LATCH_MODE_WITHOUT_INTENTION (ulint latch_mode)

void	btr_corruption_report (const buf_block_t block, const dict_index_t index) UNIV_COLD
	Report that an index page is corrupted. More...

void	btr_assert_not_corrupted (const buf_block_t block, const dict_index_t index)
	Assert that a B-tree page is not corrupted. More...

page_t *	btr_root_get (const dict_index_t index, mtr_t mtr)
	Gets the root node of a tree and sx-latches it for segment access. More...

dberr_t	btr_root_adjust_on_import (const dict_index_t *index)
	Checks and adjusts the root node of a tree during IMPORT TABLESPACE. More...

ulint	btr_height_get (dict_index_t index, mtr_t mtr)
	Gets the height of the B-tree (the level of the root, when the leaf level is assumed to be 0). More...

static buf_block_t *	btr_block_get_func (const page_id_t &page_id, const page_size_t &page_size, ulint mode, ut::Location location, const dict_index_t index, mtr_t mtr)
	Gets a buffer page and declares its latching order level. More...

static buf_block_t *	btr_block_get (const page_id_t &page_id, const page_size_t &page_size, ulint mode, ut::Location location, const dict_index_t index, mtr_t mtr)
	Gets a buffer page and declares its latching order level. More...

static space_index_t	btr_page_get_index_id (const page_t *page)
	Gets the index id field of a page. More...

static ulint	btr_page_get_level (const page_t *page)
	Gets the node level field in an index page. More...

static page_no_t	btr_page_get_next (const page_t page, mtr_t mtr)
	Gets the next index page number. More...

static page_no_t	btr_page_get_prev (const page_t page, mtr_t mtr)
	Gets the previous index page number. More...

static void	btr_leaf_page_release (buf_block_t block, ulint latch_mode, mtr_t mtr)
	Releases the latch on a leaf page and bufferunfixes it. More...

static page_no_t	btr_node_ptr_get_child_page_no (const rec_t rec, const ulint offsets)
	Gets the child node file address in a node pointer. More...

buf_block_t *	btr_node_ptr_get_child (const rec_t node_ptr, dict_index_t index, const ulint offsets, mtr_t mtr, rw_lock_type_t type=RW_SX_LATCH)
	Returns the child page of a node pointer and sx-latches it. More...

ulint	btr_create (ulint type, space_id_t space, space_index_t index_id, dict_index_t index, mtr_t mtr)
	Create the root node for a new index tree. More...

void	btr_free_if_exists (const page_id_t &page_id, const page_size_t &page_size, space_index_t index_id, mtr_t *mtr)
	Free a persistent index tree if it exists. More...

void	btr_free (const page_id_t &page_id, const page_size_t &page_size)
	Free an index tree in a temporary tablespace. More...

void	btr_truncate (const dict_index_t *index)
	Truncate an index tree. More...

void	btr_truncate_recover (const dict_index_t *index)
	Recovery function for btr_truncate. More...

rec_t *	btr_root_raise_and_insert (uint32_t flags, btr_cur_t cursor, ulint offsets, mem_heap_t heap, const dtuple_t tuple, mtr_t *mtr)
	Makes tree one level higher by splitting the root, and inserts the tuple. More...

bool	btr_page_reorganize_low (bool recovery, ulint z_level, page_cur_t cursor, dict_index_t index, mtr_t *mtr)
	Reorganizes an index page. More...

bool	btr_page_reorganize (page_cur_t cursor, dict_index_t index, mtr_t *mtr)
	Reorganizes an index page. More...

bool	btr_page_get_split_rec_to_left (btr_cur_t cursor, rec_t *split_rec)
	Decides if the page should be split at the convergence point of inserts converging to left. More...

bool	btr_page_get_split_rec_to_right (btr_cur_t cursor, rec_t *split_rec)
	Decides if the page should be split at the convergence point of inserts converging to right. More...

rec_t *	btr_page_split_and_insert (uint32_t flags, btr_cur_t cursor, ulint offsets, mem_heap_t heap, const dtuple_t tuple, mtr_t *mtr)
	Splits an index page to halves and inserts the tuple. More...

void	btr_insert_on_non_leaf_level (uint32_t flags, dict_index_t index, ulint level, dtuple_t tuple, ut::Location location, mtr_t *mtr)
	Inserts a data tuple to a tree on a non-leaf level. More...

void	btr_set_min_rec_mark (rec_t rec, mtr_t mtr)
	Sets a record as the predefined minimum record. More...

void	btr_unset_min_rec_mark (buf_block_t block, rec_t rec, mtr_t *mtr)
	Removes a record as the predefined minimum record. More...

void	btr_node_ptr_delete (dict_index_t index, buf_block_t block, mtr_t *mtr)
	Deletes on the upper level the node pointer to a page. More...

bool	btr_check_node_ptr (dict_index_t index, buf_block_t block, mtr_t *mtr)
	Asserts that the node pointer to a page is appropriate. More...

bool	btr_compress (btr_cur_t cursor, bool adjust, mtr_t mtr)
	Tries to merge the page first to the left immediate brother if such a brother exists, and the node pointers to the current page and to the brother reside on the same page. More...

void	btr_discard_page (btr_cur_t cursor, mtr_t mtr)
	Discards a page from a B-tree. More...

const byte *	btr_parse_set_min_rec_mark (const byte ptr, const byte end_ptr, ulint comp, page_t page, mtr_t mtr)
	Parses the redo log record for setting an index record as the predefined minimum record. More...

const byte *	btr_parse_page_reorganize (const byte ptr, const byte end_ptr, dict_index_t index, bool compressed, buf_block_t block, mtr_t *mtr)
	Parses a redo log record of reorganizing a page. More...

ulint	btr_get_size (dict_index_t index, ulint flag, mtr_t mtr)
	Gets the number of pages in a B-tree. More...

buf_block_t *	btr_page_alloc_priv (dict_index_t index, page_no_t hint_page_no, byte file_direction, ulint level, mtr_t mtr, mtr_t *init_mtr, const ut::Location &loc)
	Allocates a new file page to be used in an index tree. More...

dberr_t	btr_extent_alloc (const dict_index_t const index, bool is_leaf, Page_range_t &page_range, mtr_t mtr)
	Allocates all pages of one extent to be used in an index tree. More...

void	btr_page_free (dict_index_t index, buf_block_t block, mtr_t *mtr)
	Frees a file page used in an index tree. More...

void	btr_page_create (buf_block_t block, page_zip_des_t page_zip, dict_index_t index, ulint level, mtr_t mtr)
	Creates a new index page (not the root, and also not used in page reorganization). More...

void	btr_page_free_low (dict_index_t index, buf_block_t block, ulint level, mtr_t *mtr)
	Frees a file page used in an index tree. More...

buf_block_t *	btr_root_block_get (const dict_index_t index, ulint mode, mtr_t mtr)
	Gets the root node of a tree and x- or s-latches it. More...

void	btr_print_size (dict_index_t *index)
	Prints size info of a B-tree. More...

void	btr_print_index (dict_index_t *index, ulint width)
	Prints directories and other info of all nodes in the index. More...

bool	btr_index_rec_validate (const rec_t rec, const dict_index_t index, bool dump_on_error)
	Checks the size and number of fields in a record based on the definition of the index. More...

bool	btr_validate_index (dict_index_t index, const trx_t trx, bool lockout)
	Checks the consistency of an index tree. More...

dberr_t	btr_sdi_create_index (space_id_t space_id, bool dict_locked)
	Creates SDI index and stores the root page numbers in page 1 & 2. More...

bool	btr_is_index_empty (const dict_index_t *index)
	Check if the given index is empty. More...

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

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

Variables
constexpr uint32_t	BTR_MAX_LEVELS = 100
	Maximum depth of a B-tree in InnoDB. More...

constexpr size_t	BTR_INSERT = 512
	If this is ORed to btr_latch_mode, it means that the search tuple will be inserted to the index, at the searched position. More...

constexpr size_t	BTR_ESTIMATE = 1024
	This flag ORed to btr_latch_mode says that we do the search in query optimization. More...

constexpr size_t	BTR_IGNORE_SEC_UNIQUE = 2048
	This flag ORed to BTR_INSERT says that we can ignore possible UNIQUE definition on secondary indexes when we decide if we can use the insert buffer to speed up inserts. More...

constexpr size_t	BTR_DELETE_MARK = 4096
	Try to delete mark the record at the searched position using the insert/delete buffer when the record is not in the buffer pool. More...

constexpr size_t	BTR_DELETE = 8192
	Try to purge the record at the searched position using the insert/delete buffer when the record is not in the buffer pool. More...

constexpr size_t	BTR_ALREADY_S_LATCHED = 16384
	In the case of BTR_SEARCH_LEAF or BTR_MODIFY_LEAF, the caller is already holding an S latch on the index tree. More...

constexpr size_t	BTR_LATCH_FOR_INSERT = 32768
	In the case of BTR_MODIFY_TREE, the caller specifies the intention to insert record only. More...

constexpr size_t	BTR_LATCH_FOR_DELETE = 65536
	In the case of BTR_MODIFY_TREE, the caller specifies the intention to delete record only. More...

constexpr size_t	BTR_RTREE_UNDO_INS = 131072
	This flag is for undo insert of rtree. More...

constexpr size_t	BTR_MODIFY_EXTERNAL = 262144
	In the case of BTR_MODIFY_LEAF, the caller intends to allocate or free the pages of externally stored fields. More...

constexpr size_t	BTR_RTREE_DELETE_MARK = 524288
	Try to delete mark the record at the searched position when the record is in spatial index. More...

constexpr uint32_t	BTR_N_LEAF_PAGES = 1

constexpr uint32_t	BTR_TOTAL_SIZE = 2

constexpr uint32_t	BTR_MAX_NODE_LEVEL = 45
	NOTE - Changing this from the original number of 50 to 45 as insert_debug.test was failing in ASAN build because of a stack overflow issue. More...

Detailed Description

The B-tree.

Created 6/2/1994 Heikki Tuuri

Macro Definition Documentation

◆ btr_page_alloc

#define btr_page_alloc	(	index,
		hint_page_no,
		file_direction,
		level,
		mtr,
		init_mtr
	)

Value:

btr_page_alloc_priv(index, hint_page_no, file_direction, level, mtr, \

init_mtr, UT_LOCATION_HERE)

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.

Definition: btr0btr.cc:470

UT_LOCATION_HERE

#define UT_LOCATION_HERE

Definition: ut0core.h:73

◆ BTR_PAGE_MAX_REC_SIZE

#define BTR_PAGE_MAX_REC_SIZE (UNIV_PAGE_SIZE / 2 - 200)

Maximum record size which can be stored on a page, without using the special big record storage structure.

Typedef Documentation

◆ Page_range_t

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

Enumeration Type Documentation

◆ btr_latch_mode

enum btr_latch_mode : size_t

Latching modes for btr_cur_search_to_nth_level().

Enumerator
BTR_SEARCH_LEAF	Search a record on a leaf page and S-latch it.
BTR_MODIFY_LEAF	(Prepare to) modify a record on a leaf page and X-latch it.
BTR_NO_LATCHES	Obtain no latches.
BTR_MODIFY_TREE	Start modifying the entire B-tree.
BTR_CONT_MODIFY_TREE	Continue modifying the entire B-tree.
BTR_SEARCH_PREV	Search the previous record.
BTR_MODIFY_PREV	Modify the previous record.
BTR_SEARCH_TREE	Start searching the entire B-tree.
BTR_CONT_SEARCH_TREE	Continue searching the entire B-tree.

Function Documentation

◆ btr_assert_not_corrupted()

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

inline

Assert that a B-tree page is not corrupted.

Parameters

block	buffer block containing a B-tree page
index	the B-tree index

◆ btr_block_get()

static buf_block_t * btr_block_get	(	const page_id_t &	page_id,
		const page_size_t &	page_size,
		ulint	mode,
		ut::Location	location,
		const dict_index_t *	index,
		mtr_t *	mtr
	)

inlinestatic

Gets a buffer page and declares its latching order level.

Parameters

	page_id	Tablespace/page identifier
	page_size	Page size
	mode	Latch mode
[in]	location	Location from where this method is called.
	index	Index tree, may be NULL if not the insert buffer tree
	mtr	Mini-transaction handle

Returns: the block descriptor

◆ btr_block_get_func()

static buf_block_t * btr_block_get_func	(	const page_id_t &	page_id,
		const page_size_t &	page_size,
		ulint	mode,
		ut::Location	location,
		const dict_index_t *	index,
		mtr_t *	mtr
	)

inlinestatic

Gets a buffer page and declares its latching order level.

Parameters

[in]	page_id	Page id
[in]	page_size	Page size
[in]	mode	Latch mode
[in]	location	Location from where this method is called.
[in]	index	Index tree, may be NULL if it is not an insert buffer tree
[in,out]	mtr	Mini-transaction

Returns: block

◆ btr_check_node_ptr()

bool btr_check_node_ptr	(	dict_index_t *	index,
		buf_block_t *	block,
		mtr_t *	mtr
	)

Asserts that the node pointer to a page is appropriate.

Parameters

[in]	index	index tree
[in]	block	index page
[in]	mtr	mtr

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

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

block	in: corrupted block
index	in: 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]	type	Type of the index
[in]	space	Space where created
[in]	index_id	Index id
[in]	index	Index tree
[in,out]	mtr	Mini-transaction

Returns: page number of the created root

Return values

FIL_NULL if 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

cursor	in: cursor on the page to discard: not on the root page
mtr	in: 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]	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.

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_id	root page id
[in]	page_size	page 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_id	Root page id
[in]	page_size	Page size
[in]	index_id	PAGE_INDEX_ID contents
[in,out]	mtr	Mini-transaction

◆ btr_get_size()

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

Gets the number of pages in a B-tree.

Returns: number of pages, or ULINT_UNDEFINED if the index is unavailable in/out: mini-transaction where index is s-latched; number of pages, or ULINT_UNDEFINED if the index is unavailable

Parameters

index	in: index
flag	in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE
mtr	in/out: mini-transaction where index is s-latched

◆ btr_height_get()

ulint btr_height_get	(	dict_index_t *	index,
		mtr_t *	mtr
	)

Gets the height of the B-tree (the level of the root, when the leaf level is assumed to be 0).

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

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

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

Returns: tree height (level of the root)

Parameters

index	in: index tree
mtr	in/out: mini-transaction

◆ btr_index_rec_validate()

bool btr_index_rec_validate	(	const rec_t *	rec,
		const dict_index_t *	index,
		bool	dump_on_error
	)

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

Returns: true if ok in: true if the function should print hex dump of record and page on error; true if ok

Parameters

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

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

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

Returns: true if index is empty, false otherwise.

◆ BTR_LATCH_MODE_WITHOUT_FLAGS()

constexpr ulint BTR_LATCH_MODE_WITHOUT_FLAGS ( ulint latch_mode )

constexpr

◆ BTR_LATCH_MODE_WITHOUT_INTENTION()

ulint BTR_LATCH_MODE_WITHOUT_INTENTION ( ulint latch_mode )

inline

◆ btr_leaf_page_release()

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

inlinestatic

Releases the latch on a leaf page and bufferunfixes it.

Parameters

[in]	block	buffer block
[in]	latch_mode	BTR_SEARCH_LEAF or BTR_MODIFY_LEAF
[in]	mtr	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]	index	Index tree
[in]	block	Page whose node pointer is deleted
[in]	mtr	Mini-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_ptr	node pointer
[in]	index	index
[in]	offsets	array returned by rec_get_offsets()
[in]	mtr	mtr
[in]	type	latch type

Returns: child page, latched as per the type

◆ btr_node_ptr_get_child_page_no()

static page_no_t btr_node_ptr_get_child_page_no	(	const rec_t *	rec,
		const ulint *	offsets
	)

inlinestatic

Gets the child node file address in a node pointer.

NOTE: the offsets array must contain all offsets for the record since we read the last field according to offsets and assume that it contains the child page number. In other words offsets must have been retrieved with rec_get_offsets(n_fields=ULINT_UNDEFINED).

Parameters

[in]	rec	node Pointer record
[in]	offsets	Array returned by rec_get_offsets()

Returns: child node address

◆ btr_page_alloc_priv()

buf_block_t * btr_page_alloc_priv	(	dict_index_t *	index,
		page_no_t	hint_page_no,
		byte	file_direction,
		ulint	level,
		mtr_t *	mtr,
		mtr_t *	init_mtr,
		const ut::Location &	loc
	)

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

NOTE: we assume that the caller has made the reservation for free extents!

Parameters

[in]	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.

Return values

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

◆ 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

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

◆ 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

index	in: index tree
block	in: block to be freed, x-latched
mtr	in: 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]	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.

◆ btr_page_get_index_id()

static space_index_t btr_page_get_index_id ( const page_t * page )

inlinestatic

Gets the index id field of a page.

Returns: index id in: index page

◆ btr_page_get_level()

static ulint btr_page_get_level ( const page_t * page )

inlinestatic

Gets the node level field in an index page.

Parameters

[in] page index page

Returns: level, leaf level == 0

◆ btr_page_get_next()

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

inlinestatic

Gets the next index page number.

Parameters

[in]	page	Index page.
[in]	mtr	Mini-transaction handle.

Returns: next page number

◆ btr_page_get_prev()

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

inlinestatic

Gets the previous index page number.

Parameters

[in]	page	Index page.
[in]	mtr	Mini-transaction handle.

Returns: prev page number

◆ btr_page_get_split_rec_to_left()

bool btr_page_get_split_rec_to_left	(	btr_cur_t *	cursor,
		rec_t **	split_rec
	)

Decides if the page should be split at the convergence point of inserts converging to left.

Returns: true if split recommended out: if split recommended, the first record on upper half page, or NULL if tuple should be first

Decides if the page should be split at the convergence point of inserts converging to left.

Returns: true if split recommended

Parameters

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

◆ btr_page_get_split_rec_to_right()

bool btr_page_get_split_rec_to_right	(	btr_cur_t *	cursor,
		rec_t **	split_rec
	)

Decides if the page should be split at the convergence point of inserts converging to right.

Returns: true if split recommended out: if split recommended, the first record on upper half page, or NULL if tuple should be first

Decides if the page should be split at the convergence point of inserts converging to right.

Returns: true if split recommended

Parameters

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

◆ 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]	cursor	Page cursor
[in]	index	The index tree of the page
[in,out]	mtr	Mini-transaction

Return values

true	if the operation was successful
false	if it is a compressed page, and recompression failed

◆ btr_page_reorganize_low()

bool btr_page_reorganize_low	(	bool	recovery,
		ulint	z_level,
		page_cur_t *	cursor,
		dict_index_t *	index,
		mtr_t *	mtr
	)

Reorganizes an index page.

IMPORTANT: On success, the caller will have to update IBUF_BITMAP_FREE if this is a compressed leaf page in a secondary index. This has to be done either within the same mini-transaction, or by invoking ibuf_reset_free_bits() before mtr_commit(). On uncompressed pages, IBUF_BITMAP_FREE is unaffected by reorganization.

Parameters

[in]	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

Return values

true	if the operation was successful
false	if it is a compressed page, and re-compression failed

◆ btr_page_split_and_insert()

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

Splits an index page to halves and inserts the tuple.

It is assumed that mtr holds an x-latch to the index tree. NOTE: the tree x-latch is released within this function! NOTE that the operation of this function must always succeed, we cannot reverse it: therefore enough free disk space (2 pages) must be guaranteed to be available before this function is called.

Returns: inserted record in: mtr

It is assumed that mtr holds an x-latch to the index tree. NOTE: the tree x-latch is released within this function! NOTE that the operation of this function must always succeed, we cannot reverse it: therefore enough free disk space (2 pages) must be guaranteed to be available before this function is called.

Returns: inserted record

Parameters

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

◆ btr_parse_page_reorganize()

const byte * btr_parse_page_reorganize	(	const byte *	ptr,
		const byte *	end_ptr,
		dict_index_t *	index,
		bool	compressed,
		buf_block_t *	block,
		mtr_t *	mtr
	)

Parses a redo log record of reorganizing a page.

Returns: end of log record or NULL in: mtr or NULL; end of log record or NULL

Parameters

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

◆ btr_parse_set_min_rec_mark()

const byte * btr_parse_set_min_rec_mark	(	const byte *	ptr,
		const byte *	end_ptr,
		ulint	comp,
		page_t *	page,
		mtr_t *	mtr
	)

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

Returns: end of log record or NULL in: mtr or NULL; end of log record or NULL

Parameters

ptr	in: buffer
end_ptr	in: buffer end
comp	in: nonzero=compact page format
page	in: page or NULL
mtr	in: mtr or NULL

◆ btr_print_index()

void btr_print_index	(	dict_index_t *	index,
		ulint	width
	)

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

Parameters

[in]	index	the index to be printed.
[in]	width	number of entries to print from start and end.

◆ btr_print_size()

void btr_print_size ( dict_index_t * index )

Prints size info of a B-tree.

in: index tree

◆ btr_root_adjust_on_import()

dberr_t btr_root_adjust_on_import ( const dict_index_t * index )

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

Returns: error code, or DB_SUCCESS in: index tree; error code, or DB_SUCCESS

Parameters

index in: 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

index	in: index tree
mode	in: either RW_S_LATCH or RW_X_LATCH
mtr	in: 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

index	in: index tree
mtr	in: mtr

◆ btr_root_raise_and_insert()

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

Makes tree one level higher by splitting the root, and inserts the tuple.

It is assumed that mtr contains an x-latch on the tree. NOTE that the operation of this function must always succeed, we cannot reverse it: therefore enough free disk space must be guaranteed to be available before this function is called.

Returns: inserted record in: mtr

It is assumed that mtr contains an x-latch on the tree. NOTE that the operation of this function must always succeed, we cannot reverse it: therefore enough free disk space must be guaranteed to be available before this function is called.

Returns: inserted record

Parameters

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

◆ 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_id	tablespace id
[in]	dict_locked	true 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]	rec	Record
[in]	mtr	Mini-transaction

◆ btr_truncate()

void btr_truncate ( const dict_index_t * index )

Truncate an index tree.

We just free all except the root. Currently, this function is only specific for clustered indexes and the only caller is DDTableBuffer which manages a table with only a clustered index. It is up to the caller to ensure atomicity and to ensure correct recovery by calling btr_truncate_recover().

Parameters

[in] index clustered 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] index clustered 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]	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.

◆ btr_validate_index()

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

Checks the consistency of an index tree.

Returns: true if ok in: true if X-latch index is intended; true if ok

Parameters

index	in: index
trx	in: transaction or NULL
lockout	in: true if X-latch index is intended

◆ operator<<() [1/2]

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

inline

◆ operator<<() [2/2]

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

inline

Variable Documentation

◆ BTR_ALREADY_S_LATCHED

constexpr size_t BTR_ALREADY_S_LATCHED = 16384

constexpr

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

◆ BTR_DELETE

constexpr size_t BTR_DELETE = 8192

constexpr

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

◆ BTR_DELETE_MARK

constexpr size_t BTR_DELETE_MARK = 4096

constexpr

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

◆ BTR_ESTIMATE

constexpr size_t BTR_ESTIMATE = 1024

constexpr

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

◆ BTR_IGNORE_SEC_UNIQUE

constexpr size_t BTR_IGNORE_SEC_UNIQUE = 2048

constexpr

This flag ORed to BTR_INSERT says that we can ignore possible UNIQUE definition on secondary indexes when we decide if we can use the insert buffer to speed up inserts.

◆ BTR_INSERT

constexpr size_t BTR_INSERT = 512

constexpr

If this is ORed to btr_latch_mode, it means that the search tuple will be inserted to the index, at the searched position.

When the record is not in the buffer pool, try to use the insert buffer.

◆ BTR_LATCH_FOR_DELETE

constexpr size_t BTR_LATCH_FOR_DELETE = 65536

constexpr

In the case of BTR_MODIFY_TREE, the caller specifies the intention to delete record only.

It is used to optimize block->lock range.

◆ BTR_LATCH_FOR_INSERT

constexpr size_t BTR_LATCH_FOR_INSERT = 32768

constexpr

In the case of BTR_MODIFY_TREE, the caller specifies the intention to insert record only.

It is used to optimize block->lock range.

◆ BTR_MAX_LEVELS

constexpr uint32_t BTR_MAX_LEVELS = 100

constexpr

Maximum depth of a B-tree in InnoDB.

Note that this isn't a maximum as such; none of the tree operations avoid producing trees bigger than this. It is instead a "max depth that other code must work with", useful for e.g. fixed-size arrays that must store some information about each level in a tree. In other words: if a B-tree with bigger depth than this is encountered, it is not acceptable for it to lead to mysterious memory corruption, but it is acceptable for the program to die with a clear assert failure.

◆ BTR_MAX_NODE_LEVEL

constexpr uint32_t BTR_MAX_NODE_LEVEL = 45

constexpr

NOTE - Changing this from the original number of 50 to 45 as insert_debug.test was failing in ASAN build because of a stack overflow issue.

It was found that rtr_info_t was taking up a lot of stack space in the function btr_insert_on_non_leaf_level_func which is part of the recursive stack trace. Maximum B-tree page level (not really a hard limit). Used in debug assertions in btr_page_set_level and btr_page_get_level

◆ BTR_MODIFY_EXTERNAL

constexpr size_t BTR_MODIFY_EXTERNAL = 262144

constexpr

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

◆ BTR_N_LEAF_PAGES

constexpr uint32_t BTR_N_LEAF_PAGES = 1

constexpr

◆ BTR_RTREE_DELETE_MARK

constexpr size_t BTR_RTREE_DELETE_MARK = 524288

constexpr

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

◆ BTR_RTREE_UNDO_INS

constexpr size_t BTR_RTREE_UNDO_INS = 131072

constexpr

This flag is for undo insert of rtree.

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

◆ BTR_TOTAL_SIZE

constexpr uint32_t BTR_TOTAL_SIZE = 2

constexpr

Classes

Macros

Typedefs

Enumerations

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ btr_page_alloc

◆ BTR_PAGE_MAX_REC_SIZE

Typedef Documentation

◆ Page_range_t

Enumeration Type Documentation

◆ btr_latch_mode

Function Documentation

◆ btr_assert_not_corrupted()

◆ btr_block_get()

◆ btr_block_get_func()

◆ btr_check_node_ptr()

◆ btr_compress()

◆ btr_corruption_report()

◆ btr_create()

◆ btr_discard_page()

◆ btr_extent_alloc()

◆ btr_free()

◆ btr_free_if_exists()

◆ btr_get_size()

◆ btr_height_get()

◆ btr_index_rec_validate()

◆ btr_insert_on_non_leaf_level()

◆ btr_is_index_empty()

◆ BTR_LATCH_MODE_WITHOUT_FLAGS()

◆ BTR_LATCH_MODE_WITHOUT_INTENTION()

◆ btr_leaf_page_release()

◆ btr_node_ptr_delete()

◆ btr_node_ptr_get_child()

◆ btr_node_ptr_get_child_page_no()

◆ btr_page_alloc_priv()

◆ btr_page_create()

◆ btr_page_free()

◆ btr_page_free_low()

◆ btr_page_get_index_id()

◆ btr_page_get_level()

◆ btr_page_get_next()

◆ btr_page_get_prev()

◆ btr_page_get_split_rec_to_left()

◆ btr_page_get_split_rec_to_right()

◆ btr_page_reorganize()

◆ btr_page_reorganize_low()

◆ btr_page_split_and_insert()

◆ btr_parse_page_reorganize()

◆ btr_parse_set_min_rec_mark()

◆ btr_print_index()

◆ btr_print_size()

◆ btr_root_adjust_on_import()

◆ btr_root_block_get()

◆ btr_root_get()

◆ btr_root_raise_and_insert()

◆ btr_sdi_create_index()

◆ btr_set_min_rec_mark()

◆ btr_truncate()

◆ btr_truncate_recover()

◆ btr_unset_min_rec_mark()

◆ btr_validate_index()

◆ operator<<() [1/2]

◆ operator<<() [2/2]

Variable Documentation

◆ BTR_ALREADY_S_LATCHED

◆ BTR_DELETE

◆ BTR_DELETE_MARK

◆ BTR_ESTIMATE

◆ BTR_IGNORE_SEC_UNIQUE

◆ BTR_INSERT

◆ BTR_LATCH_FOR_DELETE

◆ BTR_LATCH_FOR_INSERT

◆ BTR_MAX_LEVELS

◆ BTR_MAX_NODE_LEVEL

◆ BTR_MODIFY_EXTERNAL

◆ BTR_N_LEAF_PAGES

◆ BTR_RTREE_DELETE_MARK