Google S2
http://s2geometry.io/devguide/s2cell_hierarchy
https://halfrost.com/go_spatial_search/
https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSngKwvS_jwNVHRPZTTDzXXn6Q/view?pli=1#slide=id.i148
Google’s S2 library is a real treasure, not only due to its capabilities for spatial indexing but also because it is a library that was released more than 4 years ago and it didn’t get the attention it deserved
上面这段话来自2015年一位谷歌工程师的博文。他由衷的感叹 S2 算法发布4年没有得到它应有的赞赏。不过现在 S2 已经被各大公司使用了。
在介绍这个重量级算法之前，先解释一些这个算法的名字由来。S2其实是来自几何数学中的一个数学符号 S²，它表示的是单位球。S2 这个库其实是被设计用来解决球面上各种几何问题的。值得提的一点是，除去 golang 官方 repo 里面的 geo/s2 完成度目前只有40%，其他语言，Java，C++，Python 的 S2 实现都完成100%了。本篇文章讲解以 Go 的这个版本为主。
Uber H3
https://www.uber.com/en-AU/blog/h3/
https://h3geo.org/docs/
https://docs.carto.com/data-and-analysis/analytics-toolbox-for-postgresql/key-concepts/spatial-indexes
https://www.shenyanchao.cn/blog/2020/01/16/geo_uber_h3/
https://www.biaodianfu.com/uber-h3.html
https://halfrost.com/go_spatial_search/
https://www.bolzjb.com/archives/rPjDsSYS.html
https://lihuia.com/h3%EF%BC%9A%E7%A9%BA%E9%97%B4%E7%B4%A2%E5%BC%95%E7%B2%BE%E5%BA%A6/
当涉及到空间索引技术时，理解每种技术的工作原理和应用场景是非常重要的。下面我将为你详细解释每种技术，并举例说明其在实际应用中的使用情况：
R(R+)树：
工作原理：R树是一种树形数据结构，每个节点表示一个包含子节点或数据对象的矩形区域。节点的子节点可能重叠，但其矩形区域不会重叠。查询时，从根节点开始，递归地遍历子节点，以找到满足查询条件的数据对象。
应用场景：地理信息系统（GIS）中的空间数据管理是R树的主要应用领域之一。例如，在地图应用中，可以使用R树来管理地理空间数据，如道路、建筑物和地理标记，以支持空间查询和分析操作。
网格(Grid)索引：
工作原理：网格索引将空间数据划分成规则的网格单元，每个网格单元存储落入该单元的空间数据。查询时，可以根据查询范围直接定位到相应的网格单元，然后只需要检索该网格单元中的数据。
应用场景：网格索引在地理信息系统中的栅格数据管理中广泛应用。例如，将地图划分成网格单元，每个单元存储相应的地理数据，以支持空间分析和可视化操作。
KD(K-Dimensional tree)树：
工作原理：KD树是一种多维空间的二叉树结构，通过轮流在每个维度上进行分割来构建树。查询时，从根节点开始，根据查询条件依次选择相应的分割平面，直到找到满足条件的数据对象。
应用场景：在计算机图形学中，KD树常用于加速光线追踪算法。例如，在三维场景中，可以使用KD树来管理场景中的三角形网格，以加速光线和物体之间的相交检测。
四叉树(Quadtree)：
工作原理：四叉树是一种递归的数据结构，将二维空间逐步分割成四个象限。每个节点可以有零到四个子节点，根据空间数据的分布情况来动态生成节点。查询时，通过递归遍历树结构，定位到包含查询范围的叶子节点，然后检索该节点中的数据。
应用场景：在计算机图形学和地理信息系统中，四叉树常用于空间数据的层次存储和快速查询。例如，在图像处理中，可以使用四叉树来管理图像的像素数据，以支持图像压缩和局部编辑操作。
BSP(Binary Space Partitioning)树：
工作原理：BSP树通过递归地将空间分割成凸多边形的二叉树结构。每个节点表示一个分割平面，将空间分割成两个区域。查询时，根据查询条件选择相应的分割平面，以缩小搜索范围。
应用场景：在三维图形渲染中，BSP树常用于场景的空间分区和渲染优化。例如，在实时游戏引擎中，可以使用BSP树来管理场景中的可见物体，以提高渲染性能和效率。
填充曲线(Peano Curve)索引：
工作原理：填充曲线是一种将多维空间映射到一维空间的技术。通过将空间数据沿着填充曲线进行编码，可以实现空间数据的压缩和索引。查询时，根据填充曲线的编码，可以高效地定位和检索数据。
应用场景：填充曲线索引在空间数据压缩和检索中具有广泛的应用。例如，在地理信息系统中，可以使用填充曲线来管理地图数据，以支持快速的空间查询和可视化操作。
GiST(Generalized Search Tree)：
工作原理：GiST是一种通用的索引结构，可以支持各种不同类型的数据和查询操作。它通过定义不同的索引方法和策略，实现对空间数据的高效管理和检索。
应用场景：GiST索引在数据库系统中广泛应用于空间数据管理和查询优化。例如，在地理空间数据库中，可以使用GiST索引来加速空间查询和分析操作，如范围查询和最近邻查询。
BRIN(Block Range Index)：
工作原理：BRIN是一种针对大型表的索引技术，通过对数据按块进行索引，而不是每一行进行索引。这种索引适用于顺序访问和范围查询，可以显著减少索引的存储空间和维护成本。
应用场景：在大规模数据分析和数据仓库系统中，BRIN索引可以用于加速对大型表的范围查询和聚合操作。例如
时间序列数据库：在时间序列数据库中，数据通常按照时间顺序存储，并且经常需要执行时间范围查询或聚合操作。BRIN索引可以有效地加速这些查询，特别是在处理大量时间序列数据时。
大型表的分析：在大型表中，范围查询和聚合操作可能会变得非常昂贵，因为需要扫描大量的数据。使用BRIN索引可以减少这种成本，通过只扫描相关的数据块来加速查询。
---
空间索引是空间数据库中用于提高查询效率的重要技术之一。常见的空间索引包括R(R+)树、网格(grid)索引、KD(K-Dimensional tree)树、四叉树(quadtree)、BSP树(binary space partitioning tree)、填充曲线(peano curve)索引、GiST(Generalized Search Tree)和BRIN(block range index)等。
R(R+)树索引通过递归地将空间范围划分为多个矩形子区域，并构建为一棵树状结构。每个节点代表一个矩形区域，其中存储着一个或多个空间要素。
网格(grid)索引将空间范围分割成多个网格，并为每个网格分配唯一标识符。每个网格节点存储着其覆盖的空间要素指针，以实现对空间数据的快速查询。
KD(K-Dimensional tree)树索引将空间范围划分为多个超矩形区域，构建为一棵叉树结构。每个节点表示一个超矩形区域，存储着该区域覆盖的空间要素指针。
四叉树(quadtree)索引采用逐层递归的四分方式划分空间范围，直至每个子区域仅包含一个空间要素。这种索引结构适用于对空间数据进行高效存储和检索。
BSP树(binary space partitioning tree)索引则采用逐层递归的二分方式划分空间范围，并构建为一棵二叉树。每个节点代表一个子区域，其中存储着该区域覆盖的空间要素指针。
填充曲线(peano curve)索引将多维空间数据映射到一维空间，通过特定的填充曲线算法实现空间数据的压缩和映射，以便于高效的空间数据查询和处理。
GiST(Generalized Search Tree)是一种通用的索引结构，适用于各种类型的数据。它通过构建一棵多叉树来表示空间数据，每个节点包含一个空间要素以及对应的Bounding Box，以支持高效的空间数据查询操作。
BRIN(block range index)是一种基于块的索引方式，它将相邻块中的空间要素范围索引化，而不是存储每个空间要素的具体位置信息。BRIN索引将整个空间范围划分成若干个块，以实现对大规模空间数据的快速范围查询和过滤。
网友评论