MySQL 8.1.0
Source Code Documentation
btr0btr.h
Go to the documentation of this file.
1/*****************************************************************************
2
3Copyright (c) 1994, 2023, Oracle and/or its affiliates.
4Copyright (c) 2012, Facebook Inc.
5
6This program is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License, version 2.0, as published by the
8Free Software Foundation.
9
10This program is also distributed with certain software (including but not
11limited to OpenSSL) that is licensed under separate terms, as designated in a
12particular file or component or in included license documentation. The authors
13of MySQL hereby grant you an additional permission to link the program and
14your derivative works with the separately licensed software that they have
15included with MySQL.
16
17This program is distributed in the hope that it will be useful, but WITHOUT
18ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
19FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
20for more details.
21
22You should have received a copy of the GNU General Public License along with
23this program; if not, write to the Free Software Foundation, Inc.,
2451 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
25
26*****************************************************************************/
27
28/** @file include/btr0btr.h
29 The B-tree
30
31 Created 6/2/1994 Heikki Tuuri
32 *******************************************************/
33
34#ifndef btr0btr_h
35#define btr0btr_h
36
37#include "btr0types.h"
38#include "data0data.h"
39#include "dict0dict.h"
40#include "gis0type.h"
41#include "mtr0mtr.h"
42#include "page0cur.h"
43#include "univ.i"
44
45/** Maximum record size which can be stored on a page, without using the
46special big record storage structure */
47#define BTR_PAGE_MAX_REC_SIZE (UNIV_PAGE_SIZE / 2 - 200)
48
49/** @brief Maximum depth of a B-tree in InnoDB.
50
51Note that this isn't a maximum as such; none of the tree operations
52avoid producing trees bigger than this. It is instead a "max depth
53that other code must work with", useful for e.g. fixed-size arrays
54that must store some information about each level in a tree. In other
55words: if a B-tree with bigger depth than this is encountered, it is
56not acceptable for it to lead to mysterious memory corruption, but it
57is acceptable for the program to die with a clear assert failure. */
58constexpr uint32_t BTR_MAX_LEVELS = 100;
59
60/** Latching modes for btr_cur_search_to_nth_level(). */
61enum btr_latch_mode : size_t {
62 /** Search a record on a leaf page and S-latch it. */
64 /** (Prepare to) modify a record on a leaf page and X-latch it. */
66 /** Obtain no latches. */
68 /** Start modifying the entire B-tree. */
70 /** Continue modifying the entire B-tree. */
72 /** Search the previous record. */
74 /** Modify the previous record. */
76 /** Start searching the entire B-tree. */
78 /** Continue searching the entire B-tree. */
80};
81
82/* BTR_INSERT, BTR_DELETE and BTR_DELETE_MARK are mutually exclusive. */
83
84/** If this is ORed to btr_latch_mode, it means that the search tuple
85will be inserted to the index, at the searched position.
86When the record is not in the buffer pool, try to use the insert buffer. */
87constexpr size_t BTR_INSERT = 512;
88
89/** This flag ORed to btr_latch_mode says that we do the search in query
90optimization */
91constexpr size_t BTR_ESTIMATE = 1024;
92
93/** This flag ORed to BTR_INSERT says that we can ignore possible
94UNIQUE definition on secondary indexes when we decide if we can use
95the insert buffer to speed up inserts */
96constexpr size_t BTR_IGNORE_SEC_UNIQUE = 2048;
97
98/** Try to delete mark the record at the searched position using the
99insert/delete buffer when the record is not in the buffer pool. */
100constexpr size_t BTR_DELETE_MARK = 4096;
101
102/** Try to purge the record at the searched position using the insert/delete
103buffer when the record is not in the buffer pool. */
104constexpr size_t BTR_DELETE = 8192;
105
106/** In the case of BTR_SEARCH_LEAF or BTR_MODIFY_LEAF, the caller is
107already holding an S latch on the index tree */
108constexpr size_t BTR_ALREADY_S_LATCHED = 16384;
109
110/** In the case of BTR_MODIFY_TREE, the caller specifies the intention
111to insert record only. It is used to optimize block->lock range.*/
112constexpr size_t BTR_LATCH_FOR_INSERT = 32768;
113
114/** In the case of BTR_MODIFY_TREE, the caller specifies the intention
115to delete record only. It is used to optimize block->lock range.*/
116constexpr size_t BTR_LATCH_FOR_DELETE = 65536;
117
118/** This flag is for undo insert of rtree. For rtree, we need this flag
119to find proper rec to undo insert.*/
120constexpr size_t BTR_RTREE_UNDO_INS = 131072;
121
122/** In the case of BTR_MODIFY_LEAF, the caller intends to allocate or
123free the pages of externally stored fields. */
124constexpr size_t BTR_MODIFY_EXTERNAL = 262144;
125
126/** Try to delete mark the record at the searched position when the
127record is in spatial index */
128constexpr size_t BTR_RTREE_DELETE_MARK = 524288;
129
131 return latch_mode &
136}
137
139 return latch_mode &
141}
142
143/** Report that an index page is corrupted. */
144void btr_corruption_report(const buf_block_t *block, /*!< in: corrupted block */
145 const dict_index_t *index) /*!< in: index tree */
146 UNIV_COLD;
147
148/** Assert that a B-tree page is not corrupted.
149@param block buffer block containing a B-tree page
150@param index the B-tree index */
151inline void btr_assert_not_corrupted(const buf_block_t *block,
152 const dict_index_t *index) {
153 if (page_is_comp(buf_block_get_frame(block)) !=
154 dict_table_is_comp((index)->table)) {
155 btr_corruption_report(block, index);
156 ut_error;
157 }
158}
159
160/** Gets the root node of a tree and sx-latches it for segment access.
161 @return root page, sx-latched */
162page_t *btr_root_get(const dict_index_t *index, /*!< in: index tree */
163 mtr_t *mtr); /*!< in: mtr */
164
165/** Checks and adjusts the root node of a tree during IMPORT TABLESPACE.
166 @return error code, or DB_SUCCESS */
168 const dict_index_t *index); /*!< in: index tree */
169
170/** Gets the height of the B-tree (the level of the root, when the leaf
171 level is assumed to be 0). The caller must hold an S or X latch on
172 the index.
173 @return tree height (level of the root) */
174[[nodiscard]] ulint btr_height_get(dict_index_t *index, /*!< in: index tree */
175 mtr_t *mtr); /*!< in/out: mini-transaction */
176
177#ifndef UNIV_HOTBACKUP
178/** Gets a buffer page and declares its latching order level.
179@param[in] page_id Page id
180@param[in] page_size Page size
181@param[in] mode Latch mode
182@param[in] location Location from where this method is called.
183@param[in] index Index tree, may be NULL if it is not an insert
184 buffer tree
185@param[in,out] mtr Mini-transaction
186@return block */
188 const page_id_t &page_id, const page_size_t &page_size, ulint mode,
189 ut::Location location, IF_DEBUG(const dict_index_t *index, ) mtr_t *mtr);
190
191/** Gets a buffer page and declares its latching order level.
192@param page_id Tablespace/page identifier
193@param page_size Page size
194@param mode Latch mode
195@param[in] location Location from where this method is called.
196@param index Index tree, may be NULL if not the insert buffer tree
197@param mtr Mini-transaction handle
198@return the block descriptor */
199static inline buf_block_t *btr_block_get(const page_id_t &page_id,
200 const page_size_t &page_size,
201 ulint mode, ut::Location location,
202 const dict_index_t *index,
203 mtr_t *mtr) {
204 return btr_block_get_func(page_id, page_size, mode, location,
205 IF_DEBUG(index, ) mtr);
206}
207
208#endif /* !UNIV_HOTBACKUP */
209
210/** Gets the index id field of a page.
211 @return index id */
212[[nodiscard]] static inline space_index_t btr_page_get_index_id(
213 const page_t *page); /*!< in: index page */
214/** Gets the node level field in an index page.
215 @param[in] page index page
216 @return level, leaf level == 0 */
217[[nodiscard]] static inline ulint btr_page_get_level(const page_t *page);
218/** Gets the next index page number.
219@param[in] page Index page.
220@param[in] mtr Mini-transaction handle.
221@return next page number */
222[[nodiscard]] static inline page_no_t btr_page_get_next(const page_t *page,
223 mtr_t *mtr);
224/** Gets the previous index page number.
225@param[in] page Index page.
226@param[in] mtr Mini-transaction handle.
227@return prev page number */
228[[nodiscard]] static inline page_no_t btr_page_get_prev(const page_t *page,
229 mtr_t *mtr);
230
231#ifndef UNIV_HOTBACKUP
232/** Releases the latch on a leaf page and bufferunfixes it.
233@param[in] block buffer block
234@param[in] latch_mode BTR_SEARCH_LEAF or BTR_MODIFY_LEAF
235@param[in] mtr mtr */
236static inline void btr_leaf_page_release(buf_block_t *block, ulint latch_mode,
237 mtr_t *mtr);
238#endif /* !UNIV_HOTBACKUP */
239
240/** Gets the child node file address in a node pointer.
241 NOTE: the offsets array must contain all offsets for the record since
242 we read the last field according to offsets and assume that it contains
243 the child page number. In other words offsets must have been retrieved
244 with rec_get_offsets(n_fields=ULINT_UNDEFINED).
245 @param[in] rec node Pointer record
246 @param[in] offsets Array returned by rec_get_offsets()
247 @return child node address */
248[[nodiscard]] static inline page_no_t btr_node_ptr_get_child_page_no(
249 const rec_t *rec, const ulint *offsets);
250
251/** Returns the child page of a node pointer and sx-latches it.
252@param[in] node_ptr node pointer
253@param[in] index index
254@param[in] offsets array returned by rec_get_offsets()
255@param[in] mtr mtr
256@param[in] type latch type
257@return child page, latched as per the type */
259 const ulint *offsets, mtr_t *mtr,
261
262/** Create the root node for a new index tree.
263@param[in] type Type of the index
264@param[in] space Space where created
265@param[in] index_id Index id
266@param[in] index Index tree
267@param[in,out] mtr Mini-transaction
268@return page number of the created root
269@retval FIL_NULL if did not succeed */
271 dict_index_t *index, mtr_t *mtr);
272
273/** Free a persistent index tree if it exists.
274@param[in] page_id Root page id
275@param[in] page_size Page size
276@param[in] index_id PAGE_INDEX_ID contents
277@param[in,out] mtr Mini-transaction */
278void btr_free_if_exists(const page_id_t &page_id, const page_size_t &page_size,
279 space_index_t index_id, mtr_t *mtr);
280
281/** Free an index tree in a temporary tablespace.
282@param[in] page_id root page id
283@param[in] page_size page size */
284void btr_free(const page_id_t &page_id, const page_size_t &page_size);
285
286/** Truncate an index tree. We just free all except the root.
287Currently, this function is only specific for clustered indexes and the only
288caller is DDTableBuffer which manages a table with only a clustered index.
289It is up to the caller to ensure atomicity and to ensure correct recovery by
290calling btr_truncate_recover().
291@param[in] index clustered index */
292void btr_truncate(const dict_index_t *index);
293
294/** Recovery function for btr_truncate. We will check if there is a
295crash during btr_truncate, if so, do recover it, if not, do nothing.
296@param[in] index clustered index */
297void btr_truncate_recover(const dict_index_t *index);
298
299/** Makes tree one level higher by splitting the root, and inserts
300 the tuple. It is assumed that mtr contains an x-latch on the tree.
301 NOTE that the operation of this function must always succeed,
302 we cannot reverse it: therefore enough free disk space must be
303 guaranteed to be available before this function is called.
304 @return inserted record */
305[[nodiscard]] rec_t *btr_root_raise_and_insert(
306 uint32_t flags, /*!< in: undo logging and locking flags */
307 btr_cur_t *cursor, /*!< in: cursor at which to insert: must be
308 on the root page; when the function returns,
309 the cursor is positioned on the predecessor
310 of the inserted record */
311 ulint **offsets, /*!< out: offsets on inserted record */
312 mem_heap_t **heap, /*!< in/out: pointer to memory heap
313 that can be emptied, or NULL */
314 const dtuple_t *tuple, /*!< in: tuple to insert */
315 mtr_t *mtr); /*!< in: mtr */
316/** Reorganizes an index page.
317
318IMPORTANT: On success, the caller will have to update IBUF_BITMAP_FREE
319if this is a compressed leaf page in a secondary index. This has to
320be done either within the same mini-transaction, or by invoking
321ibuf_reset_free_bits() before mtr_commit(). On uncompressed pages,
322IBUF_BITMAP_FREE is unaffected by reorganization.
323
324@param[in] recovery True if called in recovery: locks should not be updated,
325i.e., there cannot exist locks on the page, and a hash index should not be
326dropped: it cannot exist.
327@param[in] z_level Compression level to be used if dealing with compressed
328page.
329@param[in,out] cursor Page cursor.
330@param[in] index The index tree of the page.
331@param[in,out] mtr Mini-transaction
332@retval true if the operation was successful
333@retval false if it is a compressed page, and re-compression failed */
334[[nodiscard]] bool btr_page_reorganize_low(bool recovery, ulint z_level,
335 page_cur_t *cursor,
336 dict_index_t *index, mtr_t *mtr);
337
338/** Reorganizes an index page.
339
340IMPORTANT: On success, the caller will have to update IBUF_BITMAP_FREE
341if this is a compressed leaf page in a secondary index. This has to
342be done either within the same mini-transaction, or by invoking
343ibuf_reset_free_bits() before mtr_commit(). On uncompressed pages,
344IBUF_BITMAP_FREE is unaffected by reorganization.
345
346@param[in,out] cursor Page cursor
347@param[in] index The index tree of the page
348@param[in,out] mtr Mini-transaction
349@retval true if the operation was successful
350@retval false if it is a compressed page, and recompression failed */
351bool btr_page_reorganize(page_cur_t *cursor, dict_index_t *index, mtr_t *mtr);
352
353/** Decides if the page should be split at the convergence point of
354 inserts converging to left.
355 @return true if split recommended */
356[[nodiscard]] bool btr_page_get_split_rec_to_left(
357 btr_cur_t *cursor, /*!< in: cursor at which to insert */
358 rec_t **split_rec); /*!< out: if split recommended,
359 the first record on upper half page,
360 or NULL if tuple should be first */
361/** Decides if the page should be split at the convergence point of
362 inserts converging to right.
363 @return true if split recommended */
364[[nodiscard]] bool btr_page_get_split_rec_to_right(
365 btr_cur_t *cursor, /*!< in: cursor at which to insert */
366 rec_t **split_rec); /*!< out: if split recommended,
367 the first record on upper half page,
368 or NULL if tuple should be first */
369
370/** Splits an index page to halves and inserts the tuple. It is assumed
371 that mtr holds an x-latch to the index tree. NOTE: the tree x-latch is
372 released within this function! NOTE that the operation of this
373 function must always succeed, we cannot reverse it: therefore enough
374 free disk space (2 pages) must be guaranteed to be available before
375 this function is called.
376
377 @return inserted record */
378[[nodiscard]] rec_t *btr_page_split_and_insert(
379 uint32_t flags, /*!< in: undo logging and locking flags */
380 btr_cur_t *cursor, /*!< in: cursor at which to insert; when the
381 function returns, the cursor is positioned
382 on the predecessor of the inserted record */
383 ulint **offsets, /*!< out: offsets on inserted record */
384 mem_heap_t **heap, /*!< in/out: pointer to memory heap
385 that can be emptied, or NULL */
386 const dtuple_t *tuple, /*!< in: tuple to insert */
387 mtr_t *mtr); /*!< in: mtr */
388/** Inserts a data tuple to a tree on a non-leaf level. It is assumed
389 that mtr holds an x-latch on the tree.
390 @param[in] flags undo logging and locking flags
391 @param[in] index index
392 @param[in] level level, must be > 0
393 @param[in] tuple the record to be inserted
394 @param[in] location location where called
395 @param[in] mtr mtr */
397 ulint level, dtuple_t *tuple,
398 ut::Location location, mtr_t *mtr);
399
400/** Sets a record as the predefined minimum record.
401@param[in,out] rec Record
402@param[in] mtr Mini-transaction
403*/
404void btr_set_min_rec_mark(rec_t *rec, mtr_t *mtr);
405
406/** Deletes on the upper level the node pointer to a page.
407@param[in] index Index tree
408@param[in] block Page whose node pointer is deleted
409@param[in] mtr Mini-transaction
410*/
411void btr_node_ptr_delete(dict_index_t *index, buf_block_t *block, mtr_t *mtr);
412#ifdef UNIV_DEBUG
413/** Asserts that the node pointer to a page is appropriate.
414 @param[in] index index tree
415 @param[in] block index page
416 @param[in] mtr mtr
417 @return true */
418bool btr_check_node_ptr(dict_index_t *index, buf_block_t *block, mtr_t *mtr);
419#endif /* UNIV_DEBUG */
420/** Tries to merge the page first to the left immediate brother if such a
421 brother exists, and the node pointers to the current page and to the brother
422 reside on the same page. If the left brother does not satisfy these
423 conditions, looks at the right brother. If the page is the only one on that
424 level lifts the records of the page to the father page, thus reducing the
425 tree height. It is assumed that mtr holds an x-latch on the tree and on the
426 page. If cursor is on the leaf level, mtr must also hold x-latches to the
427 brothers, if they exist.
428 @param[in,out] cursor cursor on the page to merge or lift; the page must not be
429 empty: when deleting records, use btr_discard_page() if the page would become
430 empty
431 @param[in] adjust true if should adjust the cursor position even if compression
432 occurs.
433 @param[in,out] mtr mini-transaction
434 @return true on success */
435bool btr_compress(btr_cur_t *cursor, bool adjust, mtr_t *mtr);
436/** Discards a page from a B-tree. This is used to remove the last record from
437 a B-tree page: the whole page must be removed at the same time. This cannot
438 be used for the root page, which is allowed to be empty. */
439void btr_discard_page(btr_cur_t *cursor, /*!< in: cursor on the page to
440 discard: not on the root page */
441 mtr_t *mtr); /*!< in: mtr */
442/** Parses the redo log record for setting an index record as the predefined
443 minimum record.
444 @return end of log record or NULL */
445[[nodiscard]] byte *btr_parse_set_min_rec_mark(
446 byte *ptr, /*!< in: buffer */
447 byte *end_ptr, /*!< in: buffer end */
448 ulint comp, /*!< in: nonzero=compact page format */
449 page_t *page, /*!< in: page or NULL */
450 mtr_t *mtr); /*!< in: mtr or NULL */
451/** Parses a redo log record of reorganizing a page.
452 @return end of log record or NULL */
453[[nodiscard]] byte *btr_parse_page_reorganize(
454 byte *ptr, /*!< in: buffer */
455 byte *end_ptr, /*!< in: buffer end */
456 dict_index_t *index, /*!< in: record descriptor */
457 bool compressed, /*!< in: true if compressed page */
458 buf_block_t *block, /*!< in: page to be reorganized, or NULL */
459 mtr_t *mtr); /*!< in: mtr or NULL */
460/** Gets the number of pages in a B-tree.
461 @return number of pages, or ULINT_UNDEFINED if the index is unavailable */
462[[nodiscard]] ulint btr_get_size(
463 dict_index_t *index, /*!< in: index */
464 ulint flag, /*!< in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
465 mtr_t *mtr); /*!< in/out: mini-transaction where index
466 is s-latched */
467
468#ifdef UNIV_DEBUG
469#define btr_page_alloc(index, hint_page_no, file_direction, level, mtr, \
470 init_mtr) \
471 btr_page_alloc_priv(index, hint_page_no, file_direction, level, mtr, \
472 init_mtr, UT_LOCATION_HERE)
473#else /* UNIV_DEBUG */
474#define btr_page_alloc(index, hint_page_no, file_direction, level, mtr, \
475 init_mtr) \
476 btr_page_alloc_priv(index, hint_page_no, file_direction, level, mtr, init_mtr)
477#endif /* UNIV_DEBUG */
478
479/** Allocates a new file page to be used in an index tree. NOTE: we assume
480that the caller has made the reservation for free extents!
481@param[in] index Index tree
482@param[in] hint_page_no Hint of a good page
483@param[in] file_direction Direction where a possible page split is made
484@param[in] level Level where the page is placed in the tree
485@param[in,out] mtr Mini-transaction for the allocation
486@param[in,out] init_mtr Mini-transaction for x-latching and initializing the
487page
488@param[in] loc debug only parameter providing caller source location.
489@retval NULL if no page could be allocated
490@retval block, rw_lock_x_lock_count(&block->lock) == 1 if allocation succeeded
491(init_mtr == mtr, or the page was not previously freed in mtr),
492returned block is not allocated nor initialized otherwise */
493[[nodiscard]] buf_block_t *btr_page_alloc_priv(
494 dict_index_t *index, page_no_t hint_page_no, byte file_direction,
495 ulint level, mtr_t *mtr, mtr_t *init_mtr IF_DEBUG(, const ut::Location &loc)
496
497);
498
499/** Frees a file page used in an index tree. NOTE: cannot free field external
500 storage pages because the page must contain info on its level. */
501void btr_page_free(dict_index_t *index, /*!< in: index tree */
502 buf_block_t *block, /*!< in: block to be freed, x-latched */
503 mtr_t *mtr); /*!< in: mtr */
504/** Creates a new index page (not the root, and also not
505 used in page reorganization). @see btr_page_empty(). */
506void btr_page_create(
507 buf_block_t *block, /*!< in/out: page to be created */
508 page_zip_des_t *page_zip, /*!< in/out: compressed page, or NULL */
509 dict_index_t *index, /*!< in: index */
510 ulint level, /*!< in: the B-tree level of the page */
511 mtr_t *mtr); /*!< in: mtr */
512
513/** Frees a file page used in an index tree. Can be used also to BLOB
514 external storage pages.
515@param[in] index the index to which the page belongs
516@param[in] block block to be freed, x-latched
517@param[in] level page level (ULINT_UNDEFINED=BLOB)
518@param[in] mtr mini transaction context. */
519void btr_page_free_low(dict_index_t *index, buf_block_t *block, ulint level,
520 mtr_t *mtr);
521
522/** Gets the root node of a tree and x- or s-latches it.
523 @return root page, x- or s-latched */
525 const dict_index_t *index, /*!< in: index tree */
526 ulint mode, /*!< in: either RW_S_LATCH
527 or RW_X_LATCH */
528 mtr_t *mtr); /*!< in: mtr */
529
530#ifdef UNIV_BTR_PRINT
531/** Prints size info of a B-tree. */
532void btr_print_size(dict_index_t *index); /*!< in: index tree */
533/** Prints directories and other info of all nodes in the index. */
534void btr_print_index(dict_index_t *index, /*!< in: index */
535 ulint width); /*!< in: print this many entries from start
536 and end */
537#endif /* UNIV_BTR_PRINT */
538/** Checks the size and number of fields in a record based on the definition of
539the index.
540 @return true if ok */
541[[nodiscard]] bool btr_index_rec_validate(
542 const rec_t *rec, /*!< in: index record */
543 const dict_index_t *index, /*!< in: index */
544 bool dump_on_error); /*!< in: true if the function
545 should print hex dump of
546 record and page on error */
547/** Checks the consistency of an index tree.
548 @return true if ok */
549[[nodiscard]] bool btr_validate_index(
550 dict_index_t *index, /*!< in: index */
551 const trx_t *trx, /*!< in: transaction or 0 */
552 bool lockout); /*!< in: true if X-latch index is intended */
553
554/** Creates SDI index and stores the root page numbers in page 1 & 2
555@param[in] space_id tablespace id
556@param[in] dict_locked true if dict_sys mutex is acquired
557@return DB_SUCCESS on success, else DB_ERROR on failure */
558dberr_t btr_sdi_create_index(space_id_t space_id, bool dict_locked);
559
560constexpr uint32_t BTR_N_LEAF_PAGES = 1;
561constexpr uint32_t BTR_TOTAL_SIZE = 2;
562
563#include "btr0btr.ic"
564
565#endif
uint32_t space_id_t
Tablespace identifier.
Definition: api0api.h:50
uint32_t page_no_t
Page number.
Definition: api0api.h:48
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.
Definition: btr0btr.cc:3764
constexpr ulint BTR_LATCH_MODE_WITHOUT_FLAGS(ulint latch_mode)
Definition: btr0btr.h:130
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.
Definition: btr0btr.cc:3826
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.
Definition: btr0btr.cc:831
void btr_truncate(const dict_index_t *index)
Truncate an index tree.
Definition: btr0btr.cc:1046
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.
Definition: btr0btr.cc:1455
static space_index_t btr_page_get_index_id(const page_t *page)
Gets the index id field of a page.
void btr_free(const page_id_t &page_id, const page_size_t &page_size)
Free an index tree in a temporary tablespace.
Definition: btr0btr.cc:1025
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.
Definition: btr0btr.cc:1009
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.
Definition: btr0btr.cc:152
bool btr_page_reorganize(page_cur_t *cursor, dict_index_t *index, mtr_t *mtr)
Reorganizes an index page.
Definition: btr0btr.cc:1369
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.
Definition: btr0btr.h:199
bool btr_validate_index(dict_index_t *index, const trx_t *trx, bool lockout)
Checks the consistency of an index tree.
Definition: btr0btr.cc:4508
btr_latch_mode
Latching modes for btr_cur_search_to_nth_level().
Definition: btr0btr.h:61
@ BTR_CONT_MODIFY_TREE
Continue modifying the entire B-tree.
Definition: btr0btr.h:71
@ BTR_MODIFY_TREE
Start modifying the entire B-tree.
Definition: btr0btr.h:69
@ BTR_MODIFY_LEAF
(Prepare to) modify a record on a leaf page and X-latch it.
Definition: btr0btr.h:65
@ BTR_SEARCH_PREV
Search the previous record.
Definition: btr0btr.h:73
@ BTR_NO_LATCHES
Obtain no latches.
Definition: btr0btr.h:67
@ BTR_SEARCH_LEAF
Search a record on a leaf page and S-latch it.
Definition: btr0btr.h:63
@ BTR_MODIFY_PREV
Modify the previous record.
Definition: btr0btr.h:75
@ BTR_CONT_SEARCH_TREE
Continue searching the entire B-tree.
Definition: btr0btr.h:79
@ BTR_SEARCH_TREE
Start searching the entire B-tree.
Definition: btr0btr.h:77
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,...
Definition: btr0btr.cc:2970
constexpr size_t BTR_IGNORE_SEC_UNIQUE
This flag ORed to BTR_INSERT says that we can ignore possible UNIQUE definition on secondary indexes ...
Definition: btr0btr.h:96
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.
dberr_t btr_root_adjust_on_import(const dict_index_t *index)
Checks and adjusts the root node of a tree during IMPORT TABLESPACE.
Definition: btr0btr.cc:247
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.
Definition: btr0btr.cc:527
ulint BTR_LATCH_MODE_WITHOUT_INTENTION(ulint latch_mode)
Definition: btr0btr.h:138
static page_no_t btr_page_get_prev(const page_t *page, mtr_t *mtr)
Gets the previous index page number.
void btr_truncate_recover(const dict_index_t *index)
Recovery function for btr_truncate.
Definition: btr0btr.cc:1102
byte * btr_parse_set_min_rec_mark(byte *ptr, byte *end_ptr, ulint comp, page_t *page, mtr_t *mtr)
Parses the redo log record for setting an index record as the predefined minimum record.
Definition: btr0btr.cc:2729
constexpr size_t BTR_RTREE_DELETE_MARK
Try to delete mark the record at the searched position when the record is in spatial index.
Definition: btr0btr.h:128
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.
Definition: btr0btr.cc:2278
constexpr size_t BTR_DELETE
Try to purge the record at the searched position using the insert/delete buffer when the record is no...
Definition: btr0btr.h:104
constexpr size_t BTR_LATCH_FOR_DELETE
In the case of BTR_MODIFY_TREE, the caller specifies the intention to delete record only.
Definition: btr0btr.h:116
ulint btr_get_size(dict_index_t *index, ulint flag, mtr_t *mtr)
Gets the number of pages in a B-tree.
Definition: btr0btr.cc:465
constexpr size_t BTR_DELETE_MARK
Try to delete mark the record at the searched position using the insert/delete buffer when the record...
Definition: btr0btr.h:100
constexpr size_t BTR_INSERT
If this is ORed to btr_latch_mode, it means that the search tuple will be inserted to the index,...
Definition: btr0btr.h:87
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.
Definition: btr0btr.cc:615
constexpr size_t BTR_ALREADY_S_LATCHED
In the case of BTR_SEARCH_LEAF or BTR_MODIFY_LEAF, the caller is already holding an S latch on the in...
Definition: btr0btr.h:108
constexpr size_t BTR_ESTIMATE
This flag ORed to btr_latch_mode says that we do the search in query optimization.
Definition: btr0btr.h:91
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.
Definition: btr0btr.cc:2781
static page_no_t btr_page_get_next(const page_t *page, mtr_t *mtr)
Gets the next index page number.
static ulint btr_page_get_level(const page_t *page)
Gets the node level field in an index page.
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.
Definition: btr0btr.cc:1638
byte * btr_parse_page_reorganize(byte *ptr, byte *end_ptr, dict_index_t *index, bool compressed, buf_block_t *block, mtr_t *mtr)
Parses a redo log record of reorganizing a page.
Definition: btr0btr.cc:1375
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.
Definition: btr0btr.cc:1140
constexpr size_t BTR_RTREE_UNDO_INS
This flag is for undo insert of rtree.
Definition: btr0btr.h:120
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:443
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.
Definition: btr0btr.cc:1925
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).
Definition: btr0btr.cc:319
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.
Definition: btr0btr.cc:4684
constexpr uint32_t BTR_MAX_LEVELS
Maximum depth of a B-tree in InnoDB.
Definition: btr0btr.h:58
constexpr size_t BTR_MODIFY_EXTERNAL
In the case of BTR_MODIFY_LEAF, the caller intends to allocate or free the pages of externally stored...
Definition: btr0btr.h:124
constexpr uint32_t BTR_N_LEAF_PAGES
Definition: btr0btr.h:560
constexpr uint32_t BTR_TOTAL_SIZE
Definition: btr0btr.h:561
void btr_set_min_rec_mark(rec_t *rec, mtr_t *mtr)
Sets a record as the predefined minimum record.
Definition: btr0btr.cc:2757
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.
Definition: btr0btr.cc:182
void btr_discard_page(btr_cur_t *cursor, mtr_t *mtr)
Discards a page from a B-tree.
Definition: btr0btr.cc:3505
void btr_corruption_report(const buf_block_t *block, const dict_index_t *index) UNIV_COLD
Report that an index page is corrupted.
Definition: btr0btr.cc:70
constexpr size_t BTR_LATCH_FOR_INSERT
In the case of BTR_MODIFY_TREE, the caller specifies the intention to insert record only.
Definition: btr0btr.h:112
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.
void btr_assert_not_corrupted(const buf_block_t *block, const dict_index_t *index)
Assert that a B-tree page is not corrupted.
Definition: btr0btr.h:151
void btr_page_free(dict_index_t *index, buf_block_t *block, mtr_t *mtr)
Frees a file page used in an index tree.
Definition: btr0btr.cc:573
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.
Definition: btr0btr.cc:1676
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).
Definition: btr0btr.cc:195
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.
The B-tree.
The index tree general types.
static buf_frame_t * buf_block_get_frame(const buf_block_t *block)
Gets a pointer to the memory frame of a block.
Page identifier.
Definition: buf0types.h:206
Page size descriptor.
Definition: page0size.h:49
int page
Definition: ctype-mb.cc:1233
SQL data field and tuple.
dberr_t
Definition: db0err.h:38
Data dictionary system.
static bool dict_table_is_comp(const dict_table_t *table)
Check whether the table uses the compact page format.
ib_id_t space_index_t
Index identifier (unique within a tablespace).
Definition: dict0types.h:219
R-tree header file.
static int flags[50]
Definition: hp_test1.cc:39
static int flag
Definition: hp_test1.cc:39
Mini-transaction buffer.
static PFS_engine_table_share_proxy table
Definition: pfs.cc:60
mode
Definition: file_handle.h:59
The page cursor.
static bool page_is_comp(const page_t *page)
Determine whether the page is in new-style compact format.
byte page_t
Type of the index page.
Definition: page0types.h:151
byte rec_t
Definition: rem0types.h:40
required string type
Definition: replication_group_member_actions.proto:33
The tree cursor: the definition appears here only for the compiler to know struct size!
Definition: btr0cur.h:667
The buffer control block structure.
Definition: buf0buf.h:1689
Data structure for an index.
Definition: dict0mem.h:1045
Structure for an SQL data tuple of fields (logical record)
Definition: data0data.h:681
The info structure stored at the beginning of a heap block.
Definition: mem0mem.h:301
Mini-transaction handle and buffer.
Definition: mtr0mtr.h:176
Index page cursor.
Definition: page0cur.h:310
Compressed page descriptor.
Definition: page0types.h:199
Definition: trx0trx.h:685
Definition: ut0core.h:35
rw_lock_type_t
Definition: sync0rw.h:93
@ RW_SX_LATCH
Definition: sync0rw.h:96
@ RW_NO_LATCH
Definition: sync0rw.h:97
@ RW_X_LATCH
Definition: sync0rw.h:95
@ RW_S_LATCH
Definition: sync0rw.h:94
Version control for database, common definitions, and include files.
#define UNIV_COLD
Definition: univ.i:266
#define IF_DEBUG(...)
Definition: univ.i:673
unsigned long int ulint
Definition: univ.i:405
#define ut_error
Abort execution.
Definition: ut0dbg.h:64