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

空间索引的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数据结构介绍

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

rtr_cur_search_with_match 空间索引page内rec定位

row_ins_sec_index_entry_low 空间索引插入数据

rtr_page_split_and_insert rtree page split实现

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

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