1
/*****************************************************************************
3
Copyright (c) 1994, 2009, Innobase Oy. All Rights Reserved.
5
This program is free software; you can redistribute it and/or modify it under
6
the terms of the GNU General Public License as published by the Free Software
7
Foundation; version 2 of the License.
9
This program is distributed in the hope that it will be useful, but WITHOUT
10
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13
You should have received a copy of the GNU General Public License along with
14
this program; if not, write to the Free Software Foundation, Inc., 59 Temple
15
Place, Suite 330, Boston, MA 02111-1307 USA
17
*****************************************************************************/
19
/******************************************************
22
Created 6/2/1994 Heikki Tuuri
23
*******************************************************/
30
#include "dict0dict.h"
31
#include "data0data.h"
34
#include "btr0types.h"
36
#ifndef UNIV_HOTBACKUP
37
/* Maximum record size which can be stored on a page, without using the
38
special big record storage structure */
40
#define BTR_PAGE_MAX_REC_SIZE (UNIV_PAGE_SIZE / 2 - 200)
42
/* Maximum depth of a B-tree in InnoDB. Note that this isn't a maximum as
43
such; none of the tree operations avoid producing trees bigger than this. It
44
is instead a "max depth that other code must work with", useful for e.g.
45
fixed-size arrays that must store some information about each level in a
46
tree. In other words: if a B-tree with bigger depth than this is
47
encountered, it is not acceptable for it to lead to mysterious memory
48
corruption, but it is acceptable for the program to die with a clear assert
50
#define BTR_MAX_LEVELS 100
52
/* Latching modes for btr_cur_search_to_nth_level(). */
53
#define BTR_SEARCH_LEAF RW_S_LATCH
54
#define BTR_MODIFY_LEAF RW_X_LATCH
55
#define BTR_NO_LATCHES RW_NO_LATCH
56
#define BTR_MODIFY_TREE 33
57
#define BTR_CONT_MODIFY_TREE 34
58
#define BTR_SEARCH_PREV 35
59
#define BTR_MODIFY_PREV 36
61
/* If this is ORed to the latch mode, it means that the search tuple will be
62
inserted to the index, at the searched position */
63
#define BTR_INSERT 512
65
/* This flag ORed to latch mode says that we do the search in query
67
#define BTR_ESTIMATE 1024
69
/* This flag ORed to latch mode says that we can ignore possible
70
UNIQUE definition on secondary indexes when we decide if we can use the
71
insert buffer to speed up inserts */
72
#define BTR_IGNORE_SEC_UNIQUE 2048
74
/******************************************************************
75
Gets the root node of a tree and x-latches it. */
80
/* out: root page, x-latched */
81
dict_index_t* index, /* in: index tree */
82
mtr_t* mtr); /* in: mtr */
83
/******************************************************************
84
Gets a buffer page and declares its latching order level. */
89
ulint space, /* in: space id */
90
ulint zip_size, /* in: compressed page size in bytes
91
or 0 for uncompressed pages */
92
ulint page_no, /* in: page number */
93
ulint mode, /* in: latch mode */
94
mtr_t* mtr); /* in: mtr */
95
/******************************************************************
96
Gets a buffer page and declares its latching order level. */
101
ulint space, /* in: space id */
102
ulint zip_size, /* in: compressed page size in bytes
103
or 0 for uncompressed pages */
104
ulint page_no, /* in: page number */
105
ulint mode, /* in: latch mode */
106
mtr_t* mtr); /* in: mtr */
107
#endif /* !UNIV_HOTBACKUP */
108
/******************************************************************
109
Gets the index id field of a page. */
112
btr_page_get_index_id(
113
/*==================*/
115
const page_t* page); /* in: index page */
116
#ifndef UNIV_HOTBACKUP
117
/************************************************************
118
Gets the node level field in an index page. */
121
btr_page_get_level_low(
122
/*===================*/
123
/* out: level, leaf level == 0 */
124
const page_t* page); /* in: index page */
125
/************************************************************
126
Gets the node level field in an index page. */
131
/* out: level, leaf level == 0 */
132
const page_t* page, /* in: index page */
133
mtr_t* mtr); /* in: mini-transaction handle */
134
/************************************************************
135
Gets the next index page number. */
140
/* out: next page number */
141
const page_t* page, /* in: index page */
142
mtr_t* mtr); /* in: mini-transaction handle */
143
/************************************************************
144
Gets the previous index page number. */
149
/* out: prev page number */
150
const page_t* page, /* in: index page */
151
mtr_t* mtr); /* in: mini-transaction handle */
152
/*****************************************************************
153
Gets pointer to the previous user record in the tree. It is assumed
154
that the caller has appropriate latches on the page and its neighbor. */
157
btr_get_prev_user_rec(
158
/*==================*/
159
/* out: previous user record, NULL if there is none */
160
rec_t* rec, /* in: record on leaf level */
161
mtr_t* mtr); /* in: mtr holding a latch on the page, and if
162
needed, also to the previous page */
163
/*****************************************************************
164
Gets pointer to the next user record in the tree. It is assumed
165
that the caller has appropriate latches on the page and its neighbor. */
168
btr_get_next_user_rec(
169
/*==================*/
170
/* out: next user record, NULL if there is none */
171
rec_t* rec, /* in: record on leaf level */
172
mtr_t* mtr); /* in: mtr holding a latch on the page, and if
173
needed, also to the next page */
174
/******************************************************************
175
Releases the latch on a leaf page and bufferunfixes it. */
178
btr_leaf_page_release(
179
/*==================*/
180
buf_block_t* block, /* in: buffer block */
181
ulint latch_mode, /* in: BTR_SEARCH_LEAF or
183
mtr_t* mtr); /* in: mtr */
184
/******************************************************************
185
Gets the child node file address in a node pointer. */
188
btr_node_ptr_get_child_page_no(
189
/*===========================*/
190
/* out: child node address */
191
const rec_t* rec, /* in: node pointer record */
192
const ulint* offsets);/* in: array returned by rec_get_offsets() */
193
/****************************************************************
194
Creates the root node for a new index tree. */
199
/* out: page number of the created root,
200
FIL_NULL if did not succeed */
201
ulint type, /* in: type of the index */
202
ulint space, /* in: space where created */
203
ulint zip_size,/* in: compressed page size in bytes
204
or 0 for uncompressed pages */
205
dulint index_id,/* in: index id */
206
dict_index_t* index, /* in: index */
207
mtr_t* mtr); /* in: mini-transaction handle */
208
/****************************************************************
209
Frees a B-tree except the root page, which MUST be freed after this
210
by calling btr_free_root. */
213
btr_free_but_not_root(
214
/*==================*/
215
ulint space, /* in: space where created */
216
ulint zip_size, /* in: compressed page size in bytes
217
or 0 for uncompressed pages */
218
ulint root_page_no); /* in: root page number */
219
/****************************************************************
220
Frees the B-tree root page. Other tree MUST already have been freed. */
225
ulint space, /* in: space where created */
226
ulint zip_size, /* in: compressed page size in bytes
227
or 0 for uncompressed pages */
228
ulint root_page_no, /* in: root page number */
229
mtr_t* mtr); /* in: a mini-transaction which has already
231
/*****************************************************************
232
Makes tree one level higher by splitting the root, and inserts
233
the tuple. It is assumed that mtr contains an x-latch on the tree.
234
NOTE that the operation of this function must always succeed,
235
we cannot reverse it: therefore enough free disk space must be
236
guaranteed to be available before this function is called. */
239
btr_root_raise_and_insert(
240
/*======================*/
241
/* out: inserted record */
242
btr_cur_t* cursor, /* in: cursor at which to insert: must be
243
on the root page; when the function returns,
244
the cursor is positioned on the predecessor
245
of the inserted record */
246
const dtuple_t* tuple, /* in: tuple to insert */
247
ulint n_ext, /* in: number of externally stored columns */
248
mtr_t* mtr); /* in: mtr */
249
/*****************************************************************
250
Reorganizes an index page.
251
IMPORTANT: if btr_page_reorganize() is invoked on a compressed leaf
252
page of a non-clustered index, the caller must update the insert
253
buffer free bits in the same mini-transaction in such a way that the
254
modification will be redo-logged. */
259
/* out: TRUE on success, FALSE on failure */
260
buf_block_t* block, /* in: page to be reorganized */
261
dict_index_t* index, /* in: record descriptor */
262
mtr_t* mtr); /* in: mtr */
263
/*****************************************************************
264
Decides if the page should be split at the convergence point of
265
inserts converging to left. */
268
btr_page_get_split_rec_to_left(
269
/*===========================*/
270
/* out: TRUE if split recommended */
271
btr_cur_t* cursor, /* in: cursor at which to insert */
272
rec_t** split_rec);/* out: if split recommended,
273
the first record on upper half page,
274
or NULL if tuple should be first */
275
/*****************************************************************
276
Decides if the page should be split at the convergence point of
277
inserts converging to right. */
280
btr_page_get_split_rec_to_right(
281
/*============================*/
282
/* out: TRUE if split recommended */
283
btr_cur_t* cursor, /* in: cursor at which to insert */
284
rec_t** split_rec);/* out: if split recommended,
285
the first record on upper half page,
286
or NULL if tuple should be first */
287
/*****************************************************************
288
Splits an index page to halves and inserts the tuple. It is assumed
289
that mtr holds an x-latch to the index tree. NOTE: the tree x-latch
290
is released within this function! NOTE that the operation of this
291
function must always succeed, we cannot reverse it: therefore
292
enough free disk space must be guaranteed to be available before
293
this function is called. */
296
btr_page_split_and_insert(
297
/*======================*/
298
/* out: inserted record; NOTE: the tree
299
x-latch is released! NOTE: 2 free disk
300
pages must be available! */
301
btr_cur_t* cursor, /* in: cursor at which to insert; when the
302
function returns, the cursor is positioned
303
on the predecessor of the inserted record */
304
const dtuple_t* tuple, /* in: tuple to insert */
305
ulint n_ext, /* in: number of externally stored columns */
306
mtr_t* mtr); /* in: mtr */
307
/***********************************************************
308
Inserts a data tuple to a tree on a non-leaf level. It is assumed
309
that mtr holds an x-latch on the tree. */
312
btr_insert_on_non_leaf_level(
313
/*=========================*/
314
dict_index_t* index, /* in: index */
315
ulint level, /* in: level, must be > 0 */
316
dtuple_t* tuple, /* in: the record to be inserted */
317
mtr_t* mtr); /* in: mtr */
318
#endif /* !UNIV_HOTBACKUP */
319
/********************************************************************
320
Sets a record as the predefined minimum record. */
323
btr_set_min_rec_mark(
324
/*=================*/
325
rec_t* rec, /* in/out: record */
326
mtr_t* mtr); /* in: mtr */
327
#ifndef UNIV_HOTBACKUP
328
/*****************************************************************
329
Deletes on the upper level the node pointer to a page. */
334
dict_index_t* index, /* in: index tree */
335
buf_block_t* block, /* in: page whose node pointer is deleted */
336
mtr_t* mtr); /* in: mtr */
338
/****************************************************************
339
Checks that the node pointer to a page is appropriate. */
345
dict_index_t* index, /* in: index tree */
346
buf_block_t* block, /* in: index page */
347
mtr_t* mtr); /* in: mtr */
348
#endif /* UNIV_DEBUG */
349
/*****************************************************************
350
Tries to merge the page first to the left immediate brother if such a
351
brother exists, and the node pointers to the current page and to the
352
brother reside on the same page. If the left brother does not satisfy these
353
conditions, looks at the right brother. If the page is the only one on that
354
level lifts the records of the page to the father page, thus reducing the
355
tree height. It is assumed that mtr holds an x-latch on the tree and on the
356
page. If cursor is on the leaf level, mtr must also hold x-latches to
357
the brothers, if they exist. */
362
/* out: TRUE on success */
363
btr_cur_t* cursor, /* in: cursor on the page to merge or lift;
364
the page must not be empty: in record delete
365
use btr_discard_page if the page would become
367
mtr_t* mtr); /* in: mtr */
368
/*****************************************************************
369
Discards a page from a B-tree. This is used to remove the last record from
370
a B-tree page: the whole page must be removed at the same time. This cannot
371
be used for the root page, which is allowed to be empty. */
376
btr_cur_t* cursor, /* in: cursor on the page to discard: not on
378
mtr_t* mtr); /* in: mtr */
379
#endif /* !UNIV_HOTBACKUP */
380
/********************************************************************
381
Parses the redo log record for setting an index record as the predefined
385
btr_parse_set_min_rec_mark(
386
/*=======================*/
387
/* out: end of log record or NULL */
388
byte* ptr, /* in: buffer */
389
byte* end_ptr,/* in: buffer end */
390
ulint comp, /* in: nonzero=compact page format */
391
page_t* page, /* in: page or NULL */
392
mtr_t* mtr); /* in: mtr or NULL */
393
/***************************************************************
394
Parses a redo log record of reorganizing a page. */
397
btr_parse_page_reorganize(
398
/*======================*/
399
/* out: end of log record or NULL */
400
byte* ptr, /* in: buffer */
401
byte* end_ptr,/* in: buffer end */
402
dict_index_t* index, /* in: record descriptor */
403
buf_block_t* block, /* in: page to be reorganized, or NULL */
404
mtr_t* mtr); /* in: mtr or NULL */
405
#ifndef UNIV_HOTBACKUP
406
/******************************************************************
407
Gets the number of pages in a B-tree. */
412
/* out: number of pages */
413
dict_index_t* index, /* in: index */
414
ulint flag); /* in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
415
/******************************************************************
416
Allocates a new file page to be used in an index tree. NOTE: we assume
417
that the caller has made the reservation for free extents! */
422
/* out: new allocated block, x-latched;
423
NULL if out of space */
424
dict_index_t* index, /* in: index tree */
425
ulint hint_page_no, /* in: hint of a good page */
426
byte file_direction, /* in: direction where a possible
427
page split is made */
428
ulint level, /* in: level where the page is placed
430
mtr_t* mtr); /* in: mtr */
431
/******************************************************************
432
Frees a file page used in an index tree. NOTE: cannot free field external
433
storage pages because the page must contain info on its level. */
438
dict_index_t* index, /* in: index tree */
439
buf_block_t* block, /* in: block to be freed, x-latched */
440
mtr_t* mtr); /* in: mtr */
441
/******************************************************************
442
Frees a file page used in an index tree. Can be used also to BLOB
443
external storage pages, because the page level 0 can be given as an
449
dict_index_t* index, /* in: index tree */
450
buf_block_t* block, /* in: block to be freed, x-latched */
451
ulint level, /* in: page level */
452
mtr_t* mtr); /* in: mtr */
453
#ifdef UNIV_BTR_PRINT
454
/*****************************************************************
455
Prints size info of a B-tree. */
460
dict_index_t* index); /* in: index tree */
461
/******************************************************************
462
Prints directories and other info of all nodes in the index. */
467
dict_index_t* index, /* in: index */
468
ulint width); /* in: print this many entries from start
470
#endif /* UNIV_BTR_PRINT */
471
/****************************************************************
472
Checks the size and number of fields in a record based on the definition of
476
btr_index_rec_validate(
477
/*===================*/
478
/* out: TRUE if ok */
479
const rec_t* rec, /* in: index record */
480
const dict_index_t* index, /* in: index */
481
ibool dump_on_error); /* in: TRUE if the function
482
should print hex dump of record
484
/******************************************************************
485
Checks the consistency of an index tree. */
490
/* out: TRUE if ok */
491
dict_index_t* index, /* in: index */
492
trx_t* trx); /* in: transaction or NULL */
494
#define BTR_N_LEAF_PAGES 1
495
#define BTR_TOTAL_SIZE 2
496
#endif /* !UNIV_HOTBACKUP */
499
#include "btr0btr.ic"
added
removed
include/btr0btr.h
