1
/******************************************************
4
(c) 1994-1996 Innobase Oy
6
Created 6/2/1994 Heikki Tuuri
7
*******************************************************/
14
#include "dict0dict.h"
15
#include "data0data.h"
19
#include "btr0types.h"
21
/* Maximum record size which can be stored on a page, without using the
22
special big record storage structure */
24
#define BTR_PAGE_MAX_REC_SIZE (UNIV_PAGE_SIZE / 2 - 200)
26
/* Maximum depth of a B-tree in InnoDB. Note that this isn't a maximum as
27
such; none of the tree operations avoid producing trees bigger than this. It
28
is instead a "max depth that other code must work with", useful for e.g.
29
fixed-size arrays that must store some information about each level in a
30
tree. In other words: if a B-tree with bigger depth than this is
31
encountered, it is not acceptable for it to lead to mysterious memory
32
corruption, but it is acceptable for the program to die with a clear assert
34
#define BTR_MAX_LEVELS 100
36
/* Latching modes for btr_cur_search_to_nth_level(). */
37
#define BTR_SEARCH_LEAF RW_S_LATCH
38
#define BTR_MODIFY_LEAF RW_X_LATCH
39
#define BTR_NO_LATCHES RW_NO_LATCH
40
#define BTR_MODIFY_TREE 33
41
#define BTR_CONT_MODIFY_TREE 34
42
#define BTR_SEARCH_PREV 35
43
#define BTR_MODIFY_PREV 36
45
/* If this is ORed to the latch mode, it means that the search tuple will be
46
inserted to the index, at the searched position */
47
#define BTR_INSERT 512
49
/* This flag ORed to latch mode says that we do the search in query
51
#define BTR_ESTIMATE 1024
53
/* This flag ORed to latch mode says that we can ignore possible
54
UNIQUE definition on secondary indexes when we decide if we can use the
55
insert buffer to speed up inserts */
56
#define BTR_IGNORE_SEC_UNIQUE 2048
58
/******************************************************************
59
Gets the root node of a tree and x-latches it. */
64
/* out: root page, x-latched */
65
dict_index_t* index, /* in: index tree */
66
mtr_t* mtr); /* in: mtr */
67
/******************************************************************
68
Gets a buffer page and declares its latching order level. */
73
ulint space, /* in: space id */
74
ulint page_no, /* in: page number */
75
ulint mode, /* in: latch mode */
76
mtr_t* mtr); /* in: mtr */
77
/******************************************************************
78
Gets the index id field of a page. */
81
btr_page_get_index_id(
82
/*==================*/
84
page_t* page); /* in: index page */
85
/************************************************************
86
Gets the node level field in an index page. */
89
btr_page_get_level_low(
90
/*===================*/
91
/* out: level, leaf level == 0 */
92
page_t* page); /* in: index page */
93
/************************************************************
94
Gets the node level field in an index page. */
99
/* out: level, leaf level == 0 */
100
page_t* page, /* in: index page */
101
mtr_t* mtr); /* in: mini-transaction handle */
102
/************************************************************
103
Gets the next index page number. */
108
/* out: next page number */
109
page_t* page, /* in: index page */
110
mtr_t* mtr); /* in: mini-transaction handle */
111
/************************************************************
112
Gets the previous index page number. */
117
/* out: prev page number */
118
page_t* page, /* in: index page */
119
mtr_t* mtr); /* in: mini-transaction handle */
120
/*****************************************************************
121
Gets pointer to the previous user record in the tree. It is assumed
122
that the caller has appropriate latches on the page and its neighbor. */
125
btr_get_prev_user_rec(
126
/*==================*/
127
/* out: previous user record, NULL if there is none */
128
rec_t* rec, /* in: record on leaf level */
129
mtr_t* mtr); /* in: mtr holding a latch on the page, and if
130
needed, also to the previous page */
131
/*****************************************************************
132
Gets pointer to the next user record in the tree. It is assumed
133
that the caller has appropriate latches on the page and its neighbor. */
136
btr_get_next_user_rec(
137
/*==================*/
138
/* out: next user record, NULL if there is none */
139
rec_t* rec, /* in: record on leaf level */
140
mtr_t* mtr); /* in: mtr holding a latch on the page, and if
141
needed, also to the next page */
142
/******************************************************************
143
Releases the latch on a leaf page and bufferunfixes it. */
146
btr_leaf_page_release(
147
/*==================*/
148
page_t* page, /* in: page */
149
ulint latch_mode, /* in: BTR_SEARCH_LEAF or BTR_MODIFY_LEAF */
150
mtr_t* mtr); /* in: mtr */
151
/******************************************************************
152
Gets the child node file address in a node pointer. */
155
btr_node_ptr_get_child_page_no(
156
/*===========================*/
157
/* out: child node address */
158
rec_t* rec, /* in: node pointer record */
159
const ulint* offsets);/* in: array returned by rec_get_offsets() */
160
/****************************************************************
161
Creates the root node for a new index tree. */
166
/* out: page number of the created root, FIL_NULL if
168
ulint type, /* in: type of the index */
169
ulint space, /* in: space where created */
170
dulint index_id,/* in: index id */
171
ulint comp, /* in: nonzero=compact page format */
172
mtr_t* mtr); /* in: mini-transaction handle */
173
/****************************************************************
174
Frees a B-tree except the root page, which MUST be freed after this
175
by calling btr_free_root. */
178
btr_free_but_not_root(
179
/*==================*/
180
ulint space, /* in: space where created */
181
ulint root_page_no); /* in: root page number */
182
/****************************************************************
183
Frees the B-tree root page. Other tree MUST already have been freed. */
188
ulint space, /* in: space where created */
189
ulint root_page_no, /* in: root page number */
190
mtr_t* mtr); /* in: a mini-transaction which has already
192
/*****************************************************************
193
Makes tree one level higher by splitting the root, and inserts
194
the tuple. It is assumed that mtr contains an x-latch on the tree.
195
NOTE that the operation of this function must always succeed,
196
we cannot reverse it: therefore enough free disk space must be
197
guaranteed to be available before this function is called. */
200
btr_root_raise_and_insert(
201
/*======================*/
202
/* out: inserted record */
203
btr_cur_t* cursor, /* in: cursor at which to insert: must be
204
on the root page; when the function returns,
205
the cursor is positioned on the predecessor
206
of the inserted record */
207
dtuple_t* tuple, /* in: tuple to insert */
208
mtr_t* mtr); /* in: mtr */
209
/*****************************************************************
210
Reorganizes an index page. */
215
page_t* page, /* in: page to be reorganized */
216
dict_index_t* index, /* in: record descriptor */
217
mtr_t* mtr); /* in: mtr */
218
/*****************************************************************
219
Decides if the page should be split at the convergence point of
220
inserts converging to left. */
223
btr_page_get_split_rec_to_left(
224
/*===========================*/
225
/* out: TRUE if split recommended */
226
btr_cur_t* cursor, /* in: cursor at which to insert */
227
rec_t** split_rec);/* out: if split recommended,
228
the first record on upper half page,
229
or NULL if tuple should be first */
230
/*****************************************************************
231
Decides if the page should be split at the convergence point of
232
inserts converging to right. */
235
btr_page_get_split_rec_to_right(
236
/*============================*/
237
/* out: TRUE if split recommended */
238
btr_cur_t* cursor, /* in: cursor at which to insert */
239
rec_t** split_rec);/* out: if split recommended,
240
the first record on upper half page,
241
or NULL if tuple should be first */
242
/*****************************************************************
243
Splits an index page to halves and inserts the tuple. It is assumed
244
that mtr holds an x-latch to the index tree. NOTE: the tree x-latch
245
is released within this function! NOTE that the operation of this
246
function must always succeed, we cannot reverse it: therefore
247
enough free disk space must be guaranteed to be available before
248
this function is called. */
251
btr_page_split_and_insert(
252
/*======================*/
253
/* out: inserted record; NOTE: the tree
254
x-latch is released! NOTE: 2 free disk
255
pages must be available! */
256
btr_cur_t* cursor, /* in: cursor at which to insert; when the
257
function returns, the cursor is positioned
258
on the predecessor of the inserted record */
259
dtuple_t* tuple, /* in: tuple to insert */
260
mtr_t* mtr); /* in: mtr */
261
/***********************************************************
262
Inserts a data tuple to a tree on a non-leaf level. It is assumed
263
that mtr holds an x-latch on the tree. */
266
btr_insert_on_non_leaf_level(
267
/*=========================*/
268
dict_index_t* index, /* in: index */
269
ulint level, /* in: level, must be > 0 */
270
dtuple_t* tuple, /* in: the record to be inserted */
271
mtr_t* mtr); /* in: mtr */
272
/********************************************************************
273
Sets a record as the predefined minimum record. */
276
btr_set_min_rec_mark(
277
/*=================*/
278
rec_t* rec, /* in: record */
279
ulint comp, /* in: nonzero=compact page format */
280
mtr_t* mtr); /* in: mtr */
281
/*****************************************************************
282
Deletes on the upper level the node pointer to a page. */
287
dict_index_t* index, /* in: index tree */
288
page_t* page, /* in: page whose node pointer is deleted */
289
mtr_t* mtr); /* in: mtr */
291
/****************************************************************
292
Checks that the node pointer to a page is appropriate. */
298
dict_index_t* index, /* in: index tree */
299
page_t* page, /* in: index page */
300
mtr_t* mtr); /* in: mtr */
301
#endif /* UNIV_DEBUG */
302
/*****************************************************************
303
Tries to merge the page first to the left immediate brother if such a
304
brother exists, and the node pointers to the current page and to the
305
brother reside on the same page. If the left brother does not satisfy these
306
conditions, looks at the right brother. If the page is the only one on that
307
level lifts the records of the page to the father page, thus reducing the
308
tree height. It is assumed that mtr holds an x-latch on the tree and on the
309
page. If cursor is on the leaf level, mtr must also hold x-latches to
310
the brothers, if they exist. NOTE: it is assumed that the caller has reserved
311
enough free extents so that the compression will always succeed if done! */
315
btr_cur_t* cursor, /* in: cursor on the page to merge or lift;
316
the page must not be empty: in record delete
317
use btr_discard_page if the page would become
319
mtr_t* mtr); /* in: mtr */
320
/*****************************************************************
321
Discards a page from a B-tree. This is used to remove the last record from
322
a B-tree page: the whole page must be removed at the same time. This cannot
323
be used for the root page, which is allowed to be empty. */
328
btr_cur_t* cursor, /* in: cursor on the page to discard: not on
330
mtr_t* mtr); /* in: mtr */
331
/********************************************************************
332
Parses the redo log record for setting an index record as the predefined
336
btr_parse_set_min_rec_mark(
337
/*=======================*/
338
/* out: end of log record or NULL */
339
byte* ptr, /* in: buffer */
340
byte* end_ptr,/* in: buffer end */
341
ulint comp, /* in: nonzero=compact page format */
342
page_t* page, /* in: page or NULL */
343
mtr_t* mtr); /* in: mtr or NULL */
344
/***************************************************************
345
Parses a redo log record of reorganizing a page. */
348
btr_parse_page_reorganize(
349
/*======================*/
350
/* out: end of log record or NULL */
351
byte* ptr, /* in: buffer */
352
byte* end_ptr,/* in: buffer end */
353
dict_index_t* index, /* in: record descriptor */
354
page_t* page, /* in: page or NULL */
355
mtr_t* mtr); /* in: mtr or NULL */
356
/******************************************************************
357
Gets the number of pages in a B-tree. */
362
/* out: number of pages */
363
dict_index_t* index, /* in: index */
364
ulint flag); /* in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
365
/******************************************************************
366
Allocates a new file page to be used in an index tree. NOTE: we assume
367
that the caller has made the reservation for free extents! */
372
/* out: new allocated page, x-latched;
373
NULL if out of space */
374
dict_index_t* index, /* in: index tree */
375
ulint hint_page_no, /* in: hint of a good page */
376
byte file_direction, /* in: direction where a possible
377
page split is made */
378
ulint level, /* in: level where the page is placed
380
mtr_t* mtr); /* in: mtr */
381
/******************************************************************
382
Frees a file page used in an index tree. NOTE: cannot free field external
383
storage pages because the page must contain info on its level. */
388
dict_index_t* index, /* in: index tree */
389
page_t* page, /* in: page to be freed, x-latched */
390
mtr_t* mtr); /* in: mtr */
391
/******************************************************************
392
Frees a file page used in an index tree. Can be used also to BLOB
393
external storage pages, because the page level 0 can be given as an
399
dict_index_t* index, /* in: index tree */
400
page_t* page, /* in: page to be freed, x-latched */
401
ulint level, /* in: page level */
402
mtr_t* mtr); /* in: mtr */
403
#ifdef UNIV_BTR_PRINT
404
/*****************************************************************
405
Prints size info of a B-tree. */
410
dict_index_t* index); /* in: index tree */
411
/******************************************************************
412
Prints directories and other info of all nodes in the index. */
417
dict_index_t* index, /* in: index */
418
ulint width); /* in: print this many entries from start
420
#endif /* UNIV_BTR_PRINT */
421
/****************************************************************
422
Checks the size and number of fields in a record based on the definition of
426
btr_index_rec_validate(
427
/*===================*/
428
/* out: TRUE if ok */
429
rec_t* rec, /* in: index record */
430
dict_index_t* index, /* in: index */
431
ibool dump_on_error); /* in: TRUE if the function
432
should print hex dump of record
434
/******************************************************************
435
Checks the consistency of an index tree. */
440
/* out: TRUE if ok */
441
dict_index_t* index, /* in: index */
442
trx_t* trx); /* in: transaction or NULL */
444
#define BTR_N_LEAF_PAGES 1
445
#define BTR_TOTAL_SIZE 2
448
#include "btr0btr.ic"
added
removed
storage/innobase/include/btr0btr.h
