innodb 空间索引实现

innodb 空间索引实现

摘要

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

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