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
/* Latching modes for the search function (in btr0cur.*) */
27
#define BTR_SEARCH_LEAF RW_S_LATCH
28
#define BTR_MODIFY_LEAF RW_X_LATCH
29
#define BTR_NO_LATCHES RW_NO_LATCH
30
#define BTR_MODIFY_TREE 33
31
#define BTR_CONT_MODIFY_TREE 34
32
#define BTR_SEARCH_PREV 35
33
#define BTR_MODIFY_PREV 36
35
/* If this is ORed to the latch mode, it means that the search tuple will be
36
inserted to the index, at the searched position */
37
#define BTR_INSERT 512
39
/* This flag ORed to latch mode says that we do the search in query
41
#define BTR_ESTIMATE 1024
43
/* This flag ORed to latch mode says that we can ignore possible
44
UNIQUE definition on secondary indexes when we decide if we can use the
45
insert buffer to speed up inserts */
46
#define BTR_IGNORE_SEC_UNIQUE 2048
48
/******************************************************************
49
Gets the root node of a tree and x-latches it. */
54
/* out: root page, x-latched */
55
dict_tree_t* tree, /* in: index tree */
56
mtr_t* mtr); /* in: mtr */
57
/******************************************************************
58
Gets a buffer page and declares its latching order level. */
63
ulint space, /* in: space id */
64
ulint page_no, /* in: page number */
65
ulint mode, /* in: latch mode */
66
mtr_t* mtr); /* in: mtr */
67
/******************************************************************
68
Gets the index id field of a page. */
71
btr_page_get_index_id(
72
/*==================*/
74
page_t* page); /* in: index page */
75
/************************************************************
76
Gets the node level field in an index page. */
79
btr_page_get_level_low(
80
/*===================*/
81
/* out: level, leaf level == 0 */
82
page_t* page); /* in: index page */
83
/************************************************************
84
Gets the node level field in an index page. */
89
/* out: level, leaf level == 0 */
90
page_t* page, /* in: index page */
91
mtr_t* mtr); /* in: mini-transaction handle */
92
/************************************************************
93
Gets the next index page number. */
98
/* out: next page number */
99
page_t* page, /* in: index page */
100
mtr_t* mtr); /* in: mini-transaction handle */
101
/************************************************************
102
Gets the previous index page number. */
107
/* out: prev page number */
108
page_t* page, /* in: index page */
109
mtr_t* mtr); /* in: mini-transaction handle */
110
/*****************************************************************
111
Gets pointer to the previous user record in the tree. It is assumed
112
that the caller has appropriate latches on the page and its neighbor. */
115
btr_get_prev_user_rec(
116
/*==================*/
117
/* out: previous user record, NULL if there is none */
118
rec_t* rec, /* in: record on leaf level */
119
mtr_t* mtr); /* in: mtr holding a latch on the page, and if
120
needed, also to the previous page */
121
/*****************************************************************
122
Gets pointer to the next user record in the tree. It is assumed
123
that the caller has appropriate latches on the page and its neighbor. */
126
btr_get_next_user_rec(
127
/*==================*/
128
/* out: next user record, NULL if there is none */
129
rec_t* rec, /* in: record on leaf level */
130
mtr_t* mtr); /* in: mtr holding a latch on the page, and if
131
needed, also to the next page */
132
/******************************************************************
133
Releases the latch on a leaf page and bufferunfixes it. */
136
btr_leaf_page_release(
137
/*==================*/
138
page_t* page, /* in: page */
139
ulint latch_mode, /* in: BTR_SEARCH_LEAF or BTR_MODIFY_LEAF */
140
mtr_t* mtr); /* in: mtr */
141
/******************************************************************
142
Gets the child node file address in a node pointer. */
145
btr_node_ptr_get_child_page_no(
146
/*===========================*/
147
/* out: child node address */
148
rec_t* rec, /* in: node pointer record */
149
const ulint* offsets);/* in: array returned by rec_get_offsets() */
150
/****************************************************************
151
Creates the root node for a new index tree. */
156
/* out: page number of the created root, FIL_NULL if
158
ulint type, /* in: type of the index */
159
ulint space, /* in: space where created */
160
dulint index_id,/* in: index id */
161
ulint comp, /* in: nonzero=compact page format */
162
mtr_t* mtr); /* in: mini-transaction handle */
163
/****************************************************************
164
Frees a B-tree except the root page, which MUST be freed after this
165
by calling btr_free_root. */
168
btr_free_but_not_root(
169
/*==================*/
170
ulint space, /* in: space where created */
171
ulint root_page_no); /* in: root page number */
172
/****************************************************************
173
Frees the B-tree root page. Other tree MUST already have been freed. */
178
ulint space, /* in: space where created */
179
ulint root_page_no, /* in: root page number */
180
mtr_t* mtr); /* in: a mini-transaction which has already
182
/*****************************************************************
183
Makes tree one level higher by splitting the root, and inserts
184
the tuple. It is assumed that mtr contains an x-latch on the tree.
185
NOTE that the operation of this function must always succeed,
186
we cannot reverse it: therefore enough free disk space must be
187
guaranteed to be available before this function is called. */
190
btr_root_raise_and_insert(
191
/*======================*/
192
/* out: inserted record */
193
btr_cur_t* cursor, /* in: cursor at which to insert: must be
194
on the root page; when the function returns,
195
the cursor is positioned on the predecessor
196
of the inserted record */
197
dtuple_t* tuple, /* in: tuple to insert */
198
mtr_t* mtr); /* in: mtr */
199
/*****************************************************************
200
Reorganizes an index page. */
205
page_t* page, /* in: page to be reorganized */
206
dict_index_t* index, /* in: record descriptor */
207
mtr_t* mtr); /* in: mtr */
208
/*****************************************************************
209
Decides if the page should be split at the convergence point of
210
inserts converging to left. */
213
btr_page_get_split_rec_to_left(
214
/*===========================*/
215
/* out: TRUE if split recommended */
216
btr_cur_t* cursor, /* in: cursor at which to insert */
217
rec_t** split_rec);/* out: if split recommended,
218
the first record on upper half page,
219
or NULL if tuple should be first */
220
/*****************************************************************
221
Decides if the page should be split at the convergence point of
222
inserts converging to right. */
225
btr_page_get_split_rec_to_right(
226
/*============================*/
227
/* out: TRUE if split recommended */
228
btr_cur_t* cursor, /* in: cursor at which to insert */
229
rec_t** split_rec);/* out: if split recommended,
230
the first record on upper half page,
231
or NULL if tuple should be first */
232
/*****************************************************************
233
Splits an index page to halves and inserts the tuple. It is assumed
234
that mtr holds an x-latch to the index tree. NOTE: the tree x-latch
235
is released within this function! NOTE that the operation of this
236
function must always succeed, we cannot reverse it: therefore
237
enough free disk space must be guaranteed to be available before
238
this function is called. */
241
btr_page_split_and_insert(
242
/*======================*/
243
/* out: inserted record; NOTE: the tree
244
x-latch is released! NOTE: 2 free disk
245
pages must be available! */
246
btr_cur_t* cursor, /* in: cursor at which to insert; when the
247
function returns, the cursor is positioned
248
on the predecessor of the inserted record */
249
dtuple_t* tuple, /* in: tuple to insert */
250
mtr_t* mtr); /* in: mtr */
251
/***********************************************************
252
Inserts a data tuple to a tree on a non-leaf level. It is assumed
253
that mtr holds an x-latch on the tree. */
256
btr_insert_on_non_leaf_level(
257
/*=========================*/
258
dict_tree_t* tree, /* in: tree */
259
ulint level, /* in: level, must be > 0 */
260
dtuple_t* tuple, /* in: the record to be inserted */
261
mtr_t* mtr); /* in: mtr */
262
/********************************************************************
263
Sets a record as the predefined minimum record. */
266
btr_set_min_rec_mark(
267
/*=================*/
268
rec_t* rec, /* in: record */
269
ulint comp, /* in: nonzero=compact page format */
270
mtr_t* mtr); /* in: mtr */
271
/*****************************************************************
272
Deletes on the upper level the node pointer to a page. */
277
dict_tree_t* tree, /* in: index tree */
278
page_t* page, /* in: page whose node pointer is deleted */
279
mtr_t* mtr); /* in: mtr */
280
/****************************************************************
281
Checks that the node pointer to a page is appropriate. */
287
dict_tree_t* tree, /* in: index tree */
288
page_t* page, /* in: index page */
289
mtr_t* mtr); /* in: mtr */
290
/*****************************************************************
291
Tries to merge the page first to the left immediate brother if such a
292
brother exists, and the node pointers to the current page and to the
293
brother reside on the same page. If the left brother does not satisfy these
294
conditions, looks at the right brother. If the page is the only one on that
295
level lifts the records of the page to the father page, thus reducing the
296
tree height. It is assumed that mtr holds an x-latch on the tree and on the
297
page. If cursor is on the leaf level, mtr must also hold x-latches to
298
the brothers, if they exist. NOTE: it is assumed that the caller has reserved
299
enough free extents so that the compression will always succeed if done! */
303
btr_cur_t* cursor, /* in: cursor on the page to merge or lift;
304
the page must not be empty: in record delete
305
use btr_discard_page if the page would become
307
mtr_t* mtr); /* in: mtr */
308
/*****************************************************************
309
Discards a page from a B-tree. This is used to remove the last record from
310
a B-tree page: the whole page must be removed at the same time. This cannot
311
be used for the root page, which is allowed to be empty. */
316
btr_cur_t* cursor, /* in: cursor on the page to discard: not on
318
mtr_t* mtr); /* in: mtr */
319
/********************************************************************
320
Parses the redo log record for setting an index record as the predefined
324
btr_parse_set_min_rec_mark(
325
/*=======================*/
326
/* out: end of log record or NULL */
327
byte* ptr, /* in: buffer */
328
byte* end_ptr,/* in: buffer end */
329
ulint comp, /* in: nonzero=compact page format */
330
page_t* page, /* in: page or NULL */
331
mtr_t* mtr); /* in: mtr or NULL */
332
/***************************************************************
333
Parses a redo log record of reorganizing a page. */
336
btr_parse_page_reorganize(
337
/*======================*/
338
/* out: end of log record or NULL */
339
byte* ptr, /* in: buffer */
340
byte* end_ptr,/* in: buffer end */
341
dict_index_t* index, /* in: record descriptor */
342
page_t* page, /* in: page or NULL */
343
mtr_t* mtr); /* in: mtr or NULL */
344
/******************************************************************
345
Gets the number of pages in a B-tree. */
350
/* out: number of pages */
351
dict_index_t* index, /* in: index */
352
ulint flag); /* in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
353
/******************************************************************
354
Allocates a new file page to be used in an index tree. NOTE: we assume
355
that the caller has made the reservation for free extents! */
360
/* out: new allocated page, x-latched;
361
NULL if out of space */
362
dict_tree_t* tree, /* in: index tree */
363
ulint hint_page_no, /* in: hint of a good page */
364
byte file_direction, /* in: direction where a possible
365
page split is made */
366
ulint level, /* in: level where the page is placed
368
mtr_t* mtr); /* in: mtr */
369
/******************************************************************
370
Frees a file page used in an index tree. NOTE: cannot free field external
371
storage pages because the page must contain info on its level. */
376
dict_tree_t* tree, /* in: index tree */
377
page_t* page, /* in: page to be freed, x-latched */
378
mtr_t* mtr); /* in: mtr */
379
/******************************************************************
380
Frees a file page used in an index tree. Can be used also to BLOB
381
external storage pages, because the page level 0 can be given as an
387
dict_tree_t* tree, /* in: index tree */
388
page_t* page, /* in: page to be freed, x-latched */
389
ulint level, /* in: page level */
390
mtr_t* mtr); /* in: mtr */
391
#ifdef UNIV_BTR_PRINT
392
/*****************************************************************
393
Prints size info of a B-tree. */
398
dict_tree_t* tree); /* in: index tree */
399
/******************************************************************
400
Prints directories and other info of all nodes in the tree. */
405
dict_tree_t* tree, /* in: tree */
406
ulint width); /* in: print this many entries from start
408
#endif /* UNIV_BTR_PRINT */
409
/****************************************************************
410
Checks the size and number of fields in a record based on the definition of
414
btr_index_rec_validate(
415
/*====================*/
416
/* out: TRUE if ok */
417
rec_t* rec, /* in: index record */
418
dict_index_t* index, /* in: index */
419
ibool dump_on_error); /* in: TRUE if the function
420
should print hex dump of record
422
/******************************************************************
423
Checks the consistency of an index tree. */
428
/* out: TRUE if ok */
429
dict_tree_t* tree, /* in: tree */
430
trx_t* trx); /* in: transaction or NULL */
432
#define BTR_N_LEAF_PAGES 1
433
#define BTR_TOTAL_SIZE 2
436
#include "btr0btr.ic"
added
removed
mysql-source/innobase/include/btr0btr.h
