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