← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/innobase/include/btr0btr.h

  • Committer: Monty Taylor
  • Date: 2008-10-27 23:19:48 UTC
  • mto: (520.4.12 merge-innodb-plugin)
  • mto: This revision was merged to the branch mainline in revision 563.
  • Revision ID: monty@inaugust.com-20081027231948-3kl6ss04plbakqcr
Split some more things out of common_includes.h.

Show diffs side-by-side

added added

removed removed

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