动态空间划分（R-tree）
静态空间划分（GeoHash、S2、H3）
空间划分知识：http://www.cocoachina.com/cms/wap.php?action=article&id=20309
GeoHash
四叉树
经度、纬度的二分来分块，逻辑最简单。
Z-行空间遍历
编码方式
所在层级经纬度二分下标（0、1），先经后纬，逐层排列。
Google S2
正方体投影
以正方体投影作为基准，六个面逐级纬度二分。
希尔伯特曲线
相邻相近
等距连续？
编码方式
六面ID+ 所在层级经纬度二分下标（0、1），受曲线旋转影响，逐层排列。
映射修正
使面积差距小
线性变换：s = 0.5 * (1 + u)
tan变换：s = 2 / pi * (atan(u) + pi / 4) = 2 * atan(u) / pi + 0.5
二次变换（Uber选择）：u >= 0，s = 0.5 * sqrt(1 + 3*u)
u < 0, s = 1 - 0.5 * sqrt(1 - 3*u)
Uber H3
官网
https://uber.github.io/h3/#/documentation/overview/introduction
怎么划分空间
假设正x多边形，y个顶点相接：360 / y = ((x-2)*180) / x
y = 2x / (x-2)
正整数解只有（3,6、4,4、6,3)
正六多边形优点
相邻单元距离相等
近似圆
自身近似圆形，贴合密度概念，很适合大多数的汇总分析场景。
周围相近近似圆形且等距，方便附近查找，阶梯分析等
Uber怎么做？
想要的一个优点，分割后面积相同。
面积相同的正六边形不能构建成球形。
正二十面体
正二十面体
基本单元
H3基本块
正二十面体，交点有五个边。每一个基本单元做上图图示的分割。
全球被划分为12个正五边形和110个正六边形的基本单元。
Dymaxion map
戴美克森氏地图(Dymaxion map)或称富勒地图(Fuller map),由Richard Buckminster Fuller发明。建筑师。
dymaxion（最大限度利用能源的,以最少结构提供最大强度的），这个词来源于三个单词：Dynamic，意思是动力，Maximum，意思是最多、最大，还有ion，是一个原子或是一个电极中一组原子。
选择二十面体的顶点在水中，尽量避免常规应用中同时使用五边形和六边形。
逐级等分
可支持16级拆分
第一层基础单元格，15级（编码方式决定）的等面积拆分。
基本元素
单元格(cell)
普通的各级分裂的结果
有向格
单元格增加一个以六条边为基础的维度，可以表示从一个单元格到另一个共边单元格的意向，相当于记录两个有共边的单元格，当需要时，可以将边缘转换回原始索引或目标索引。
分为单向格(Unidirectional Edge)和双向格(bidirectional edge)。
IJK坐标系
一种平面六边形网络中的三轴坐标系。为六边形网络中的每一个元素提供唯一路径。
FaceIJK坐标系
H3 核心运算使用的坐标系。
由二十面体基本单元ID + IJK坐标系构成。有两种类型（R. Buckminster Fuller定义）：
0层使用ClassII；逐层摇摆，交替使用。
其他坐标系
https://uber.github.io/h3/#/documentation/core-library/coordinate-systems
编码方式
使用64位，一个Long值的长度来记录一个基本类型。
·· 前4位表示索引模式：0：无效；1：单元格；2：单向格；3：双向格。
·· 3位表示共边ID（模式2和模式3有效）。
·· 4位表示当前索引级别（0-15）。
·· 7位表示基本单元格ID（0-121）。
·· 每3位一个层级，逐层排列（3*15）。
·· 队尾未被使用的位置1。
拆分编码：（ 五边形拆分中废弃下标1）
应用场景
普通索引
高精度的数据，模糊到选定的H3粒度，作为数据的索引使用。
附近搜
K环（kRing）：
根据指定中心点，得到指定单位距离内（K）的其他单元格，非常方便的实现附近的需要。发挥近似圆的优势。
多边形索引
指定粒度切分指定多边形，得到多边形覆盖的单元格，并且提供压缩功能。
jar使用
groupId：com.uber
artifactId：h3
version：
H3Core h3 = H3Core.newInstance();
h3.xxx();
性能
普通应用场景和geohash的使用场景并无实质性的区别，但是等面积、近圆的特性，在一些场景，会降低实现算法的难度。
多边形索引的场景，需要围栏预处理工作，然后做两个Btree的关联运算，具体性能对比，待测试。
缺点
上下级的不完全覆盖(蓝色区域举例)，一些应用场景要注意。
编码方式对普通索引不友好
如下：同一个经纬度，在不同层级的索引值
000100000000011000111111111111111111111111111111111111111111111
8031fffffffffff
000100000010011000110111111111111111111111111111111111111111111
8131bffffffffff
000100000100011000110011111111111111111111111111111111111111111
82319ffffffffff
000100010010011000110011101101010101001110000111111111111111111
89319daa9c3ffff
000100011110011000110011101101010101001110000011101000000110011
8f319daa9c1d033
如果使用压缩算法，上级（压缩后）的索引值和下级（压缩前）的索引值，没有办法命中普通数据库之类的的普通索引，大大的限制了压缩算法的使用场景。
解决方式：
擦除索引层级标记
000100000100011000110011111111111111111111111111111111111111111&111111100001111111111111111111111111111111111111111111111111111
000100010010011000110011101101010101001110000111111111111111111&111111100001111111111111111111111111111111111111111111111111111
-->
000100000000011000110011111111111111111111111111111111111111111
000100000000011000110011101101010101001110000111111111111111111
截断后面无效的1
000100000000011000110011111111111111111111111111111111111111111
000100000000011000110011101101010101001110000111111111111111111
-->
000100000000011000110011
000100000000011000110011101101010101001110000
base8编码？
就可以在使用压缩算法节省存储空间的同时，又可以命中普通Btree索引。
跨Base区怎么办？
分割（投影）算法不完美
不只有概念描述中的五边形、六边形；
会有七边形，甚至十边形(出现在正二十面体的交线上)；
网友评论