innodb空间索引介绍

innodb支持空间索引，但很少有关于innodb关于空间索引的实现的介绍文章，本篇文章主要目的是介绍innodb关于空间索引的源码介绍，知其所以然。空间索引本质上是二级索引中的一种，基于R树实现。

innodb索引主要是基于B+树实现，B+树是一棵平衡树，是把一维直线分为若干段线段，当我们查找满足某个要求的点的时候，只要去查找它所属的线段即可。这种思想其实就是先找一个大的空间，再逐步缩小所要查找的空间，最终在一个自己设定的最小不可分空间内找出满足要求的解。B+树是解决低纬度数据（通常一维，也就是一个数据维度上进行比较），R树很好的解决了高维空间搜索问题。它把B树的思想很好的扩展到了多维空间，采用了B树分割空间的思想（如果B树在一维的线段进行分割，R树就是在二维甚至多维度的空间），并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，R树就是一棵用来存储高维数据的平衡树。R树的介绍我们在此不过多展开介绍，详细可查询相关文档。

源码实现分析

innodb空间索引的代码实现主要聚集在这几个文件：include/gis0geo.h include/gis0rtree.h include/gis0tree.ic include/gis0type.h gis/gis0geo.cc gis/gis0rtee.cc gis/gis0sea.cc，代码量不大，大概是几千行，相对比较容易阅读。本篇文章下面围绕空间索引rec的定位，查询，插入，更新，删除等来做介绍，主要介绍核心代码逻辑。代码基于mysql 8.0.30。

rec定位

空间索引的rec定位不仅是在查询的时候使用，在其他DML操作前也需要将cursor定位到对应的rec位置，代码实现上主要是结合数据结构rtr_info_t，由函数btr_cur_search_to_nth_level进行逐层迭代查询，在非叶子节点调用rtr_cur_search_with_match函数，遍历对应level的page上所有rec，将cursor定位到匹配的rec，进而往下层继续遍历，在叶子节点，调用page_cur_search_with_match函数，类似其他索引使用二分法定位。我们在此着重说明数据结构rtr_info_t和函数btr_cur_search_to_nth_level和rtr_cur_search_with_match在空间索引定位上的实现。

rtr_info_t数据结构介绍

  1. // rtr_info_t数据结构主要用来记录定位rec过程中匹配的page或者rec信息，
  2. // 主要被使用在btr_cur_t中跟踪cursor定位rtree中的一些信息，以及用在
  3. // dict_index_t中跟踪所有当前rtree在进行的查询请求相关信息rtr_info_track_t
  4. typedef struct rtr_info {
  5.   rtr_node_path_t *path; // vector保存所有匹配的内部节点page         
  6.   rtr_node_path_t *parent_path; // vector 保存查询中匹配的 parent pages
  7.   matched_rec_t *matches; // 保存所有匹配的叶子节点记录
  8.   ib_mutex_t rtr_path_mutex; /*!< mutex protect the "path" vector */
  9.   buf_block_t *tree_blocks[RTR_MAX_LEVELS + RTR_LEAF_LATCH_NUM];
  10.   /*!< tracking pages that would be locked at leaf level, for future free */
  11.   ulint tree_savepoints[RTR_MAX_LEVELS + RTR_LEAF_LATCH_NUM];
  12.   /*!< savepoint used to release latches/blocks on each level and leaf level */
  13.   rtr_mbr_t mbr;       /*!< the search MBR */
  14.   que_thr_t *thr;      /*!< the search thread */
  15.   mem_heap_t *heap;    /*!< memory heap */
  16.   btr_cur_t *cursor;   /*!< cursor used for search */
  17.   dict_index_t *index; /*!< index it is searching */
  18.   bool need_prdt_lock; /*!< whether we will need predicate lock the tree */
  19.   bool need_page_lock; /*!< whether we will need predicate page lock the tree */
  20.   bool allocated; /*!< whether this structure is allocate or on stack */
  21.   bool mbr_adj;   /*!< whether mbr will need to be enlarged for an insertion operation */
  22.   bool fd_del;    /*!< found deleted row */
  23.   const dtuple_t *search_tuple; /*!< search tuple being used */
  24.   page_cur_mode_t search_mode; /*!< current search mode */
  25.   bool *is_dup; /*!< whether the current rec is a duplicate record. */
  26. } rtr_info_t;

btr_cur_search_to_nth_level 函数关于空间索引rtree定位

  1. // btr_cur_search_to_nth_level 函数是Btree定位rec的关键函数，
  2. // 空间索引实现的Rtree在逐层迭代上同Btree类似，所以也由该函数完成各种的遍历
  3. // 主要是一些初始化，search mode调整，谓词锁添加，判断是否要调整rtr_inof.mbr，
  4. // 及将每层对应page的定位交给rtr_cur_search_with_match 和 page_cur_search_with_match
  5. // 该函数非空间索引相关实现可参考http://mysql.taobao.org/monthly/2021/07/02/
  6. // 下面是该函数的注释版本，主要是空间索引相关的关键代码
  7. void btr_cur_search_to_nth_level(
  8.     dict_index_t *index,   /*!< in: index */
  9.     ulint level,           /*!< in: the tree level of search */
  10.     const dtuple_t *tuple, /*!< in: data tuple; NOTE: n_fields_cmp in
  11.                            tuple must be set so that it cannot get
  12.                            compared to the node ptr page number field! */
  13.     page_cur_mode_t mode,  /*!< in: PAGE_CUR_L, ...;
  14.                            Inserts should always be made using
  15.                            PAGE_CUR_LE to search the position! */
  16.     ...)
  17. {
  18.   const space_id_t space = dict_index_get_space(index);
  19.   const page_size_t page_size(dict_table_page_size(index->table));
  20.   /* Start with the root page. */
  21.   page_id_t page_id(space, dict_index_get_page(index));
  23. // 循环、逐层的查找，直至达到传入的层数 level，一般是0（即叶子节点）
  24. // 此处只分析空间索引Spatial index的部分
  25. search_loop:
  26.   //获取每层对应page
  27.   page = buf_block_get_frame(block);
  29.   // root节点，进行一些初始化操作
  30.   // 对空间索引rtree split sequence no rtr_ssn进行初始化
  31.   // 将待定位记录的MBR保存到cursor rtr_info
  32.   if (UNIV_UNLIKELY(height == ULINT_UNDEFINED)) {
  33.     if (dict_index_is_spatial(index)) {
  34.       node_seq_t seq_no = rtr_get_current_ssn_id(index);
  35.       /* If SSN in memory is not initialized, fetch
  36.       it from root page */
  37.       if (seq_no < 1) {
  38.         node_seq_t root_seq_no;
  39.         root_seq_no = page_get_ssn_id(page);
  40.         mutex_enter(&(index->rtr_ssn.mutex));
  41.         index->rtr_ssn.seq_no = root_seq_no + 1;
  42.         mutex_exit(&(index->rtr_ssn.mutex));
  43.       }
  44.       /* Save the MBR */
  45.       cursor->rtr_info->thr = cursor->thr;
  46.       rtr_get_mbr_from_tuple(tuple, &cursor->rtr_info->mbr);
  47.     }
  48.   }
  50.   // search mode调整:
  51.   // 目标level，叶子节点调整为PAGE_CUR_LE
  52.   // 非目标level搜索所有子树，看是否“contain”相应查询MBR
  53.   if (dict_index_is_spatial(index)) {
  54.     /* Remember the page search mode */
  55.     search_mode = page_mode;
  56.     // 查询定位 search mode调整
  57.     if (page_mode == PAGE_CUR_RTREE_LOCATE && level == height) {
  58.       if (level == 0) {
  59.         page_mode = PAGE_CUR_LE;
  60.       } else {
  61.         page_mode = PAGE_CUR_RTREE_GET_FATHER;
  62.       }
  63.     }
  64.     // 插入记录定位 search mode调整
  65.     if (page_mode == PAGE_CUR_RTREE_INSERT) {
  66.       page_mode = (level == height) ? PAGE_CUR_LE : PAGE_CUR_RTREE_INSERT;
  67.     }
  68.   }
  70.   // page内定位记录
  71.   // 非目标level使用rtr_cur_search_with_match
  72.   // 目标level使用page_cur_search_with_match
  73.   if (dict_index_is_spatial(index) && page_mode >= PAGE_CUR_CONTAIN) {
  74.     //非目标level搜索定位
  75.     found = rtr_cur_search_with_match(block, index, tuple, page_mode,
  76.                                       page_cursor, cursor->rtr_info);
  77.     /* Need to use BTR_MODIFY_TREE to do the MBR adjustment */
  78.     if (search_mode == PAGE_CUR_RTREE_INSERT && cursor->rtr_info->mbr_adj) {
  79.       if (latch_mode & BTR_MODIFY_LEAF) {
  80.         /* Parent MBR needs updated, should retry
  81.         with BTR_MODIFY_TREE */
  82.         goto func_exit;
  83.       } else if (latch_mode & BTR_MODIFY_TREE) {
  84.         rtree_parent_modified = true;
  85.         cursor->rtr_info->mbr_adj = false;
  86.         mbr_adj = true;
  87.       } else {
  88.         ut_d(ut_error);
  89.       }
  90.     }
  91.     if (found && page_mode == PAGE_CUR_RTREE_GET_FATHER) {
  92.       cursor->low_match = DICT_INDEX_SPATIAL_NODEPTR_SIZE + 1;
  93.     }
  94.   } else {
  95.     // 目标level搜索定位
  96.     /* Search for complete index fields. */
  97.     up_bytes = low_bytes = 0;
  98.     page_cur_search_with_match(block, index, tuple, page_mode, &up_match,
  99.                                &low_match, page_cursor,
  100.                                need_path ? cursor->rtr_info : nullptr);
  101.   }
  103.   // 在serializable isolation时添加谓词锁Predicate lock
  104.   if (dict_index_is_spatial(index) && cursor->rtr_info->need_prdt_lock &&
  105.       mode != PAGE_CUR_RTREE_INSERT && mode != PAGE_CUR_RTREE_LOCATE &&
  106.       mode >= PAGE_CUR_CONTAIN) {
  107.     trx_t *trx = thr_get_trx(cursor->thr);
  108.     lock_prdt_t prdt;
  109.     trx_mutex_enter(trx);
  110.     lock_init_prdt_from_mbr(&prdt, &cursor->rtr_info->mbr, mode,
  111.                             trx->lock.lock_heap);
  112.     trx_mutex_exit(trx);
  113.     if (rw_latch == RW_NO_LATCH && height != 0) {
  114.       rw_lock_s_lock(&block->lock, UT_LOCATION_HERE);
  115.     }
  116.     lock_prdt_lock(block, &prdt, index, LOCK_S, LOCK_PREDICATE, cursor->thr);
  117.     if (rw_latch == RW_NO_LATCH && height != 0) {
  118.       rw_lock_s_unlock(&(block->lock));
  119.     }
  120.   }
  122.   if (level != height) {
  123.     node_ptr = page_cur_get_rec(page_cursor);
  125.     if (dict_index_is_spatial(index)) {
  126.      // supremum rec 直接返回
  127.       if (page_rec_is_supremum(node_ptr)) {
  128.         cursor->low_match = 0;
  129.         cursor->up_match = 0;
  130.         goto func_exit;
  131.       }
  133.       /* If we are doing insertion or record locating,
  134.       remember the tree nodes we visited */
  135.       if (page_mode == PAGE_CUR_RTREE_INSERT ||
  136.           (search_mode == PAGE_CUR_RTREE_LOCATE &&
  137.            (latch_mode != BTR_MODIFY_LEAF))) {
  139.         /* Store the parent cursor location */
  140.         rtr_store_parent_path(block, cursor, latch_mode, height + 1, mtr);
  141.         if (page_mode == PAGE_CUR_RTREE_INSERT) {
  142.           btr_pcur_t *r_cursor =
  143.               rtr_get_parent_cursor(cursor, height + 1, true);
  144.           node_ptr = r_cursor->get_rec();
  145.         }
  146.       }
  147.       page_mode = search_mode;
  148.     }
  150.     // 往下层继续查找
  151.     page_id.reset(space, btr_node_ptr_get_child_page_no(node_ptr, offsets));
  153.     if (dict_index_is_spatial(index) && page_mode >= PAGE_CUR_CONTAIN &&
  154.         page_mode != PAGE_CUR_RTREE_INSERT) {
  155.       rtr_node_path_t *path = cursor->rtr_info->path;
  156.       if (!path->empty() && found) {
  157.         path->pop_back();
  158.       }
  159.     }
  161.     goto search_loop;
  162.   }
  164.   /* For spatial index, remember  what blocks are still latched */
  165.   if (dict_index_is_spatial(index) &&
  166.       (latch_mode == BTR_MODIFY_TREE || latch_mode == BTR_MODIFY_LEAF)) {
  167.     for (ulint i = 0; i < n_releases; i++) {
  168.       cursor->rtr_info->tree_blocks[i] = nullptr;
  169.       cursor->rtr_info->tree_savepoints[i] = 0;
  170.     }
  172.     for (ulint i = n_releases; i <= n_blocks; i++) {
  173.       cursor->rtr_info->tree_blocks[i] = tree_blocks[i];
  174.       cursor->rtr_info->tree_savepoints[i] = tree_savepoints[i];
  175.     }
  176.   }
  178. func_exit:
  180.   if (mbr_adj) {
  181.     /* remember that we will need to adjust parent MBR */
  182.     cursor->rtr_info->mbr_adj = true;
  183.   }
  184. }

rtr_cur_search_with_match 空间索引page内rec定位

  1. /** Searches the right position in rtree for a page cursor.*/
  2. // rtr_cur_search_with_match 函数是定位rtree page内位置的主要函数，其实现就是遍历page内
  3. // 所有rec，判断遍历到的rec和要查询定位的rec的mbr是否满足某种关系，然后将page cursor定位到
  4. // 查询定位到的rec，并更新一些数据结构
  5. bool rtr_cur_search_with_match(const buf_block_t *block, dict_index_t *index,
  6.                                const dtuple_t *tuple, page_cur_mode_t mode,
  7.                                page_cur_t *cursor, rtr_info_t *rtr_info) {
  8.   // 判断是不是到叶子节点，初始rec为第一个rec
  9.   page = buf_block_get_frame(block);
  10.   is_leaf = page_is_leaf(page);
  11.   level = btr_page_get_level(page);
  12.   if (mode == PAGE_CUR_RTREE_LOCATE) {
  13.     mode = PAGE_CUR_WITHIN;
  14.   }
  15.   rec = page_dir_slot_get_rec(page_dir_get_nth_slot(page, 0));
  16.   last_rec = rec;
  17.   best_rec = rec;
  18.   if (page_rec_is_infimum(rec)) {
  19.     rec = page_rec_get_next_const(rec);
  20.   }
  22.   // 从前往后循环遍历所有rec来定位rec，直到supremum rec
  23.   while (!page_rec_is_supremum(rec)) {
  24.     // 非叶子节点定位rec
  25.     if (!is_leaf) {
  26.       switch (mode) {
  27.         ... ...
  28.         // 非叶子节点，插入rec场景，找到所有rec中让mbr增加最小的rec
  29.         case PAGE_CUR_RTREE_INSERT:
  30.           cmp = cmp_dtuple_rec_with_gis(tuple, rec, offsets, PAGE_CUR_WITHIN,
  31.                                         index->rtr_srs.get());
  32.           if (cmp != 0) {
  33.             double area{0.0};
  34.             increase = rtr_rec_cal_increase(tuple, rec, offsets, &area,
  35.                                             index->rtr_srs.get());
  36.             if (increase < least_inc) {
  37.               least_inc = increase;
  38.               best_rec = rec;
  39.             } else if (best_rec && best_rec == first_rec) {
  40.               /* if first_rec is set,
  41.               we will try to avoid it */
  42.               least_inc = increase;
  43.               best_rec = rec;
  44.             }
  45.           }
  46.           break;
  47.         case PAGE_CUR_RTREE_GET_FATHER:
  48.           cmp = cmp_dtuple_rec_with_gis_internal(tuple, rec, offsets,
  49.                                                  index->rtr_srs.get());
  50.           break;
  51.         default:
  52.           //有前面mode调整知查询定位rec走到这里，判断对应rec的mbr是否包含要查询的rec
  53.           cmp = cmp_dtuple_rec_with_gis(tuple, rec, offsets, mode,
  54.                                         index->rtr_srs.get());
  55.       }
  56.     } else {
  57.       cmp = cmp_dtuple_rec_with_gis(tuple, rec, offsets, mode,
  58.                                     index->rtr_srs.get());
  59.     }
  61.     //匹配到对应rec
  62.     if (cmp == 0) {
  63.       found = true;
  64.       // 如果定位到，非叶子节点则将匹配的node/rec 添加到rtr_info->path
  65.       // 叶子节点则添加到rtr_info->matches
  66.       if (rtr_info && mode != PAGE_CUR_RTREE_INSERT) {
  67.         if (!is_leaf) {
  68.           is_loc = (orig_mode == PAGE_CUR_RTREE_LOCATE ||
  69.                     orig_mode == PAGE_CUR_RTREE_GET_FATHER);
  70.           page_no = btr_node_ptr_get_child_page_no(rec, offsets);
  71.           rtr_non_leaf_stack_push(rtr_info->path, page_no, new_seq, level - 1,
  72.                                   0, nullptr, 0);
  73.           if (is_loc) {
  74.             rtr_non_leaf_insert_stack_push(index, rtr_info->parent_path, level,
  75.                                            page_no, block, rec, 0);
  76.           }
  77.         } else {
  78.           rtr_leaf_push_match_rec(rec, rtr_info, offsets, page_is_comp(page));
  79.         }
  80.         last_match_rec = rec;
  81.       } else {
  82.         /* This is the insertion case, it will break
  83.         once it finds the first MBR that can accomodate
  84.         the inserting rec */
  85.         break;
  86.       }
  87.     }
  89.     last_rec = rec;
  90.     //取下一条rec记录继续往后遍历
  91.     rec = page_rec_get_next_const(rec);
  92.   } //循环结束
  94.   // 页上所有rec都比较后，定位cursor到对应rec    
  95.   if (page_rec_is_supremum(rec)) {
  96.     if (!is_leaf) {
  97.       if (!found) {
  98.         /* No match case, if it is for insertion,
  99.         then we select the record that result in
  100.         least increased area */
  101.         if (mode == PAGE_CUR_RTREE_INSERT) {
  102.           child_no = btr_node_ptr_get_child_page_no(best_rec, offsets);
  103.           rtr_non_leaf_insert_stack_push(index, rtr_info->parent_path, level,
  104.                                          child_no, block, best_rec, least_inc);
  105.           page_cur_position(best_rec, block, cursor);
  106.           rtr_info->mbr_adj = true;
  107.         } else {
  108.           /* Position at the last rec of the
  109.           page, if it is not the leaf page */
  110.           page_cur_position(last_rec, block, cursor);
  111.         }
  112.       } else {
  113.         /* There are matching records, position
  114.         in the last matching records */
  115.         if (rtr_info) {
  116.           rec = last_match_rec;
  117.           page_cur_position(rec, block, cursor);
  118.         }
  119.       }
  120.     } else if (rtr_info) {
  121.       /* Leaf level, no match, position at the
  122.       last (supremum) rec */
  123.       if (!last_match_rec) {
  124.         page_cur_position(rec, block, cursor);
  125.         goto func_exit;
  126.       }
  128.       /* There are matched records */
  129.       matched_rec_t *match_rec = rtr_info->matches;
  130.       test_rec = match_rec->matched_recs->back();
  131.       /* Pop the last match record and position on it */
  132.       match_rec->matched_recs->pop_back();
  133.       page_cur_position(test_rec.r_rec, &match_rec->block, cursor);
  134.     }
  135.   } else {
  136.     if (mode == PAGE_CUR_RTREE_INSERT) {
  137.       child_no = btr_node_ptr_get_child_page_no(rec, offsets);
  138.       rtr_non_leaf_insert_stack_push(index, rtr_info->parent_path, level,
  139.                                      child_no, block, rec, 0);
  140.     } else if (rtr_info && found && !is_leaf) {
  141.       rec = last_match_rec;
  142.     }
  143.     page_cur_position(rec, block, cursor);
  144.   }
  146. func_exit:
  147.   return (found);
  148. }

插入

向有空间索引的表中插入数据时，主要的代码路径和其他普通记录基本一致，即先更新主键，然后再更新二级索引，空间索引是二级索引的一种，空间索引插入数据的代码主要是在row_ins_sec_index_entry_low，cursor定位到的位置是有足够的空间来存放插入的数据，则直接插入数据返回即可，如果没有足够的空间插入数据，则会导致rtree的split，rtree的split代码实现主要是函数rtr_page_split_and_insert。我们主要分析函数row_ins_sec_index_entry_low和rtr_page_split_and_insert实现

row_ins_sec_index_entry_low 空间索引插入数据

  1. // row_ins_sec_index_entry_low是完成二级索引数据插入的主要函数
  2. dberr_t row_ins_sec_index_entry_low(uint32_t flags, ulint mode,
  3.                                     dict_index_t *index,
  4.                                     mem_heap_t *offsets_heap, mem_heap_t *heap,
  5.                                     dtuple_t *entry, ... ...) {
  6.   // 初始化rtr_info，及定位rec
  7.   if (dict_index_is_spatial(index)) {
  8.     cursor.index = index;
  9.     // 初始化rtr_info并保存到cursor中，
  10.     rtr_init_rtr_info(&rtr_info, false, &cursor, index, false);
  11.     rtr_info_update_btr(&cursor, &rtr_info);
  13.     //通过btr_cur_search_to_nth_level定位cursor到对应rec
  14.     btr_cur_search_to_nth_level(index, 0, entry, PAGE_CUR_RTREE_INSERT,
  15.                                 search_mode, &cursor, 0, __FILE__, __LINE__,
  16.                                 &mtr);
  18.     // 需要改为悲观插入时，调整search mode重新定位rec
  19.     if (mode == BTR_MODIFY_LEAF && rtr_info.mbr_adj) {
  20.       mtr_commit(&mtr);
  21.       rtr_clean_rtr_info(&rtr_info, true);
  22.       rtr_init_rtr_info(&rtr_info, false, &cursor, index, false);
  23.       rtr_info_update_btr(&cursor, &rtr_info);
  25.       mtr_start(&mtr);
  26.       search_mode &= ~BTR_MODIFY_LEAF;
  27.       search_mode |= BTR_MODIFY_TREE;
  28.       btr_cur_search_to_nth_level(index, 0, entry, PAGE_CUR_RTREE_INSERT,
  29.                                   search_mode, &cursor, 0, __FILE__, __LINE__,
  30.                                   &mtr);
  31.       mode = BTR_MODIFY_TREE;
  32.     }
  33.   }
  35.   if (row_ins_must_modify_rec(&cursor)) {
  36.     // 通过修改去掉已有rec的delete mark插入数据
  37.     err = row_ins_sec_index_entry_by_modify(
  38.         flags, mode, &cursor, &offsets, offsets_heap, heap, entry, thr, &mtr);
  40.     if (err == DB_SUCCESS && dict_index_is_spatial(index) && rtr_info.mbr_adj) {
  41.       // 插入后调整插入路径节点的mbr范围
  42.       err = rtr_ins_enlarge_mbr(&cursor, &mtr);
  43.     }
  44.   } else {
  45.     rec_t *insert_rec;
  46.     big_rec_t *big_rec;
  48.     if (mode == BTR_MODIFY_LEAF) {
  49.       // 乐观插入
  50.       err = btr_cur_optimistic_insert(flags, &cursor, &offsets, &offsets_heap,
  51.                                       entry, &insert_rec, &big_rec, thr, &mtr);
  52.       if (err == DB_SUCCESS && dict_index_is_spatial(index) &&
  53.           rtr_info.mbr_adj) {
  54.         // 插入后调整插入路径节点的mbr范围
  55.         err = rtr_ins_enlarge_mbr(&cursor, &mtr);
  56.       }
  57.     } else {
  58.       // 先尝试乐观插入，失败后再尝试悲观插入
  59.       err = btr_cur_optimistic_insert(flags, &cursor, &offsets, &offsets_heap,
  60.                                       entry, &insert_rec, &big_rec, thr, &mtr);
  61.       if (err == DB_FAIL) {
  62.         err = btr_cur_pessimistic_insert(flags, &cursor, &offsets, &offsets_heap,
  63.                                        entry, &insert_rec, &big_rec, thr, &mtr);
  64.       }
  65.       if (err == DB_SUCCESS && dict_index_is_spatial(index) &&
  66.           rtr_info.mbr_adj) {
  67.         // 插入后调整插入路径节点的mbr范围
  68.         err = rtr_ins_enlarge_mbr(&cursor, &mtr);
  69.       }
  70.     }
  71.   }
  73. func_exit:
  74.   if (dict_index_is_spatial(index)) {
  75.     // 清除rtr_info
  76.     rtr_clean_rtr_info(&rtr_info, true);
  77.   }
  79.   return err;
  80. }

rtr_page_split_and_insert rtree page split实现

  1. // rtr_page_split_and_insert 函数将page上的recs分为两个组，
  2. // 新申请一个page，将一组recs留在旧page，将二组recs移动到新page
  3. rec_t *rtr_page_split_and_insert(
  4.     uint32_t flags,        /*!< in: undo logging and locking flags */
  5.     btr_cur_t *cursor,     /*!< in/out: cursor at which to insert; when the
  6.                            function returns, the cursor is positioned
  7.                            on the predecessor of the inserted record */
  8.     ulint **offsets,       /*!< out: offsets on inserted record */
  9.     mem_heap_t **heap,     /*!< in/out: pointer to memory heap, or NULL */
  10.     const dtuple_t *tuple, /*!< in: tuple to insert */
  11.     mtr_t *mtr)            /*!< in: mtr */
  12. {
  14. func_start:
  15.   // 将page上recs分为两组
  16.   n_recs = page_get_n_recs(page) + 1;
  17.   end_split_node = rtr_split_node_array + n_recs;
  18.   first_rec_group = split_rtree_node(
  19.       rtr_split_node_array, static_cast<int>(n_recs),
  20.       static_cast<int>(total_data), static_cast<int>(insert_size), 0, 2, 2,
  21.       &buf_pos, SPDIMS, static_cast<uchar *>(first_rec),
  22.       cursor->index->rtr_srs.get());
  24.   // 分配一个新的page
  25.   direction = FSP_UP;
  26.   hint_page_no = page_no + 1;
  27.   new_block = btr_page_alloc(cursor->index, hint_page_no, direction, page_level,
  28.                              mtr, mtr);
  29.   new_page_zip = buf_block_get_page_zip(new_block);
  30.   btr_page_create(new_block, new_page_zip, cursor->index, page_level, mtr);
  31.   new_page = buf_block_get_frame(new_block);
  33.   /* Set new ssn to the new page and page. */
  34.   page_set_ssn_id(new_block, new_page_zip, current_ssn, mtr);
  35.   next_ssn = rtr_get_new_ssn_id(cursor->index);
  36.   page_set_ssn_id(block, page_zip, next_ssn, mtr);
  38.   // 第一个group的recs留在旧page，将第二个group的rec移动到新page，主要在函数rtr_split_page_move_rec_list操作实现
  39.   // 如果新page为压缩页，且压缩操作失败，则在下面将所有rec拷贝到新page，然后分别删除新旧page上多余的rec
  40.   if (false || !rtr_split_page_move_rec_list(rtr_split_node_array, first_rec_group,
  41.                                        new_block, block, first_rec,
  42.                                        cursor->index, *heap, mtr)) {
  44.     /* For some reason, compressing new_page failed,
  45.     even though it should contain fewer records than
  46.     the original page.  Copy the page byte for byte
  47.     and then delete the records from both pages
  48.     as appropriate.  Deleting will always succeed. */
  49.     ... ...
  50.   }
  52.   /* Insert the new rec to the proper page. */
  53.   cur_split_node = end_split_node - 1;
  54.   if (cur_split_node->n_node != first_rec_group) {
  55.     insert_block = new_block;
  56.   } else {
  57.     insert_block = block;
  58.   }
  60.   /* Reposition the cursor for insert and try insertion */
  61.   page_cursor = btr_cur_get_page_cur(cursor);
  62.   page_cur_search(insert_block, cursor->index, tuple, PAGE_CUR_LE, page_cursor);
  65.   // 插入数据
  66.   rec = page_cur_tuple_insert(page_cursor, tuple, cursor->index, offsets, heap,
  67.                               mtr);
  69.   /* If insert did not fit, try page reorganization.
  70.   For compressed pages, page_cur_tuple_insert() will have
  71.   attempted this already. */
  72.   if (rec == nullptr) {
  73.     if (!page_cur_get_page_zip(page_cursor) &&
  74.         btr_page_reorganize(page_cursor, cursor->index, mtr)) {
  75.       rec = page_cur_tuple_insert(page_cursor, tuple, cursor->index, offsets,
  76.                                   heap, mtr);
  77.     }
  78.     /* If insert fail, we will try to split the insert_block
  79.     again. */
  80.   }
  82.   // 更新mbr、ssn等信息
  83.   /* Calculate the mbr on the upper half-page, and the mbr on
  84.   original page. */
  85.   rtr_page_cal_mbr(cursor->index, block, &mbr, *heap);
  86.   rtr_page_cal_mbr(cursor->index, new_block, &new_mbr, *heap);
  87.   prdt.data = &mbr;
  88.   new_prdt.data = &new_mbr;
  90.   /* Check any predicate locks need to be moved/copied to the
  91.   new page */
  92.   lock_prdt_update_split(block, new_block, &prdt, &new_prdt);
  94.   /* Adjust the upper level. */
  95.   rtr_adjust_upper_level(cursor, flags, block, new_block, &mbr, &new_mbr, mtr);
  97.   /* Save the new ssn to the root page, since we need to reinit
  98.   the first ssn value from it after restart server. */
  99.   root_block = btr_root_block_get(cursor->index, RW_SX_LATCH, mtr);
  100.   page_zip = buf_block_get_page_zip(root_block);
  101.   page_set_ssn_id(root_block, page_zip, next_ssn, mtr);
  103.   /* Insert fit on the page: update the free bits for the
  104.   left and right pages in the same mtr */
  105.   if (page_is_leaf(page)) {
  106.     ibuf_update_free_bits_for_two_pages_low(block, new_block, mtr);
  107.   }
  109.   /* If the new res insert fail, we need to do another split
  110.    again. */
  111.   if (!rec) {
  112.     /* We play safe and reset the free bits for new_page */
  113.     ... ...
  114.     goto func_start;
  115.   }
  116.   MONITOR_INC(MONITOR_INDEX_SPLIT);
  117.   return (rec);
  118. }

读取

读取数据，分为一致性读和锁定读。事务利用MVCC进行读取操作称为一致性读（Consistent Read），或者一致性无锁读（也称快照读），所有普通的SELECT语句在READ COMMITTED、 REPEATABLE READ隔离级别下都是一致性读。一致性读并不会对表中任何记录进行加锁操作，其他事务可以自由底对表中的记录进行改动。在一致性读场景下空间索引和普通索引没有区别，只是定位rec的方法不同（rtree定位rec见上面分析），在锁定读，serializable isolation隔离级别时空间索引加的是predicate lock，关于加锁读这里也不再展开。

更新及删除

空间索引更新删除操作同普通二级索引更新擅长操作代码路径基本一致，主要在函数row_upd_sec_index_entry_low中实现，该函数中空间索引部分和普通索引除了定位rec有区别，其他基本一致，所以不再详细说明。删除操作可以看作是更新操作的一种，删除操作是将原来record更新添加delete mark标记，实际record的删除是在undo purge的时候，这时可能会导致进行page的merge，此处也不再展开说明。

总结

innodb基于rtree的空间索引实现，和基于B+树实现的二级索引，主要代码路径基本一致，空间索引在MVCC，事务等特性上和普通二级索引一致。只是在定位、插入、更新及删除rec时，涉及rtree的一些基本信息及rtree的操作有些不同，还有就是在serializable isolation隔离级别时使用了predicate lock，相对一般二级索引有所不同。空间索引是二级索引基于rtree的一个特殊实现版本。