btr0btr.h
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:15k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /******************************************************
  2. The B-tree
  3. (c) 1994-1996 Innobase Oy
  4. Created 6/2/1994 Heikki Tuuri
  5. *******************************************************/
  6. #ifndef btr0btr_h
  7. #define btr0btr_h
  8. #include "univ.i"
  9. #include "dict0dict.h"
  10. #include "data0data.h"
  11. #include "page0cur.h"
  12. #include "rem0rec.h"
  13. #include "mtr0mtr.h"
  14. #include "btr0types.h"
  15. /* Maximum record size which can be stored on a page, without using the
  16. special big record storage structure */
  17. #define BTR_PAGE_MAX_REC_SIZE (UNIV_PAGE_SIZE / 2 - 200)
  18. /* Maximum key size in a B-tree: the records on non-leaf levels must be
  19. shorter than this */
  20. #define BTR_PAGE_MAX_KEY_SIZE 1024
  21. /* If data in page drops below this limit, we try to compress it.
  22. NOTE! The value has to be > 2 * BTR_MAX_KEY_SIZE */
  23. #define BTR_COMPRESS_LIMIT (UNIV_PAGE_SIZE / 4 + 1);
  24. /* Latching modes for the search function (in btr0cur.*) */
  25. #define BTR_SEARCH_LEAF RW_S_LATCH
  26. #define BTR_MODIFY_LEAF RW_X_LATCH
  27. #define BTR_NO_LATCHES RW_NO_LATCH
  28. #define BTR_MODIFY_TREE 33
  29. #define BTR_CONT_MODIFY_TREE 34
  30. #define BTR_SEARCH_PREV 35
  31. #define BTR_MODIFY_PREV 36
  32. /* If this is ORed to the latch mode, it means that the search tuple will be
  33. inserted to the index, at the searched position */
  34. #define BTR_INSERT 512
  35. /* This flag ORed to latch mode says that we do the search in query
  36. optimization */
  37. #define BTR_ESTIMATE 1024
  38. /* This flag ORed to latch mode says that we can ignore possible
  39. UNIQUE definition on secondary indexes when we decide if we can use the
  40. insert buffer to speed up inserts */
  41. #define BTR_IGNORE_SEC_UNIQUE 2048
  42. /******************************************************************
  43. Gets the root node of a tree and x-latches it. */
  44. page_t*
  45. btr_root_get(
  46. /*=========*/
  47. /* out: root page, x-latched */
  48. dict_tree_t* tree, /* in: index tree */
  49. mtr_t* mtr); /* in: mtr */
  50. /******************************************************************
  51. Gets a buffer page and declares its latching order level. */
  52. UNIV_INLINE
  53. page_t*
  54. btr_page_get(
  55. /*=========*/
  56. ulint space, /* in: space id */
  57. ulint page_no, /* in: page number */
  58. ulint mode, /* in: latch mode */
  59. mtr_t* mtr); /* in: mtr */
  60. /******************************************************************
  61. Gets the index id field of a page. */
  62. UNIV_INLINE
  63. dulint
  64. btr_page_get_index_id(
  65. /*==================*/
  66. /* out: index id */
  67. page_t* page); /* in: index page */
  68. /************************************************************
  69. Gets the node level field in an index page. */
  70. UNIV_INLINE
  71. ulint
  72. btr_page_get_level_low(
  73. /*===================*/
  74. /* out: level, leaf level == 0 */
  75. page_t* page); /* in: index page */
  76. /************************************************************
  77. Gets the node level field in an index page. */
  78. UNIV_INLINE
  79. ulint
  80. btr_page_get_level(
  81. /*===============*/
  82. /* out: level, leaf level == 0 */
  83. page_t* page, /* in: index page */
  84. mtr_t* mtr); /* in: mini-transaction handle */
  85. /************************************************************
  86. Gets the next index page number. */
  87. UNIV_INLINE
  88. ulint
  89. btr_page_get_next(
  90. /*==============*/
  91. /* out: next page number */
  92. page_t* page, /* in: index page */
  93. mtr_t* mtr); /* in: mini-transaction handle */
  94. /************************************************************
  95. Gets the previous index page number. */
  96. UNIV_INLINE
  97. ulint
  98. btr_page_get_prev(
  99. /*==============*/
  100. /* out: prev page number */
  101. page_t* page, /* in: index page */
  102. mtr_t* mtr); /* in: mini-transaction handle */
  103. /*****************************************************************
  104. Gets pointer to the previous user record in the tree. It is assumed
  105. that the caller has appropriate latches on the page and its neighbor. */
  106. rec_t*
  107. btr_get_prev_user_rec(
  108. /*==================*/
  109. /* out: previous user record, NULL if there is none */
  110. rec_t* rec, /* in: record on leaf level */
  111. mtr_t* mtr); /* in: mtr holding a latch on the page, and if
  112. needed, also to the previous page */
  113. /*****************************************************************
  114. Gets pointer to the next user record in the tree. It is assumed
  115. that the caller has appropriate latches on the page and its neighbor. */
  116. rec_t*
  117. btr_get_next_user_rec(
  118. /*==================*/
  119. /* out: next user record, NULL if there is none */
  120. rec_t* rec, /* in: record on leaf level */
  121. mtr_t* mtr); /* in: mtr holding a latch on the page, and if
  122. needed, also to the next page */
  123. /******************************************************************
  124. Releases the latch on a leaf page and bufferunfixes it. */
  125. UNIV_INLINE
  126. void
  127. btr_leaf_page_release(
  128. /*==================*/
  129. page_t* page, /* in: page */
  130. ulint latch_mode, /* in: BTR_SEARCH_LEAF or BTR_MODIFY_LEAF */
  131. mtr_t* mtr); /* in: mtr */
  132. /******************************************************************
  133. Gets the child node file address in a node pointer. */
  134. UNIV_INLINE
  135. ulint
  136. btr_node_ptr_get_child_page_no(
  137. /*===========================*/
  138.     /* out: child node address */
  139. rec_t* rec); /* in: node pointer record */
  140. /****************************************************************
  141. Creates the root node for a new index tree. */
  142. ulint
  143. btr_create(
  144. /*=======*/
  145. /* out: page number of the created root, FIL_NULL if
  146. did not succeed */
  147. ulint type, /* in: type of the index */
  148. ulint space, /* in: space where created */
  149. dulint index_id,/* in: index id */
  150. mtr_t* mtr); /* in: mini-transaction handle */
  151. /****************************************************************
  152. Frees a B-tree except the root page, which MUST be freed after this
  153. by calling btr_free_root. */
  154. void
  155. btr_free_but_not_root(
  156. /*==================*/
  157. ulint space, /* in: space where created */
  158. ulint root_page_no); /* in: root page number */
  159. /****************************************************************
  160. Frees the B-tree root page. Other tree MUST already have been freed. */
  161. void
  162. btr_free_root(
  163. /*==========*/
  164. ulint space, /* in: space where created */
  165. ulint root_page_no, /* in: root page number */
  166. mtr_t* mtr); /* in: a mini-transaction which has already
  167. been started */
  168. /*****************************************************************
  169. Makes tree one level higher by splitting the root, and inserts
  170. the tuple. It is assumed that mtr contains an x-latch on the tree.
  171. NOTE that the operation of this function must always succeed,
  172. we cannot reverse it: therefore enough free disk space must be
  173. guaranteed to be available before this function is called. */
  174. rec_t*
  175. btr_root_raise_and_insert(
  176. /*======================*/
  177. /* out: inserted record */
  178. btr_cur_t* cursor, /* in: cursor at which to insert: must be
  179. on the root page; when the function returns,
  180. the cursor is positioned on the predecessor
  181. of the inserted record */
  182. dtuple_t* tuple, /* in: tuple to insert */
  183. mtr_t* mtr); /* in: mtr */
  184. /*****************************************************************
  185. Reorganizes an index page. */
  186. void
  187. btr_page_reorganize(
  188. /*================*/
  189. page_t* page, /* in: page to be reorganized */
  190. mtr_t* mtr); /* in: mtr */
  191. /*****************************************************************
  192. Decides if the page should be split at the convergence point of
  193. inserts converging to left. */
  194. ibool
  195. btr_page_get_split_rec_to_left(
  196. /*===========================*/
  197. /* out: TRUE if split recommended */
  198. btr_cur_t* cursor, /* in: cursor at which to insert */
  199. rec_t** split_rec);/* out: if split recommended,
  200. the first record on upper half page,
  201. or NULL if tuple should be first */
  202. /*****************************************************************
  203. Decides if the page should be split at the convergence point of
  204. inserts converging to right. */
  205. ibool
  206. btr_page_get_split_rec_to_right(
  207. /*============================*/
  208. /* out: TRUE if split recommended */
  209. btr_cur_t* cursor, /* in: cursor at which to insert */
  210. rec_t** split_rec);/* out: if split recommended,
  211. the first record on upper half page,
  212. or NULL if tuple should be first */
  213. /*****************************************************************
  214. Splits an index page to halves and inserts the tuple. It is assumed
  215. that mtr holds an x-latch to the index tree. NOTE: the tree x-latch
  216. is released within this function! NOTE that the operation of this
  217. function must always succeed, we cannot reverse it: therefore
  218. enough free disk space must be guaranteed to be available before
  219. this function is called. */
  220. rec_t*
  221. btr_page_split_and_insert(
  222. /*======================*/
  223. /* out: inserted record; NOTE: the tree
  224. x-latch is released! NOTE: 2 free disk
  225. pages must be available! */
  226. btr_cur_t* cursor, /* in: cursor at which to insert; when the
  227. function returns, the cursor is positioned
  228. on the predecessor of the inserted record */
  229. dtuple_t* tuple, /* in: tuple to insert */
  230. mtr_t* mtr); /* in: mtr */
  231. /***********************************************************
  232. Inserts a data tuple to a tree on a non-leaf level. It is assumed
  233. that mtr holds an x-latch on the tree. */
  234. void
  235. btr_insert_on_non_leaf_level(
  236. /*=========================*/
  237. dict_tree_t* tree, /* in: tree */
  238. ulint level, /* in: level, must be > 0 */
  239. dtuple_t* tuple, /* in: the record to be inserted */
  240. mtr_t* mtr); /* in: mtr */
  241. /********************************************************************
  242. Sets a record as the predefined minimum record. */
  243. void
  244. btr_set_min_rec_mark(
  245. /*=================*/
  246. rec_t* rec, /* in: record */
  247. mtr_t* mtr); /* in: mtr */
  248. /*****************************************************************
  249. Deletes on the upper level the node pointer to a page. */
  250. void
  251. btr_node_ptr_delete(
  252. /*================*/
  253. dict_tree_t* tree, /* in: index tree */
  254. page_t* page, /* in: page whose node pointer is deleted */
  255. mtr_t* mtr); /* in: mtr */
  256. /****************************************************************
  257. Checks that the node pointer to a page is appropriate. */
  258. ibool
  259. btr_check_node_ptr(
  260. /*===============*/
  261. /* out: TRUE */
  262. dict_tree_t* tree, /* in: index tree */
  263. page_t* page, /* in: index page */
  264. mtr_t* mtr); /* in: mtr */
  265. /*****************************************************************
  266. Tries to merge the page first to the left immediate brother if such a
  267. brother exists, and the node pointers to the current page and to the
  268. brother reside on the same page. If the left brother does not satisfy these
  269. conditions, looks at the right brother. If the page is the only one on that
  270. level lifts the records of the page to the father page, thus reducing the
  271. tree height. It is assumed that mtr holds an x-latch on the tree and on the
  272. page. If cursor is on the leaf level, mtr must also hold x-latches to
  273. the brothers, if they exist. NOTE: it is assumed that the caller has reserved
  274. enough free extents so that the compression will always succeed if done! */
  275. void
  276. btr_compress(
  277. /*=========*/
  278. btr_cur_t* cursor, /* in: cursor on the page to merge or lift;
  279. the page must not be empty: in record delete
  280. use btr_discard_page if the page would become
  281. empty */
  282. mtr_t* mtr); /* in: mtr */
  283. /*****************************************************************
  284. Discards a page from a B-tree. This is used to remove the last record from
  285. a B-tree page: the whole page must be removed at the same time. This cannot
  286. be used for the root page, which is allowed to be empty. */
  287. void
  288. btr_discard_page(
  289. /*=============*/
  290. btr_cur_t* cursor, /* in: cursor on the page to discard: not on
  291. the root page */
  292. mtr_t* mtr); /* in: mtr */
  293. /********************************************************************
  294. Parses the redo log record for setting an index record as the predefined
  295. minimum record. */
  296. byte*
  297. btr_parse_set_min_rec_mark(
  298. /*=======================*/
  299. /* out: end of log record or NULL */
  300. byte* ptr, /* in: buffer */
  301. byte* end_ptr,/* in: buffer end */
  302. page_t* page, /* in: page or NULL */
  303. mtr_t* mtr); /* in: mtr or NULL */
  304. /***************************************************************
  305. Parses a redo log record of reorganizing a page. */
  306. byte*
  307. btr_parse_page_reorganize(
  308. /*======================*/
  309. /* out: end of log record or NULL */
  310. byte* ptr, /* in: buffer */
  311. byte* end_ptr,/* in: buffer end */
  312. page_t* page, /* in: page or NULL */
  313. mtr_t* mtr); /* in: mtr or NULL */
  314. /******************************************************************
  315. Gets the number of pages in a B-tree. */
  316. ulint
  317. btr_get_size(
  318. /*=========*/
  319. /* out: number of pages */
  320. dict_index_t* index, /* in: index */
  321. ulint flag); /* in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
  322. /******************************************************************
  323. Allocates a new file page to be used in an index tree. NOTE: we assume
  324. that the caller has made the reservation for free extents! */
  325. page_t*
  326. btr_page_alloc(
  327. /*===========*/
  328. /* out: new allocated page, x-latched;
  329. NULL if out of space */
  330. dict_tree_t* tree, /* in: index tree */
  331. ulint hint_page_no, /* in: hint of a good page */
  332. byte file_direction, /* in: direction where a possible
  333. page split is made */
  334. ulint level, /* in: level where the page is placed
  335. in the tree */
  336. mtr_t* mtr); /* in: mtr */
  337. /******************************************************************
  338. Frees a file page used in an index tree. NOTE: cannot free field external
  339. storage pages because the page must contain info on its level. */
  340. void
  341. btr_page_free(
  342. /*==========*/
  343. dict_tree_t* tree, /* in: index tree */
  344. page_t* page, /* in: page to be freed, x-latched */
  345. mtr_t* mtr); /* in: mtr */
  346. /******************************************************************
  347. Frees a file page used in an index tree. Can be used also to BLOB
  348. external storage pages, because the page level 0 can be given as an
  349. argument. */
  350. void
  351. btr_page_free_low(
  352. /*==============*/
  353. dict_tree_t* tree, /* in: index tree */
  354. page_t* page, /* in: page to be freed, x-latched */
  355. ulint level, /* in: page level */
  356. mtr_t* mtr); /* in: mtr */
  357. /*****************************************************************
  358. Prints size info of a B-tree. */
  359. void
  360. btr_print_size(
  361. /*===========*/
  362. dict_tree_t* tree); /* in: index tree */
  363. /******************************************************************
  364. Prints directories and other info of all nodes in the tree. */
  365. void
  366. btr_print_tree(
  367. /*===========*/
  368. dict_tree_t* tree, /* in: tree */
  369. ulint width); /* in: print this many entries from start
  370. and end */
  371. /****************************************************************
  372. Checks the size and number of fields in a record based on the definition of
  373. the index. */
  374. ibool
  375. btr_index_rec_validate(
  376. /*====================*/
  377. /* out: TRUE if ok */
  378. rec_t* rec, /* in: index record */
  379. dict_index_t* index, /* in: index */
  380. ibool dump_on_error); /* in: TRUE if the function
  381. should print hex dump of record
  382. and page on error */
  383. /******************************************************************
  384. Checks the consistency of an index tree. */
  385. ibool
  386. btr_validate_tree(
  387. /*==============*/
  388. /* out: TRUE if ok */
  389. dict_tree_t* tree); /* in: tree */
  390. #define BTR_N_LEAF_PAGES  1
  391. #define BTR_TOTAL_SIZE 2
  392. #ifndef UNIV_NONINL
  393. #include "btr0btr.ic"
  394. #endif
  395. #endif