MySQL 记录、页、索引的数据结构简析( 六 ) _MySQL

其中：

入参中包括 dict_index_t* index 与 dtuple_t* entry ，分别对应 ins_node_t->index 与 ins_node_t->entry，其中 entry 中保存索引的数据；
调用 btr_pcur_open 函数将 cursor 移动到索引上待插入的位置，也就是定位页与行，注意入参 mode = PAGE_CUR_LE；
调用 btr_cur_optimistic_insert 函数乐观插入。

btr_pcur_open 函数中调用 btr_cur_search_to_nth_level 函数用于自顶向下查找整个 B-tree 。

page_cursor = btr_cur_get_page_cur(cursor);// 初始的，获得索引的根节点（space_id，page_no） const ulintspace = dict_index_get_space(index); const page_size_t page_size(dict_table_page_size(index->table)); /* Start with the root page. */ // 从 dict_index_t 元信息中拿到 root page 在物理文件的 page no（默认是 4） page_id_tpage_id(space, dict_index_get_page(index));// 从 buffer_pool 中根据 page no 拿 page（buf_page_get_gen），buffer pool 模块会根据 page 是否被缓存来决定是从内存中还是磁盘中读取 ， 并根据加锁策略对 page 加锁 block = buf_page_get_gen(page_id, page_size, rw_latch, guess,buf_mode, file, line, mtr); tree_blocks[n_blocks] = block;/* Search for complete index fields. */up_bytes = low_bytes = 0;// 对 page 内部的 record list 进行二分搜索 (page_cur_search_with_match)// page_cur_search_with_match：在一个数据页内“二分查找”（使用数据页中的 directory slot），定位到 recordpage_cur_search_with_match(block, index, tuple, page_mode, &up_match,&low_match, page_cursor,need_path ? cursor->rtr_info : NULL);

其中：

调用 buf_page_get_gen 函数根据 page no 获取 page（block），如果 page 在 buffer poo 中就直接读取，否则从文件读取到 buffer pool 中；
调用 page_cur_search_with_match 函数在 page 内部首先通过 Page Directory 二分查找确定 slot，然后线性查找确定行 record，其中 mode = PAGE_CUR_LE。

/* Perform binary search until the lower and upper limit directory slots come to the distance 1 of each other */// 在索引页内查找对于指定的 tuple，满足某种条件（依赖于传入的 mode，比如 PAGE_CUR_L）的 record // PAGE_CUR_G（>），PAGE_CUR_GE（>=），PAGE_CUR_L（<），PAGE_CUR_LE（<=） // 1. 二分查找 // 在稀疏的 Page Directory 内使用二分查找 low = 0; up = page_dir_get_n_slots(page) - 1;/* Perform linear search until the upper and lower records come to distance 1 of each other. */ // 二分查找结束后，low / up是临近的两个 slot，这两个 slot 指向的 record 记为// low_rec 和 up_rec，满足：low_rec <= tuple <= up_rec，切记 tuple 为待插入的（逻辑）记录// 2. 线性查找 ， 渐渐夹逼// 在两个相邻的 directory 内，进行线性查找 。线性查找的实现即不断"增大 low"，"减小 up"

其中：

二分查找与线性查找过程中都需要比较大?。?咛宓饔?cmp_dtuple_rec_with_match_low 函数比较物理记录与逻辑记录的大小。

// storage/innobase/rem/rem0cmp.cc/** Compare a data tuple to a physical record.@param[in] dtuple data tuple@param[in] rec B-tree record@param[in] offsets rec_get_offsets(rec)@param[in] n_cmp number of fields to compare@param[in,out] matched_fields number of completely matched fields@return the comparison result of dtuple and rec@retval 0 if dtuple is equal to rec@retval negative if dtuple is less than rec@retval positive if dtuple is greater than rec */intcmp_dtuple_rec_with_match_low( const dtuple_t* dtuple,const rec_t* rec, const ulint* offsets, ulintn_cmp, ulint*matched_fields){/* Match fields in a loop */// 遍历记录的每个字段 for (; cur_field < n_cmp; cur_field++) {// 获取逻辑记录const dfield_t* dtuple_field= dtuple_get_nth_field(dtuple, cur_field);// 将逻辑记录转换为物理记录const byte* dtuple_b_ptr= static_cast<const byte*>(dfield_get_data(dtuple_field));// 根据 offset 获取物理记录rec_b_ptr = rec_get_nth_field(rec, offsets, cur_field,&rec_f_len);// 比较大小ret = cmp_data(type->mtype, type->prtype,dtuple_b_ptr, dtuple_f_len,rec_b_ptr, rec_f_len);if (ret) {goto order_resolved;}}}

其中：