高效空间数据索引R树及其批量加载方法STR简介

高效空间数据索引R树及其批量加载方法STR简介

11 2021-09-29 17:33:28

##背景

工作中经常需要跟空间数据打交道，因此频繁使用一个工具类`com.vividsolutions.jts.index.strtree.STRtree`。STRtree类似于一个集合，向其插入一些带空间信息的数据后可以很便利地按范围查询空间数据，如下图示意。

![](/img/pic/2021092916303927125_png_511_425_251302)
> 范围查询

由于不清楚STRtree的查询实现逻辑，为探明原因及避免后续踩坑了解了一下，发现STRtree应用了非常精巧且应用广泛的空间索引结构R树（R-Tree）及优秀的批量加载算法STR。下文我们将从R树开始介绍，进一步了解STR算法，并说明一些STRtree相关的注意事项。

## R树是什么

> R树是用来做空间数据存储的树状数据结构。例如给地理位置，矩形和多边形这类多维数据建立索引。R树是由Antonin Guttman于1984年提出的。 ...... 可以用它来回答“查找距离我2千米以内的博物馆”，“检索距离我2千米以内的所有路段”（然后显示在导航系统中）或者“查找（直线距离）最近的加油站”这类问题。R树还可以用来加速使用包括大圆距离在内的各种距离度量方式的最邻近搜索。
> ——维基百科

R树是一种层次数据结构，它是B树在k维空间上的自然扩展，因此和B树一样，R树是一种高度平衡树，在叶结点中包含指向实际数据对象的指针。

定义：

> 1. 除非它是根结点之外，所有叶子结点包含有m至M个记录索引（条目）。作为根结点的叶子结点所具有的记录个数可以少于m。通常，m=M/2。
2. 对于所有在叶子中存储的记录（条目），I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（注意：此处所说的“矩形”是可以扩展到高维空间的）。
3. 每一个非叶子结点拥有m至M个孩子结点，除非它是根结点。
4. 对于在非叶子结点上的每一个条目，i是最小的可以在空间上完全覆盖这些条目所代表的点的矩形（同性质2）。
5. 所有叶子结点都位于同一层，因此R树为平衡树。

![](/img/pic/2021092917000348430_png_906_294_136887)
> R-Tree层次结构

简单来说，R树种的每个节点都是一个矩形，而且是节点数据的最小外接矩形（MBR，Minimun Bounding Rectangle），即覆盖内部几何图形的最小矩形边界。

***MBR本身通过x、y坐标容易计算，计算MBR相交也十分简单高效，适用于应用在索引结构中。***

![](/img/pic/2021092917013558231_png_86_86_11631)
> R8是D1数据的MBR

其中，叶子结点为实际结点空间数据的MBR；非叶子结点则为其所有子节点形成的MBR，即刚好包裹住所有子节点。

![](/img/pic/2021092916593458229_png_818_680_251486)
> R-Tree空间示意，实际父节点MBR不会像这样略微扩大

从定义中可以看出来，其结构与B树类似：

- 高度平衡，查询性能稳定
- 子节点数量有限制即存在节点分裂和合并
- 但节点不存储数据，正如作者Guttman论文所说，整个R树是完全针对计算机空间数据存储而设计的索引结构。

简单的部分到此为止，R树具体的插入删除规则涉及到复杂的规则，在节点分裂和合并之外还涉及父节点MBR的调整等，详情可参考原论文或[其他资料](https://www.cnblogs.com/cmi-sh-love/p/kong-jian-shud-ju-suo-yinRTree-wan-quan-jie-xi-jiJa.html)。

## R树能做什么

在不使用R树时，最基础的范围搜索方法是遍历整个数据集，将所有落在范围内的数据返回，在较大数据集中这个代价显然是不可接受的。当然通过网格划分数据集的方式也可以大大缩小候选数据集，但仍需要遍历候选网格的全量数据。

而R树的搜索算法则类似B树，从根节点开始，根据搜索范围找到命中的节点，并不断向下查找到叶子结点，缩小范围，最终返回命中的数据。这非常易于理解：当我们要找到某个商场时，思考路径也是AA市->BB区->CC路->DD路口依次缩小范围。

![](/img/pic/2021092917213202033_png_1062_1120_574930)
> R树搜索蓝色区域，命中了多个叶子结点

但R树与B树最显著的区别在于R树在非一维空间使用MBR描述节点的上下界，无法像B树节点一样准确适应子节点的分布。虽然通过通过MBR提高了计算和求交的效率，不过这也势必牺牲了空间利用率（父节点包含了空白区域）及查询效率（兄弟节点MBR可能会重叠）。

![](/img/pic/2021092916402641727_png_594_596_75438)
> 二维及更高维度下空白子区域和兄弟节点MBR重叠很难避免

在查询时，以下常见的情况会导致需要多路径搜索：

- 兄弟节点MBR重叠，搜索范围命中重叠区域
- 兄弟节点MBR不重叠但搜索范围跨多个节点，在点查询时不会出现这种情况

现在我们可以理解，R树中的R表示Rectangle，也表明其本质是一组有层次关系的“矩形”，在一维空间是线结构，在没有重叠的情况下结构很像B树，推广到三维则是长方体。

![](/img/pic/2021092918063820436_png_637_763_150396)
> 一维R树，结构接近B树

![](/img/pic/2021092917072028532_png_478_504_306491)
> 三维R树

R树作为一个比较宽泛的结构定义，并未限定具体的构造方式，而基于R树的概念及各种组织方式衍生出了庞大的R树家族，不同组织方式的R树变体性能差距很大。其他比较有特点的一些变体索引结构：

- **R+树** 将跨父MBR的节点分割成多个MBR，冗余存储在多个父级节点中，避免了兄弟节点MBR重叠，但增加了树的高度降低了范围查询效率，增删操作也更复杂
- **R\*树** 优化了插入和分裂策略，并使用节点强制重插技术即在触发分裂时优先将子节点重新插入，整体使得MBR的结构重叠减少，也减少了节点的分裂，提升查询效率
- **SS树** 使用最小外接圆替代MBR，增加了最近邻查询的效率，但在高维度表现不佳

![](/img/pic/2021092918020497235_png_1108_350_691674)
> 不同组织方式下的R树效果差别会很大

## STR R-Tree

通常从空树开始构建整个R树时，将记录逐个插入直至生成整个树的过程中会频繁触发索引结构的动态维护，这对于海量空间数据的初始化而言耗时巨大，代价过高。由此发展而来的Packing（批量加载）算法则可以在数据已知且相对静态的情况下尽可能提高R树的构建速度并优化索引结构。

其中Leutenegger等提出了一种STR(Sort-Tile-Recursive，递归网格排序) Packing算法，该算法易于实现且适用范围较广，在大多数场景下表现良好，且易于推广到高维空间。

***STR算法本质上只是R树的一种构建算法，STR R-Tree本质上仍是R树。***

### STR核心思路

STR可以理解为切蛋糕，首先确定一共应该切成N份，然后从左到右根据蛋糕上草莓个数竖切成sqrt(N)个中份，再从上到下把每个中份横切成sqrt(N)个小份，一趟递归就完成了。下一趟则是将小份蛋糕当作草莓，继续切直到不需要切为止，自下而上递归构成R树。

- **Sort** 子节点在某维度排序，方便划分网格
- **Tile** 网格化，即在某维度将数据集划分成多个切片，最终多个维度切片后综合形成节点的MBR
- **Recursive** 递归处理，自下而上每趟构建R树的一层

具体细节可以查看[作者原论文](https://www.cs.odu.edu/~mln/ltrs-pdfs/icase-1997-14.pdf)，算法介绍不到一页，概念好理解。

![](/img/pic/2021092917245285634_png_928_1090_276780)
> STR构建过程及效果，大部分场景效果很好，左右极端情况下表现一般，整体重叠比例小

### STR的优势

STR本身逻辑并不复杂，其排序和网格化的逻辑是与维度无关的，还可以拆分至按维度计算，对算法实现比较友好，构建效率也高；同时，其使用递归和网格化的思路可以较好地将兄弟MBR大致分离，尽可能减少重叠区域，大多数数据分布下查询效率较高。

## 补充

- MySql使用了R-Tree作为空间索引，参见[说明文档](https://dev.mysql.com/doc/refman/5.7/en/creating-spatial-indexes.html)
- `com.vividsolutions.jts.index.strtree.STRtree`是实现了STR packing算法的R树索引
	- 在packing后（首次调用query后）不能再增删节点
	- STRtree通过Envelope即MBR的形式进行查询，因此在范围查询时如果范围几何不是矩形则需要对查询结果做过滤处理

![](/img/pic/2021092918175075237_png_640_538_192731)
> MBR查询后需再经过几何范围过滤

## 参考资料

[R-Trees - A Dynamic Index Structure for Spatial Searching](http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf)

[STR: A Simple and Efficient Algorithm for R-Tree Packing](https://www.cs.odu.edu/~mln/ltrs-pdfs/icase-1997-14.pdf)

[R树家族的演变和发展 - 中国科学院](http://sourcedb.igsnrr.cas.cn/zw/lw/200906/P020090625735352938182.pdf)

[空间数据索引RTree（R树）完全解析及Java实现 - 佳佳牛 - 博客园](https://www.cnblogs.com/cmi-sh-love/p/kong-jian-shud-ju-suo-yinRTree-wan-quan-jie-xi-jiJa.html)

[MySQL :: MySQL 5.7 Reference Manual :: 11.4.9 Creating Spatial Indexes](https://dev.mysql.com/doc/refman/5.7/en/creating-spatial-indexes.html)