btr0btr.h 16.8 KB
Newer Older
osku's avatar
osku committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
/******************************************************
The B-tree

(c) 1994-1996 Innobase Oy

Created 6/2/1994 Heikki Tuuri
*******************************************************/

#ifndef btr0btr_h
#define btr0btr_h

#include "univ.i"

#include "dict0dict.h"
#include "data0data.h"
#include "page0cur.h"
#include "mtr0mtr.h"
#include "btr0types.h"

/* Maximum record size which can be stored on a page, without using the
special big record storage structure */

#define	BTR_PAGE_MAX_REC_SIZE	(UNIV_PAGE_SIZE / 2 - 200)

25 26 27 28 29 30 31 32 33 34 35
/* Maximum depth of a B-tree in InnoDB. Note that this isn't a maximum as
such; none of the tree operations avoid producing trees bigger than this. It
is instead a "max depth that other code must work with", useful for e.g.
fixed-size arrays that must store some information about each level in a
tree. In other words: if a B-tree with bigger depth than this is
encountered, it is not acceptable for it to lead to mysterious memory
corruption, but it is acceptable for the program to die with a clear assert
failure. */
#define BTR_MAX_LEVELS		100

/* Latching modes for btr_cur_search_to_nth_level(). */
osku's avatar
osku committed
36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
#define BTR_SEARCH_LEAF		RW_S_LATCH
#define BTR_MODIFY_LEAF		RW_X_LATCH
#define BTR_NO_LATCHES		RW_NO_LATCH
#define	BTR_MODIFY_TREE		33
#define	BTR_CONT_MODIFY_TREE	34
#define	BTR_SEARCH_PREV		35
#define	BTR_MODIFY_PREV		36

/* If this is ORed to the latch mode, it means that the search tuple will be
inserted to the index, at the searched position */
#define BTR_INSERT		512

/* This flag ORed to latch mode says that we do the search in query
optimization */
#define BTR_ESTIMATE		1024

/* This flag ORed to latch mode says that we can ignore possible
UNIQUE definition on secondary indexes when we decide if we can use the
insert buffer to speed up inserts */
55
#define BTR_IGNORE_SEC_UNIQUE	2048
osku's avatar
osku committed
56 57 58

/******************************************************************
Gets the root node of a tree and x-latches it. */
59
UNIV_INTERN
osku's avatar
osku committed
60 61 62 63
page_t*
btr_root_get(
/*=========*/
				/* out: root page, x-latched */
64
	dict_index_t*	index,	/* in: index tree */
osku's avatar
osku committed
65 66 67 68
	mtr_t*		mtr);	/* in: mtr */
/******************************************************************
Gets a buffer page and declares its latching order level. */
UNIV_INLINE
69 70 71 72
buf_block_t*
btr_block_get(
/*==========*/
	ulint	space,		/* in: space id */
73 74
	ulint	zip_size,	/* in: compressed page size in bytes
				or 0 for uncompressed pages */
75 76 77 78 79 80
	ulint	page_no,	/* in: page number */
	ulint	mode,		/* in: latch mode */
	mtr_t*	mtr);		/* in: mtr */
/******************************************************************
Gets a buffer page and declares its latching order level. */
UNIV_INLINE
osku's avatar
osku committed
81 82 83 84
page_t*
btr_page_get(
/*=========*/
	ulint	space,		/* in: space id */
85 86
	ulint	zip_size,	/* in: compressed page size in bytes
				or 0 for uncompressed pages */
osku's avatar
osku committed
87 88 89 90 91 92 93 94 95 96
	ulint	page_no,	/* in: page number */
	ulint	mode,		/* in: latch mode */
	mtr_t*	mtr);		/* in: mtr */
/******************************************************************
Gets the index id field of a page. */
UNIV_INLINE
dulint
btr_page_get_index_id(
/*==================*/
				/* out: index id */
97
	const page_t*	page);	/* in: index page */
osku's avatar
osku committed
98 99 100 101 102 103
/************************************************************
Gets the node level field in an index page. */
UNIV_INLINE
ulint
btr_page_get_level_low(
/*===================*/
104 105
				/* out: level, leaf level == 0 */
	const page_t*	page);	/* in: index page */
osku's avatar
osku committed
106 107 108 109 110 111
/************************************************************
Gets the node level field in an index page. */
UNIV_INLINE
ulint
btr_page_get_level(
/*===============*/
112 113 114
				/* out: level, leaf level == 0 */
	const page_t*	page,	/* in: index page */
	mtr_t*		mtr);	/* in: mini-transaction handle */
osku's avatar
osku committed
115 116 117 118 119 120
/************************************************************
Gets the next index page number. */
UNIV_INLINE
ulint
btr_page_get_next(
/*==============*/
121 122 123
				/* out: next page number */
	const page_t*	page,	/* in: index page */
	mtr_t*		mtr);	/* in: mini-transaction handle */
osku's avatar
osku committed
124 125 126 127 128 129
/************************************************************
Gets the previous index page number. */
UNIV_INLINE
ulint
btr_page_get_prev(
/*==============*/
130 131 132
				/* out: prev page number */
	const page_t*	page,	/* in: index page */
	mtr_t*		mtr);	/* in: mini-transaction handle */
osku's avatar
osku committed
133 134 135
/*****************************************************************
Gets pointer to the previous user record in the tree. It is assumed
that the caller has appropriate latches on the page and its neighbor. */
136
UNIV_INTERN
osku's avatar
osku committed
137 138 139 140 141 142 143 144 145 146
rec_t*
btr_get_prev_user_rec(
/*==================*/
			/* out: previous user record, NULL if there is none */
	rec_t*	rec,	/* in: record on leaf level */
	mtr_t*	mtr);	/* in: mtr holding a latch on the page, and if
			needed, also to the previous page */
/*****************************************************************
Gets pointer to the next user record in the tree. It is assumed
that the caller has appropriate latches on the page and its neighbor. */
147
UNIV_INTERN
osku's avatar
osku committed
148 149 150 151 152 153 154 155 156 157 158 159 160
rec_t*
btr_get_next_user_rec(
/*==================*/
			/* out: next user record, NULL if there is none */
	rec_t*	rec,	/* in: record on leaf level */
	mtr_t*	mtr);	/* in: mtr holding a latch on the page, and if
			needed, also to the next page */
/******************************************************************
Releases the latch on a leaf page and bufferunfixes it. */
UNIV_INLINE
void
btr_leaf_page_release(
/*==================*/
161 162 163 164
	buf_block_t*	block,		/* in: buffer block */
	ulint		latch_mode,	/* in: BTR_SEARCH_LEAF or
					BTR_MODIFY_LEAF */
	mtr_t*		mtr);		/* in: mtr */
osku's avatar
osku committed
165 166 167 168 169 170
/******************************************************************
Gets the child node file address in a node pointer. */
UNIV_INLINE
ulint
btr_node_ptr_get_child_page_no(
/*===========================*/
171
				/* out: child node address */
172
	const rec_t*	rec,	/* in: node pointer record */
osku's avatar
osku committed
173 174 175
	const ulint*	offsets);/* in: array returned by rec_get_offsets() */
/****************************************************************
Creates the root node for a new index tree. */
176
UNIV_INTERN
osku's avatar
osku committed
177 178 179
ulint
btr_create(
/*=======*/
180 181 182 183
				/* out: page number of the created root,
				FIL_NULL if did not succeed */
	ulint		type,	/* in: type of the index */
	ulint		space,	/* in: space where created */
184 185
	ulint		zip_size,/* in: compressed page size in bytes
				or 0 for uncompressed pages */
186 187 188
	dulint		index_id,/* in: index id */
	dict_index_t*	index,	/* in: index */
	mtr_t*		mtr);	/* in: mini-transaction handle */
osku's avatar
osku committed
189 190 191
/****************************************************************
Frees a B-tree except the root page, which MUST be freed after this
by calling btr_free_root. */
192
UNIV_INTERN
osku's avatar
osku committed
193 194 195 196
void
btr_free_but_not_root(
/*==================*/
	ulint	space,		/* in: space where created */
197 198
	ulint	zip_size,	/* in: compressed page size in bytes
				or 0 for uncompressed pages */
osku's avatar
osku committed
199 200 201
	ulint	root_page_no);	/* in: root page number */
/****************************************************************
Frees the B-tree root page. Other tree MUST already have been freed. */
202
UNIV_INTERN
osku's avatar
osku committed
203 204 205 206
void
btr_free_root(
/*==========*/
	ulint	space,		/* in: space where created */
207 208
	ulint	zip_size,	/* in: compressed page size in bytes
				or 0 for uncompressed pages */
osku's avatar
osku committed
209 210 211 212 213 214 215 216 217
	ulint	root_page_no,	/* in: root page number */
	mtr_t*	mtr);		/* in: a mini-transaction which has already
				been started */
/*****************************************************************
Makes tree one level higher by splitting the root, and inserts
the tuple. It is assumed that mtr contains an x-latch on the tree.
NOTE that the operation of this function must always succeed,
we cannot reverse it: therefore enough free disk space must be
guaranteed to be available before this function is called. */
218
UNIV_INTERN
osku's avatar
osku committed
219 220 221 222 223 224 225 226
rec_t*
btr_root_raise_and_insert(
/*======================*/
				/* out: inserted record */
	btr_cur_t*	cursor,	/* in: cursor at which to insert: must be
				on the root page; when the function returns,
				the cursor is positioned on the predecessor
				of the inserted record */
227 228
	const dtuple_t*	tuple,	/* in: tuple to insert */
	ulint		n_ext,	/* in: number of externally stored columns */
osku's avatar
osku committed
229 230
	mtr_t*		mtr);	/* in: mtr */
/*****************************************************************
231 232 233 234 235
Reorganizes an index page.
IMPORTANT: if btr_page_reorganize() is invoked on a compressed leaf
page of a non-clustered index, the caller must update the insert
buffer free bits in the same mini-transaction in such a way that the
modification will be redo-logged. */
236
UNIV_INTERN
237
ibool
osku's avatar
osku committed
238 239
btr_page_reorganize(
/*================*/
240
				/* out: TRUE on success, FALSE on failure */
241
	buf_block_t*	block,	/* in: page to be reorganized */
osku's avatar
osku committed
242
	dict_index_t*	index,	/* in: record descriptor */
243
	mtr_t*		mtr);	/* in: mtr */
osku's avatar
osku committed
244 245 246
/*****************************************************************
Decides if the page should be split at the convergence point of
inserts converging to left. */
247
UNIV_INTERN
osku's avatar
osku committed
248 249 250 251 252 253 254 255 256 257 258
ibool
btr_page_get_split_rec_to_left(
/*===========================*/
				/* out: TRUE if split recommended */
	btr_cur_t*	cursor,	/* in: cursor at which to insert */
	rec_t**		split_rec);/* out: if split recommended,
				the first record on upper half page,
				or NULL if tuple should be first */
/*****************************************************************
Decides if the page should be split at the convergence point of
inserts converging to right. */
259
UNIV_INTERN
osku's avatar
osku committed
260 261 262 263 264 265 266 267 268 269 270 271 272 273 274
ibool
btr_page_get_split_rec_to_right(
/*============================*/
				/* out: TRUE if split recommended */
	btr_cur_t*	cursor,	/* in: cursor at which to insert */
	rec_t**		split_rec);/* out: if split recommended,
				the first record on upper half page,
				or NULL if tuple should be first */
/*****************************************************************
Splits an index page to halves and inserts the tuple. It is assumed
that mtr holds an x-latch to the index tree. NOTE: the tree x-latch
is released within this function! NOTE that the operation of this
function must always succeed, we cannot reverse it: therefore
enough free disk space must be guaranteed to be available before
this function is called. */
275
UNIV_INTERN
osku's avatar
osku committed
276 277 278 279 280 281 282 283 284
rec_t*
btr_page_split_and_insert(
/*======================*/
				/* out: inserted record; NOTE: the tree
				x-latch is released! NOTE: 2 free disk
				pages must be available! */
	btr_cur_t*	cursor,	/* in: cursor at which to insert; when the
				function returns, the cursor is positioned
				on the predecessor of the inserted record */
285 286
	const dtuple_t*	tuple,	/* in: tuple to insert */
	ulint		n_ext,	/* in: number of externally stored columns */
osku's avatar
osku committed
287 288 289 290
	mtr_t*		mtr);	/* in: mtr */
/***********************************************************
Inserts a data tuple to a tree on a non-leaf level. It is assumed
that mtr holds an x-latch on the tree. */
291
UNIV_INTERN
osku's avatar
osku committed
292 293 294
void
btr_insert_on_non_leaf_level(
/*=========================*/
295
	dict_index_t*	index,	/* in: index */
osku's avatar
osku committed
296 297 298 299 300
	ulint		level,	/* in: level, must be > 0 */
	dtuple_t*	tuple,	/* in: the record to be inserted */
	mtr_t*		mtr);	/* in: mtr */
/********************************************************************
Sets a record as the predefined minimum record. */
301
UNIV_INTERN
osku's avatar
osku committed
302 303 304
void
btr_set_min_rec_mark(
/*=================*/
305 306
	rec_t*	rec,	/* in/out: record */
	mtr_t*	mtr);	/* in: mtr */
osku's avatar
osku committed
307 308
/*****************************************************************
Deletes on the upper level the node pointer to a page. */
309
UNIV_INTERN
osku's avatar
osku committed
310 311 312
void
btr_node_ptr_delete(
/*================*/
313
	dict_index_t*	index,	/* in: index tree */
314
	buf_block_t*	block,	/* in: page whose node pointer is deleted */
osku's avatar
osku committed
315
	mtr_t*		mtr);	/* in: mtr */
316
#ifdef UNIV_DEBUG
osku's avatar
osku committed
317 318
/****************************************************************
Checks that the node pointer to a page is appropriate. */
319
UNIV_INTERN
osku's avatar
osku committed
320 321 322 323
ibool
btr_check_node_ptr(
/*===============*/
				/* out: TRUE */
324
	dict_index_t*	index,	/* in: index tree */
325
	buf_block_t*	block,	/* in: index page */
osku's avatar
osku committed
326
	mtr_t*		mtr);	/* in: mtr */
327
#endif /* UNIV_DEBUG */
osku's avatar
osku committed
328 329 330 331 332 333 334 335
/*****************************************************************
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. If the left brother does not satisfy these
conditions, looks at the right brother. If the page is the only one on that
level lifts the records of the page to the father page, thus reducing the
tree height. It is assumed that mtr holds an x-latch on the tree and on the
page. If cursor is on the leaf level, mtr must also hold x-latches to
marko's avatar
marko committed
336
the brothers, if they exist. */
337
UNIV_INTERN
marko's avatar
marko committed
338
ibool
osku's avatar
osku committed
339 340
btr_compress(
/*=========*/
marko's avatar
marko committed
341
				/* out: TRUE on success */
osku's avatar
osku committed
342 343 344 345 346 347 348 349 350
	btr_cur_t*	cursor,	/* in: cursor on the page to merge or lift;
				the page must not be empty: in record delete
				use btr_discard_page if the page would become
				empty */
	mtr_t*		mtr);	/* in: mtr */
/*****************************************************************
Discards a page from a B-tree. This is used to remove the last record from
a B-tree page: the whole page must be removed at the same time. This cannot
be used for the root page, which is allowed to be empty. */
351
UNIV_INTERN
osku's avatar
osku committed
352 353 354 355 356 357 358 359 360
void
btr_discard_page(
/*=============*/
	btr_cur_t*	cursor,	/* in: cursor on the page to discard: not on
				the root page */
	mtr_t*		mtr);	/* in: mtr */
/********************************************************************
Parses the redo log record for setting an index record as the predefined
minimum record. */
361
UNIV_INTERN
osku's avatar
osku committed
362 363 364 365 366 367 368 369 370 371 372
byte*
btr_parse_set_min_rec_mark(
/*=======================*/
			/* out: end of log record or NULL */
	byte*	ptr,	/* in: buffer */
	byte*	end_ptr,/* in: buffer end */
	ulint	comp,	/* in: nonzero=compact page format */
	page_t*	page,	/* in: page or NULL */
	mtr_t*	mtr);	/* in: mtr or NULL */
/***************************************************************
Parses a redo log record of reorganizing a page. */
373
UNIV_INTERN
osku's avatar
osku committed
374 375 376 377 378 379 380
byte*
btr_parse_page_reorganize(
/*======================*/
				/* out: end of log record or NULL */
	byte*		ptr,	/* in: buffer */
	byte*		end_ptr,/* in: buffer end */
	dict_index_t*	index,	/* in: record descriptor */
381
	buf_block_t*	block,	/* in: page to be reorganized, or NULL */
osku's avatar
osku committed
382 383 384
	mtr_t*		mtr);	/* in: mtr or NULL */
/******************************************************************
Gets the number of pages in a B-tree. */
385
UNIV_INTERN
osku's avatar
osku committed
386 387 388 389 390 391 392 393 394
ulint
btr_get_size(
/*=========*/
				/* out: number of pages */
	dict_index_t*	index,	/* in: index */
	ulint		flag);	/* in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
/******************************************************************
Allocates a new file page to be used in an index tree. NOTE: we assume
that the caller has made the reservation for free extents! */
395
UNIV_INTERN
396
buf_block_t*
osku's avatar
osku committed
397 398
btr_page_alloc(
/*===========*/
399
					/* out: new allocated block, x-latched;
osku's avatar
osku committed
400
					NULL if out of space */
401
	dict_index_t*	index,		/* in: index tree */
osku's avatar
osku committed
402 403 404 405 406 407 408 409 410
	ulint		hint_page_no,	/* in: hint of a good page */
	byte		file_direction,	/* in: direction where a possible
					page split is made */
	ulint		level,		/* in: level where the page is placed
					in the tree */
	mtr_t*		mtr);		/* in: mtr */
/******************************************************************
Frees a file page used in an index tree. NOTE: cannot free field external
storage pages because the page must contain info on its level. */
411
UNIV_INTERN
osku's avatar
osku committed
412 413 414
void
btr_page_free(
/*==========*/
415
	dict_index_t*	index,	/* in: index tree */
416
	buf_block_t*	block,	/* in: block to be freed, x-latched */
osku's avatar
osku committed
417 418 419 420 421
	mtr_t*		mtr);	/* in: mtr */
/******************************************************************
Frees a file page used in an index tree. Can be used also to BLOB
external storage pages, because the page level 0 can be given as an
argument. */
422
UNIV_INTERN
osku's avatar
osku committed
423 424 425
void
btr_page_free_low(
/*==============*/
426
	dict_index_t*	index,	/* in: index tree */
427
	buf_block_t*	block,	/* in: block to be freed, x-latched */
osku's avatar
osku committed
428 429 430 431 432
	ulint		level,	/* in: page level */
	mtr_t*		mtr);	/* in: mtr */
#ifdef UNIV_BTR_PRINT
/*****************************************************************
Prints size info of a B-tree. */
433
UNIV_INTERN
osku's avatar
osku committed
434 435 436
void
btr_print_size(
/*===========*/
437
	dict_index_t*	index);	/* in: index tree */
osku's avatar
osku committed
438
/******************************************************************
439
Prints directories and other info of all nodes in the index. */
440
UNIV_INTERN
osku's avatar
osku committed
441
void
442 443 444
btr_print_index(
/*============*/
	dict_index_t*	index,	/* in: index */
osku's avatar
osku committed
445 446 447 448 449 450
	ulint		width);	/* in: print this many entries from start
				and end */
#endif /* UNIV_BTR_PRINT */
/****************************************************************
Checks the size and number of fields in a record based on the definition of
the index. */
451
UNIV_INTERN
osku's avatar
osku committed
452 453
ibool
btr_index_rec_validate(
454
/*===================*/
455 456 457 458 459 460
						/* out: TRUE if ok */
	const rec_t*		rec,		/* in: index record */
	const dict_index_t*	index,		/* in: index */
	ibool			dump_on_error);	/* in: TRUE if the function
						should print hex dump of record
						and page on error */
osku's avatar
osku committed
461 462
/******************************************************************
Checks the consistency of an index tree. */
463
UNIV_INTERN
osku's avatar
osku committed
464
ibool
465 466
btr_validate_index(
/*===============*/
osku's avatar
osku committed
467
				/* out: TRUE if ok */
468
	dict_index_t*	index,	/* in: index */
osku's avatar
osku committed
469 470
	trx_t*		trx);	/* in: transaction or NULL */

471
#define BTR_N_LEAF_PAGES	1
osku's avatar
osku committed
472 473 474 475 476 477
#define BTR_TOTAL_SIZE		2

#ifndef UNIV_NONINL
#include "btr0btr.ic"
#endif

478
#endif