(十五）GeoSpark源码解析（四）

GeoSpark源码解析（四）

上节我们讲了GeoSpark如何根据已经分好的格网（Grid）来进行分块（partition）操作。对于GeoSpark来说，格网的生成算法实际上是决定了并行计算的关键，在上一节中，我们讲到了SpatialRDD的spatialPartitioning方法，他需要一个SpatialPartitioner类型的参数，这个参数有三种类型：

image.png

这三种SpatialPartitioner其实是在public void spatialPartitioning(GridType gridType, int numPartitions)这个函数中构造的。我们先看下GridType：

public enum GridType{
    /**
     * The equalgrid.
     */
    EQUALGRID,
    /**
     * The hilbert.
     */
    HILBERT,
    /**
     * The rtree.
     */
    RTREE,
    /**
     * The voronoi.
     */
    VORONOI,
    /**
     * The voronoi.
     */
    QUADTREE,
    /**
     * K-D-B-tree (k-dimensional B-tree)
     */
    KDBTREE;
}

代码中共有6种，我们分别介绍下：

1. EQUALGRID，这个我们从名字上就可以看出他是等分，就是等分为多少行多少列。

  public EqualPartitioning(Envelope boundary, int partitions)
       {
           //Local variable should be declared here
           Double root = Math.sqrt(partitions);
           int partitionsAxis;
           double intervalX;
           double intervalY;
   
           //Calculate how many bounds should be on each axis
           partitionsAxis = root.intValue();
           intervalX = (boundary.getMaxX() - boundary.getMinX()) / partitionsAxis;
           intervalY = (boundary.getMaxY() - boundary.getMinY()) / partitionsAxis;
           //System.out.println("Boundary: "+boundary+"root: "+root+" interval: "+intervalX+","+intervalY);
           for (int i = 0; i < partitionsAxis; i++) {
               for (int j = 0; j < partitionsAxis; j++) {
                   Envelope grid = new Envelope(boundary.getMinX() + intervalX * i, boundary.getMinX() + intervalX * (i + 1), boundary.getMinY() + intervalY * j, boundary.getMinY() + intervalY * (j + 1));
                   //System.out.println("Grid: "+grid);
                   grids.add(grid);
               }
               //System.out.println("Finish one column/one certain x");
           }
       }

代码的第11、12行首先根据要分块的长宽计算X、Y间隔，然后第14、15行for循环遍历生成网格。

2. HILBERT:Hilbert其实是最近很流行的一种新型NoSQL空间索引，就是利用这个算法生成key-Value格式的空间索引，存储在HBase、Accumulo等分布式非关系型数据库中，目前LocationTech下的GeoWave、GeoMesa就是采用了这个思路。
3. RTREE，下面这张图很好的展示R树的工作原理，其实就是对整个空间建立索引关系，加快搜索效率。然后GeoSpark是将RTree的最后一级叶子节点作为网格建立。

image.png

4. VORONOI，这个不了解。
5. QUADTREE，GIS中很经典的一种索引算法，就是数据结构中的四叉树，其原理就是将一个空间每次四等分下去，分到某个级别后停止。
6. KDBTREE，这个我也不是特别理解，感觉和RTREE大致上差不多的，可能具体针对特别的空间分布下的空间数据有相应的优势吧。

image.png

当Grid构建好之后，就可以构造SpatialPartitioner，然后进行分块操作。

    public void spatialPartitioning(GridType gridType, int numPartitions)
            throws Exception{
        //  省略部分代码
        switch (gridType) {
            case EQUALGRID: {
                EqualPartitioning EqualPartitioning = new EqualPartitioning(paddedBoundary, numPartitions);
                grids = EqualPartitioning.getGrids();
                partitioner = new FlatGridPartitioner(grids);
                break;
            }
            case HILBERT: {
                HilbertPartitioning hilbertPartitioning = new HilbertPartitioning(samples, paddedBoundary, numPartitions);
                grids = hilbertPartitioning.getGrids();
                partitioner = new FlatGridPartitioner(grids);
                break;
            }
            case RTREE: {
                RtreePartitioning rtreePartitioning = new RtreePartitioning(samples, numPartitions);
                grids = rtreePartitioning.getGrids();
                partitioner = new FlatGridPartitioner(grids);
                break;
            }
            case VORONOI: {
                VoronoiPartitioning voronoiPartitioning = new VoronoiPartitioning(samples, numPartitions);
                grids = voronoiPartitioning.getGrids();
                partitioner = new FlatGridPartitioner(grids);
                break;
            }
            case QUADTREE: {
                QuadtreePartitioning quadtreePartitioning = new QuadtreePartitioning(samples, paddedBoundary, numPartitions);
                partitionTree = quadtreePartitioning.getPartitionTree();
                partitioner = new QuadTreePartitioner(partitionTree);
                break;
            }
            case KDBTREE: {
                final KDBTree tree = new KDBTree(samples.size() / numPartitions, numPartitions, paddedBoundary);
                for (final Envelope sample : samples) {
                    tree.insert(sample);
                tree.assignLeafIds();
                partitioner = new KDBTreePartitioner(tree);
                break;
            }
        }
        this.spatialPartitionedRDD = partition(partitioner);
    }

到这里，基本上GeoSpark基本代码就介绍完了，也算是对前期自己工作的一个总结，后续根据时间、项目再来进行探讨。