动态空间划分（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区怎么办？

        分割（投影）算法不完美

不只有概念描述中的五边形、六边形；   

会有七边形，甚至十边形(出现在正二十面体的交线上)；