MySQL  8.0.19
Source Code Documentation
btr0btr.h
Go to the documentation of this file.
1 /*****************************************************************************
2 
3 Copyright (c) 1994, 2019, 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 @param[in] index index tree, may be NULL if it is not an insert
182  buffer tree
183 @param[in,out] mtr mini-transaction
184 @return block */
185 UNIV_INLINE
187  const page_size_t &page_size, ulint mode,
188  const char *file, ulint line,
189 #ifdef UNIV_DEBUG
190  const dict_index_t *index,
191 #endif /* UNIV_DEBUG */
192  mtr_t *mtr);
193 
194 #ifdef UNIV_DEBUG
195 /** Gets a buffer page and declares its latching order level.
196 @param page_id tablespace/page identifier
197 @param page_size page size
198 @param mode latch mode
199 @param index index tree, may be NULL if not the insert buffer tree
200 @param mtr mini-transaction handle
201 @return the block descriptor */
202 #define btr_block_get(page_id, page_size, mode, index, mtr) \
203  btr_block_get_func(page_id, page_size, mode, __FILE__, __LINE__, index, mtr)
204 #else /* UNIV_DEBUG */
205 /** Gets a buffer page and declares its latching order level.
206 @param page_id tablespace/page identifier
207 @param page_size page size
208 @param mode latch mode
209 @param index index tree, may be NULL if not the insert buffer tree
210 @param mtr mini-transaction handle
211 @return the block descriptor */
212 #define btr_block_get(page_id, page_size, mode, index, mtr) \
213  btr_block_get_func(page_id, page_size, mode, __FILE__, __LINE__, mtr)
214 #endif /* UNIV_DEBUG */
215 /** Gets a buffer page and declares its latching order level.
216 @param page_id tablespace/page identifier
217 @param page_size page size
218 @param mode latch mode
219 @param index index tree, may be NULL if not the insert buffer tree
220 @param mtr mini-transaction handle
221 @return the uncompressed page frame */
222 #define btr_page_get(page_id, page_size, mode, index, mtr) \
223  buf_block_get_frame(btr_block_get(page_id, page_size, mode, index, mtr))
224 /** Gets the index id field of a page.
225  @return index id */
226 UNIV_INLINE
227 space_index_t btr_page_get_index_id(const page_t *page) /*!< in: index page */
228  MY_ATTRIBUTE((warn_unused_result));
229 /** Gets the node level field in an index page.
230  @return level, leaf level == 0 */
231 UNIV_INLINE
232 ulint btr_page_get_level_low(const page_t *page) /*!< in: index page */
233  MY_ATTRIBUTE((warn_unused_result));
234 #define btr_page_get_level(page, mtr) btr_page_get_level_low(page)
235 /** Gets the next index page number.
236  @return next page number */
237 UNIV_INLINE
238 page_no_t btr_page_get_next(const page_t *page, /*!< in: index page */
239  mtr_t *mtr) /*!< in: mini-transaction handle */
240  MY_ATTRIBUTE((warn_unused_result));
241 /** Gets the previous index page number.
242  @return prev page number */
243 UNIV_INLINE
244 page_no_t btr_page_get_prev(const page_t *page, /*!< in: index page */
245  mtr_t *mtr) /*!< in: mini-transaction handle */
246  MY_ATTRIBUTE((warn_unused_result));
247 
248 /** Releases the latch on a leaf page and bufferunfixes it.
249 @param[in] block buffer block
250 @param[in] latch_mode BTR_SEARCH_LEAF or BTR_MODIFY_LEAF
251 @param[in] mtr mtr */
252 UNIV_INLINE
253 void btr_leaf_page_release(buf_block_t *block, ulint latch_mode, mtr_t *mtr);
254 
255 /** Gets the child node file address in a node pointer.
256  NOTE: the offsets array must contain all offsets for the record since
257  we read the last field according to offsets and assume that it contains
258  the child page number. In other words offsets must have been retrieved
259  with rec_get_offsets(n_fields=ULINT_UNDEFINED).
260  @return child node address */
261 UNIV_INLINE
263  const rec_t *rec, /*!< in: node pointer record */
264  const ulint *offsets) /*!< in: array returned by rec_get_offsets() */
265  MY_ATTRIBUTE((warn_unused_result));
266 
267 /** Returns the child page of a node pointer and sx-latches it.
268 @param[in] node_ptr node pointer
269 @param[in] index index
270 @param[in] offsets array returned by rec_get_offsets()
271 @param[in] mtr mtr
272 @return child page, sx-latched */
274  const ulint *offsets, mtr_t *mtr);
275 
276 /** Create the root node for a new index tree.
277 @param[in] type type of the index
278 @param[in] space space where created
279 @param[in] page_size page size
280 @param[in] index_id index id
281 @param[in] index index tree
282 @param[in,out] mtr mini-transaction
283 @return page number of the created root
284 @retval FIL_NULL if did not succeed */
285 ulint btr_create(ulint type, space_id_t space, const page_size_t &page_size,
286  space_index_t index_id, dict_index_t *index, mtr_t *mtr);
287 
288 /** Free a persistent index tree if it exists.
289 @param[in] page_id root page id
290 @param[in] page_size page size
291 @param[in] index_id PAGE_INDEX_ID contents
292 @param[in,out] mtr mini-transaction */
293 void btr_free_if_exists(const page_id_t &page_id, const page_size_t &page_size,
294  space_index_t index_id, mtr_t *mtr);
295 
296 /** Free an index tree in a temporary tablespace.
297 @param[in] page_id root page id
298 @param[in] page_size page size */
299 void btr_free(const page_id_t &page_id, const page_size_t &page_size);
300 
301 /** Truncate an index tree. We just free all except the root.
302 Currently, this function is only specific for clustered indexes and the only
303 caller is DDTableBuffer which manages a table with only a clustered index.
304 It is up to the caller to ensure atomicity and to implement recovery by
305 calling btr_truncate_recover().
306 @param[in] index clustered index */
307 void btr_truncate(const dict_index_t *index);
308 
309 /** Recovery function for btr_truncate. We will check if there is a
310 crash during btr_truncate, if so, do recover it, if not, do nothing.
311 @param[in] index clustered index */
313 
314 /** Makes tree one level higher by splitting the root, and inserts
315  the tuple. It is assumed that mtr contains an x-latch on the tree.
316  NOTE that the operation of this function must always succeed,
317  we cannot reverse it: therefore enough free disk space must be
318  guaranteed to be available before this function is called.
319  @return inserted record */
321  ulint flags, /*!< in: undo logging and locking flags */
322  btr_cur_t *cursor, /*!< in: cursor at which to insert: must be
323  on the root page; when the function returns,
324  the cursor is positioned on the predecessor
325  of the inserted record */
326  ulint **offsets, /*!< out: offsets on inserted record */
327  mem_heap_t **heap, /*!< in/out: pointer to memory heap
328  that can be emptied, or NULL */
329  const dtuple_t *tuple, /*!< in: tuple to insert */
330  ulint n_ext, /*!< in: number of externally stored columns */
331  mtr_t *mtr) /*!< in: mtr */
332  MY_ATTRIBUTE((warn_unused_result));
333 /** Reorganizes an index page.
334 
335  IMPORTANT: On success, the caller will have to update IBUF_BITMAP_FREE
336  if this is a compressed leaf page in a secondary index. This has to
337  be done either within the same mini-transaction, or by invoking
338  ibuf_reset_free_bits() before mtr_commit(). On uncompressed pages,
339  IBUF_BITMAP_FREE is unaffected by reorganization.
340 
341  @retval true if the operation was successful
342  @retval false if it is a compressed page, and recompression failed */
344  bool recovery, /*!< in: true if called in recovery:
345  locks should not be updated, i.e.,
346  there cannot exist locks on the
347  page, and a hash index should not be
348  dropped: it cannot exist */
349  ulint z_level, /*!< in: compression level to be used
350  if dealing with compressed page */
351  page_cur_t *cursor, /*!< in/out: page cursor */
352  dict_index_t *index, /*!< in: the index tree of the page */
353  mtr_t *mtr) /*!< in/out: mini-transaction */
354  MY_ATTRIBUTE((warn_unused_result));
355 /** Reorganizes an index page.
356 
357  IMPORTANT: On success, the caller will have to update IBUF_BITMAP_FREE
358  if this is a compressed leaf page in a secondary index. This has to
359  be done either within the same mini-transaction, or by invoking
360  ibuf_reset_free_bits() before mtr_commit(). On uncompressed pages,
361  IBUF_BITMAP_FREE is unaffected by reorganization.
362 
363  @retval true if the operation was successful
364  @retval false if it is a compressed page, and recompression failed */
366  page_cur_t *cursor, /*!< in/out: page cursor */
367  dict_index_t *index, /*!< in: the index tree of the page */
368  mtr_t *mtr); /*!< in/out: mini-transaction */
369 /** Decides if the page should be split at the convergence point of
370  inserts converging to left.
371  @return true if split recommended */
373  btr_cur_t *cursor, /*!< in: cursor at which to insert */
374  rec_t **split_rec) /*!< out: if split recommended,
375  the first record on upper half page,
376  or NULL if tuple should be first */
377  MY_ATTRIBUTE((warn_unused_result));
378 /** Decides if the page should be split at the convergence point of
379  inserts converging to right.
380  @return true if split recommended */
382  btr_cur_t *cursor, /*!< in: cursor at which to insert */
383  rec_t **split_rec) /*!< out: if split recommended,
384  the first record on upper half page,
385  or NULL if tuple should be first */
386  MY_ATTRIBUTE((warn_unused_result));
387 
388 /** Splits an index page to halves and inserts the tuple. It is assumed
389  that mtr holds an x-latch to the index tree. NOTE: the tree x-latch is
390  released within this function! NOTE that the operation of this
391  function must always succeed, we cannot reverse it: therefore enough
392  free disk space (2 pages) must be guaranteed to be available before
393  this function is called.
394 
395  @return inserted record */
397  ulint flags, /*!< in: undo logging and locking flags */
398  btr_cur_t *cursor, /*!< in: cursor at which to insert; when the
399  function returns, the cursor is positioned
400  on the predecessor of the inserted record */
401  ulint **offsets, /*!< out: offsets on inserted record */
402  mem_heap_t **heap, /*!< in/out: pointer to memory heap
403  that can be emptied, or NULL */
404  const dtuple_t *tuple, /*!< in: tuple to insert */
405  ulint n_ext, /*!< in: number of externally stored columns */
406  mtr_t *mtr) /*!< in: mtr */
407  MY_ATTRIBUTE((warn_unused_result));
408 /** Inserts a data tuple to a tree on a non-leaf level. It is assumed
409  that mtr holds an x-latch on the tree. */
411  ulint flags, /*!< in: undo logging and locking flags */
412  dict_index_t *index, /*!< in: index */
413  ulint level, /*!< in: level, must be > 0 */
414  dtuple_t *tuple, /*!< in: the record to be inserted */
415  const char *file, /*!< in: file name */
416  ulint line, /*!< in: line where called */
417  mtr_t *mtr); /*!< in: mtr */
418 #define btr_insert_on_non_leaf_level(f, i, l, t, m) \
419  btr_insert_on_non_leaf_level_func(f, i, l, t, __FILE__, __LINE__, m)
420 /** Sets a record as the predefined minimum record. */
421 void btr_set_min_rec_mark(rec_t *rec, /*!< in/out: record */
422  mtr_t *mtr); /*!< in: mtr */
423 /** Deletes on the upper level the node pointer to a page. */
425  dict_index_t *index, /*!< in: index tree */
426  buf_block_t *block, /*!< in: page whose node pointer is deleted */
427  mtr_t *mtr); /*!< in: mtr */
428 #ifdef UNIV_DEBUG
429 /** Checks that the node pointer to a page is appropriate.
430  @return true */
431 ibool btr_check_node_ptr(dict_index_t *index, /*!< in: index tree */
432  buf_block_t *block, /*!< in: index page */
433  mtr_t *mtr) /*!< in: mtr */
434  MY_ATTRIBUTE((warn_unused_result));
435 #endif /* UNIV_DEBUG */
436 /** Tries to merge the page first to the left immediate brother if such a
437  brother exists, and the node pointers to the current page and to the
438  brother reside on the same page. If the left brother does not satisfy these
439  conditions, looks at the right brother. If the page is the only one on that
440  level lifts the records of the page to the father page, thus reducing the
441  tree height. It is assumed that mtr holds an x-latch on the tree and on the
442  page. If cursor is on the leaf level, mtr must also hold x-latches to
443  the brothers, if they exist.
444  @return true on success */
445 ibool btr_compress(
446  btr_cur_t *cursor, /*!< in/out: cursor on the page to merge
447  or lift; the page must not be empty:
448  when deleting records, use btr_discard_page()
449  if the page would become empty */
450  ibool adjust, /*!< in: TRUE if should adjust the
451  cursor position even if compression occurs */
452  mtr_t *mtr); /*!< in/out: mini-transaction */
453 /** Discards a page from a B-tree. This is used to remove the last record from
454  a B-tree page: the whole page must be removed at the same time. This cannot
455  be used for the root page, which is allowed to be empty. */
456 void btr_discard_page(btr_cur_t *cursor, /*!< in: cursor on the page to discard:
457  not on the root page */
458  mtr_t *mtr); /*!< in: mtr */
459 /** Parses the redo log record for setting an index record as the predefined
460  minimum record.
461  @return end of log record or NULL */
463  byte *ptr, /*!< in: buffer */
464  byte *end_ptr, /*!< in: buffer end */
465  ulint comp, /*!< in: nonzero=compact page format */
466  page_t *page, /*!< in: page or NULL */
467  mtr_t *mtr) /*!< in: mtr or NULL */
468  MY_ATTRIBUTE((warn_unused_result));
469 /** Parses a redo log record of reorganizing a page.
470  @return end of log record or NULL */
472  byte *ptr, /*!< in: buffer */
473  byte *end_ptr, /*!< in: buffer end */
474  dict_index_t *index, /*!< in: record descriptor */
475  bool compressed, /*!< in: true if compressed page */
476  buf_block_t *block, /*!< in: page to be reorganized, or NULL */
477  mtr_t *mtr) /*!< in: mtr or NULL */
478  MY_ATTRIBUTE((warn_unused_result));
479 /** Gets the number of pages in a B-tree.
480  @return number of pages, or ULINT_UNDEFINED if the index is unavailable */
481 ulint btr_get_size(dict_index_t *index, /*!< in: index */
482  ulint flag, /*!< in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
483  mtr_t *mtr) /*!< in/out: mini-transaction where index
484  is s-latched */
485  MY_ATTRIBUTE((warn_unused_result));
486 /** Allocates a new file page to be used in an index tree. NOTE: we assume
487  that the caller has made the reservation for free extents!
488  @retval NULL if no page could be allocated
489  @retval block, rw_lock_x_lock_count(&block->lock) == 1 if allocation succeeded
490  (init_mtr == mtr, or the page was not previously freed in mtr)
491  @retval block (not allocated or initialized) otherwise */
493  dict_index_t *index, /*!< in: index tree */
494  page_no_t hint_page_no, /*!< in: hint of a good page */
495  byte file_direction, /*!< in: direction where a possible
496  page split is made */
497  ulint level, /*!< in: level where the page is placed
498  in the tree */
499  mtr_t *mtr, /*!< in/out: mini-transaction
500  for the allocation */
501  mtr_t *init_mtr) /*!< in/out: mini-transaction
502  for x-latching and initializing
503  the page */
504  MY_ATTRIBUTE((warn_unused_result));
505 /** Frees a file page used in an index tree. NOTE: cannot free field external
506  storage pages because the page must contain info on its level. */
507 void btr_page_free(dict_index_t *index, /*!< in: index tree */
508  buf_block_t *block, /*!< in: block to be freed, x-latched */
509  mtr_t *mtr); /*!< in: mtr */
510 /** Creates a new index page (not the root, and also not
511  used in page reorganization). @see btr_page_empty(). */
512 void btr_page_create(
513  buf_block_t *block, /*!< in/out: page to be created */
514  page_zip_des_t *page_zip, /*!< in/out: compressed page, or NULL */
515  dict_index_t *index, /*!< in: index */
516  ulint level, /*!< in: the B-tree level of the page */
517  mtr_t *mtr); /*!< in: mtr */
518 /** Frees a file page used in an index tree. Can be used also to BLOB
519  external storage pages. */
520 void btr_page_free_low(
521  dict_index_t *index, /*!< in: index tree */
522  buf_block_t *block, /*!< in: block to be freed, x-latched */
523  ulint level, /*!< in: page level (ULINT_UNDEFINED=BLOB) */
524  mtr_t *mtr); /*!< in: mtr */
525 /** Gets the root node of a tree and x- or s-latches it.
526  @return root page, x- or s-latched */
528  const dict_index_t *index, /*!< in: index tree */
529  ulint mode, /*!< in: either RW_S_LATCH
530  or RW_X_LATCH */
531  mtr_t *mtr); /*!< in: mtr */
532 
533 #ifdef UNIV_BTR_PRINT
534 /** Prints size info of a B-tree. */
535 void btr_print_size(dict_index_t *index); /*!< in: index tree */
536 /** Prints directories and other info of all nodes in the index. */
537 void btr_print_index(dict_index_t *index, /*!< in: index */
538  ulint width); /*!< in: print this many entries from start
539  and end */
540 #endif /* UNIV_BTR_PRINT */
541 /** Checks the size and number of fields in a record based on the definition of
542  the index.
543  @return true if ok */
544 ibool btr_index_rec_validate(const rec_t *rec, /*!< in: index record */
545  const dict_index_t *index, /*!< in: index */
546  ibool dump_on_error) /*!< in: TRUE if the function
547  should print hex dump of
548  record and page on error */
549  MY_ATTRIBUTE((warn_unused_result));
550 /** Checks the consistency of an index tree.
551  @return true if ok */
552 bool btr_validate_index(
553  dict_index_t *index, /*!< in: index */
554  const trx_t *trx, /*!< in: transaction or 0 */
555  bool lockout) /*!< in: true if X-latch index is intended */
556  MY_ATTRIBUTE((warn_unused_result));
557 
558 /** Creates SDI index and stores the root page numbers in page 1 & 2
559 @param[in] space_id tablespace id
560 @param[in] dict_locked true if dict_sys mutex is acquired
561 @return DB_SUCCESS on success, else DB_ERROR on failure */
562 dberr_t btr_sdi_create_index(space_id_t space_id, bool dict_locked);
563 
564 #define BTR_N_LEAF_PAGES 1
565 #define BTR_TOTAL_SIZE 2
566 
567 #include "btr0btr.ic"
568 
569 #endif
page_no_t
uint32 page_no_t
Page number.
Definition: api0api.h:57
btr_page_get_split_rec_to_left
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
btr_page_reorganize
bool btr_page_reorganize(page_cur_t *cursor, dict_index_t *index, mtr_t *mtr)
Reorganizes an index page.
Definition: btr0btr.cc:1392
dtuple_t
Structure for an SQL data tuple of fields (logical record)
Definition: data0data.h:716
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.
Definition: btr0btr.cc:246
page_t
byte page_t
Type of the index page.
Definition: page0types.h:133
btr_create
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:840
btr_discard_page
void btr_discard_page(btr_cur_t *cursor, mtr_t *mtr)
Discards a page from a B-tree.
Definition: btr0btr.cc:3546
gis0type.h
btr_validate_index
bool btr_validate_index(dict_index_t *index, const trx_t *trx, bool lockout)
Checks the consistency of an index tree.
Definition: btr0btr.cc:4543
BTR_SEARCH_TREE
@ BTR_SEARCH_TREE
Start searching the entire B-tree.
Definition: btr0btr.h:77
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.
Definition: btr0btr.cc:468
dict_index_t
Data structure for an index.
Definition: dict0mem.h:869
btr_latch_mode
btr_latch_mode
Latching modes for btr_cur_search_to_nth_level().
Definition: btr0btr.h:61
mtr_t
Mini-transaction handle and buffer.
Definition: mtr0mtr.h:169
page_cur_t
Index page cursor.
Definition: page0cur.h:315
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.
Definition: btr0btr.cc:1034
BTR_LATCH_FOR_DELETE
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
btr_leaf_page_release
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.
dberr_t
dberr_t
Definition: db0err.h:38
btr_page_get_level_low
UNIV_INLINE ulint btr_page_get_level_low(const page_t *page)
Gets the node level field in an index page.
btr_compress
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,...
Definition: btr0btr.cc:3004
buf_block_t
The buffer control block structure.
Definition: buf0buf.h:1318
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.
Definition: btr0btr.cc:1018
BTR_IGNORE_SEC_UNIQUE
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
rec_t
byte rec_t
Definition: rem0types.h:39
BTR_MODIFY_TREE
@ BTR_MODIFY_TREE
Start modifying the entire B-tree.
Definition: btr0btr.h:69
BTR_CONT_SEARCH_TREE
@ BTR_CONT_SEARCH_TREE
Continue searching the entire B-tree.
Definition: btr0btr.h:79
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.
Definition: btr0btr.cc:582
mem_block_info_t
The info structure stored at the beginning of a heap block.
Definition: mem0mem.h:337
btr_insert_on_non_leaf_level_func
void btr_insert_on_non_leaf_level_func(ulint 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:1946
page_zip_des_t
Compressed page descriptor.
Definition: page0types.h:182
btr_page_split_and_insert
rec_t * btr_page_split_and_insert(ulint flags, btr_cur_t *cursor, ulint **offsets, mem_heap_t **heap, const dtuple_t *tuple, ulint n_ext, mtr_t *mtr)
Splits an index page to halves and inserts the tuple.
Definition: btr0btr.cc:2302
BTR_INSERT
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
BTR_MODIFY_EXTERNAL
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
btr_parse_page_reorganize
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:1402
BTR_ALREADY_S_LATCHED
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
RW_S_LATCH
@ RW_S_LATCH
Definition: sync0rw.h:135
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.
Definition: btr0btr.cc:2780
BTR_CONT_MODIFY_TREE
@ BTR_CONT_MODIFY_TREE
Continue modifying the entire B-tree.
Definition: btr0btr.h:71
BTR_LATCH_FOR_INSERT
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
page_size_t
Page size descriptor.
Definition: page0size.h:50
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.
Definition: btr0btr.cc:181
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).
Definition: btr0btr.cc:194
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)
Returns the child page of a node pointer and sx-latches it.
Definition: btr0btr.cc:625
page0cur.h
btr_page_get_prev
UNIV_INLINE page_no_t btr_page_get_prev(const page_t *page, mtr_t *mtr)
Gets the previous index page number.
RW_X_LATCH
@ RW_X_LATCH
Definition: sync0rw.h:136
BTR_DELETE_MARK
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
page
int page
Definition: ctype-mb.cc:1232
BTR_DELETE
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
BTR_RTREE_UNDO_INS
constexpr size_t BTR_RTREE_UNDO_INS
This flag is for undo insert of rtree.
Definition: btr0btr.h:120
btr0types.h
btr_page_get_split_rec_to_right
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
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.
Definition: btr0btr.cc:2802
BTR_MODIFY_LEAF
@ BTR_MODIFY_LEAF
(Prepare to) modify a record on a leaf page and X-latch it.
Definition: btr0btr.h:65
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.
Definition: btr0btr.cc:532
btr_cur_t
The tree cursor: the definition appears here only for the compiler to know struct size!
Definition: btr0cur.h:692
RW_NO_LATCH
@ RW_NO_LATCH
Definition: sync0rw.h:138
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.
Definition: btr0btr.cc:152
BTR_MODIFY_PREV
@ BTR_MODIFY_PREV
Modify the previous record.
Definition: btr0btr.h:75
btr_check_node_ptr
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:3806
space_index_t
ib_id_t space_index_t
Index identifier (unique within a tablespace).
Definition: dict0types.h:217
btr_page_get_next
UNIV_INLINE page_no_t btr_page_get_next(const page_t *page, mtr_t *mtr)
Gets the next index page number.
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).
Definition: btr0btr.cc:319
page_id_t
Page identifier.
Definition: buf0types.h:153
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.
Definition: btr0btr.cc:4690
btr_parse_set_min_rec_mark
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:2755
BTR_ESTIMATE
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
btr_block_get_func
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.
btr_truncate
void btr_truncate(const dict_index_t *index)
Truncate an index tree.
Definition: btr0btr.cc:1054
BTR_RTREE_DELETE_MARK
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
HttpMethod::type
int type
Definition: http_common.h:411
mtr0mtr.h
space_id_t
uint32 space_id_t
Tablespace identifier.
Definition: api0api.h:59
data0data.h
BTR_SEARCH_PREV
@ BTR_SEARCH_PREV
Search the previous record.
Definition: btr0btr.h:73
BTR_SEARCH_LEAF
@ BTR_SEARCH_LEAF
Search a record on a leaf page and S-latch it.
Definition: btr0btr.h:63
btr_node_ptr_get_child_page_no
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.
btr_truncate_recover
void btr_truncate_recover(const dict_index_t *index)
Recovery function for btr_truncate.
Definition: btr0btr.cc:1109
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.
Definition: btr0btr.cc:1157
btr_page_get_index_id
UNIV_INLINE space_index_t btr_page_get_index_id(const page_t *page)
Gets the index id field of a page.
BTR_NO_LATCHES
@ BTR_NO_LATCHES
Obtain no latches.
Definition: btr0btr.h:67
dict0dict.h
btr_page_alloc
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_index_rec_validate
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:3871
btr_corruption_report
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
index
char * index(const char *, int c)
Definition: mysql.cc:2875
trx_t
Definition: trx0trx.h:780
btr_root_raise_and_insert
rec_t * btr_root_raise_and_insert(ulint flags, btr_cur_t *cursor, ulint **offsets, mem_heap_t **heap, const dtuple_t *tuple, ulint n_ext, mtr_t *mtr)
Makes tree one level higher by splitting the root, and inserts the tuple.
Definition: btr0btr.cc:1484
flag
static int flag
Definition: hp_test1.cc:39
flags
static int flags[50]
Definition: hp_test1.cc:39