← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

  • Committer: Brian Aker
  • Date: 2010-12-18 18:24:57 UTC
  • mfrom: (1999.6.3 trunk)
  • Revision ID: brian@tangent.org-20101218182457-yi1wd0so2hml1k1w
Merge in Lee's copyright header fix

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
 
 
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
 
page_t*
71
 
btr_page_get(
72
 
/*=========*/
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. */
79
 
UNIV_INLINE
80
 
dulint
81
 
btr_page_get_index_id(
82
 
/*==================*/
83
 
                                /* out: index id */
84
 
        page_t*         page);  /* in: index page */
85
 
/************************************************************
86
 
Gets the node level field in an index page. */
87
 
UNIV_INLINE
88
 
ulint
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. */
95
 
UNIV_INLINE
96
 
ulint
97
 
btr_page_get_level(
98
 
/*===============*/
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. */
104
 
UNIV_INLINE
105
 
ulint
106
 
btr_page_get_next(
107
 
/*==============*/
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. */
113
 
UNIV_INLINE
114
 
ulint
115
 
btr_page_get_prev(
116
 
/*==============*/
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. */
123
 
 
124
 
rec_t*
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. */
134
 
 
135
 
rec_t*
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. */
144
 
UNIV_INLINE
145
 
void
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. */
153
 
UNIV_INLINE
154
 
ulint
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. */
162
 
 
163
 
ulint
164
 
btr_create(
165
 
/*=======*/
166
 
                        /* out: page number of the created root, FIL_NULL if
167
 
                        did not succeed */
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. */
176
 
 
177
 
void
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. */
184
 
 
185
 
void
186
 
btr_free_root(
187
 
/*==========*/
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
191
 
                                been started */
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. */
198
 
 
199
 
rec_t*
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. */
211
 
 
212
 
void
213
 
btr_page_reorganize(
214
 
/*================*/
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. */
221
 
 
222
 
ibool
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. */
233
 
 
234
 
ibool
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. */
249
 
 
250
 
rec_t*
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. */
264
 
 
265
 
void
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. */
274
 
 
275
 
void
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. */
283
 
 
284
 
void
285
 
btr_node_ptr_delete(
286
 
/*================*/
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 */
290
 
#ifdef UNIV_DEBUG
291
 
/****************************************************************
292
 
Checks that the node pointer to a page is appropriate. */
293
 
 
294
 
ibool
295
 
btr_check_node_ptr(
296
 
/*===============*/
297
 
                                /* out: TRUE */
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! */
312
 
void
313
 
btr_compress(
314
 
/*=========*/
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
318
 
                                empty */
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. */
324
 
 
325
 
void
326
 
btr_discard_page(
327
 
/*=============*/
328
 
        btr_cur_t*      cursor, /* in: cursor on the page to discard: not on
329
 
                                the root page */
330
 
        mtr_t*          mtr);   /* in: mtr */
331
 
/********************************************************************
332
 
Parses the redo log record for setting an index record as the predefined
333
 
minimum record. */
334
 
 
335
 
byte*
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. */
346
 
 
347
 
byte*
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. */
358
 
 
359
 
ulint
360
 
btr_get_size(
361
 
/*=========*/
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! */
368
 
 
369
 
page_t*
370
 
btr_page_alloc(
371
 
/*===========*/
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
379
 
                                        in the tree */
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. */
384
 
 
385
 
void
386
 
btr_page_free(
387
 
/*==========*/
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
394
 
argument. */
395
 
 
396
 
void
397
 
btr_page_free_low(
398
 
/*==============*/
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. */
406
 
 
407
 
void
408
 
btr_print_size(
409
 
/*===========*/
410
 
        dict_index_t*   index); /* in: index tree */
411
 
/******************************************************************
412
 
Prints directories and other info of all nodes in the index. */
413
 
 
414
 
void
415
 
btr_print_index(
416
 
/*============*/
417
 
        dict_index_t*   index,  /* in: index */
418
 
        ulint           width); /* in: print this many entries from start
419
 
                                and end */
420
 
#endif /* UNIV_BTR_PRINT */
421
 
/****************************************************************
422
 
Checks the size and number of fields in a record based on the definition of
423
 
the index. */
424
 
 
425
 
ibool
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
433
 
                                        and page on error */
434
 
/******************************************************************
435
 
Checks the consistency of an index tree. */
436
 
 
437
 
ibool
438
 
btr_validate_index(
439
 
/*===============*/
440
 
                                /* out: TRUE if ok */
441
 
        dict_index_t*   index,  /* in: index */
442
 
        trx_t*          trx);   /* in: transaction or NULL */
443
 
 
444
 
#define BTR_N_LEAF_PAGES        1
445
 
#define BTR_TOTAL_SIZE          2
446
 
 
447
 
#ifndef UNIV_NONINL
448
 
#include "btr0btr.ic"
449
 
#endif
450
 
 
451
 
#endif