关于elasticsearch:Elasticsearch-在地理信息空间索引的探索和演进

vivo 互联网服务器团队 - Shuai Guangying

本文梳理了 Elasticsearch 对于数值索引实现计划的降级和优化思考，从 2015 年至今数值索引的计划经验了多个版本的迭代，实现思路从最后的字符串模仿到 KD-Tree，技术越来越简单，能力越来越弱小，利用场景也越来越丰盛。从地理位置信息建模到多维坐标，数据检索到数据分析洞察都能够看到 Elasticsearch 的身影。

一、业务背景

LBS 服务是以后互联网重要的一环，波及餐饮、娱乐、打车、批发等场景。在这些场景中，有很重要的一项根底能力：搜寻左近的 POI。比方搜寻左近的美食，搜寻左近的电影院，搜寻左近的专车，搜寻左近的门店。例如：以某个坐标点为核心查问出 1km 半径范畴的 POI 坐标，如下图所示：

Elasticsearch 在地理位置信息检索上具备了毫秒级响应的能力，而毫秒级响应对于用户体验至关重要。下面的问题应用 Elasticsearch，只需用到 geo_distance 查问就能够解决业务问题。应用 Elasticsearch 的查问语法如下：

GET /my_locations/_search
{
  "query": {
    "bool": {
      "must": {"match_all": {}
      },
      "filter": {
        "geo_distance": {
          "distance": "1km",
          "pin.location": {
            "lat": 40,
            "lon": 116
          }
        }
      }
    }
  }
}

工具的应用是一个非常简单的事件，更有意思在于工具解决问题背地的思维。了解了解决问题的思维，就能够超然于工具自身，做到触类旁通。本文基于在海量数据背景下，如何实现毫秒级搜寻左近的 POI 这个问题，探讨了 Elasticsearch 的实现计划，以及实现地理位置索引技术的演进过程。

二、背景常识

在介绍 Elasticsearch 的解决计划前，咱们首先须要介绍一些背景常识，次要是 3 个问题。

1. 如何精确定位一个地址？

由经度、纬度和相对高度组成的天文坐标系，可能明确标示出地球上的任何一个地位。地球上的经度范畴 [-180，180]，纬度范畴[-90，90]。通常以本初子午线(经度为 0)、赤道(纬度为 0) 为分界线。对于大多数业务场景，由经纬度组成的二维坐标曾经足以应答业务问题，可能重庆山城会有些例外。

2. 如何计算两个地址间隔？

对于立体坐标系，由勾股定理能够不便计算出两个点的间隔。然而因为地球是一个不完满球体，且不同地位有不同海拔高度，所以准确计算两个间隔地位是一个非常复杂的问题。在不思考高度的状况下，二维坐标间隔通常应用 Haversine 公式。

这个公式非常简单，只需用到 arcsin 和 cos 两个高中数学公式。其中 φ 和 λ 示意两个点纬度和经度的弧度制度量。其中 d 即为所求两个点的间隔，对应的数学公式如下(参考维基百科)：

程序员更喜爱看代码，对照代码了解公式更简略。相应的代码如下：

// 代码摘自 lucene-core-8.2.0，SloppyMath 工具类
 
 /**
  * Returns the Haversine distance in meters between two points
  * given the previous result from {@link #haversinSortKey(double, double, double, double)}
  * @return distance in meters.
  */
 public static double haversinMeters(double sortKey) {return TO_METERS * 2 * asin(Math.min(1, Math.sqrt(sortKey * 0.5)));
 }
 
 /**
  * Returns a sort key for distance. This is less expensive to compute than
  * {@link #haversinMeters(double, double, double, double)}, but it always compares the same.
  * This can be converted into an actual distance with {@link #haversinMeters(double)}, which
  * effectively does the second half of the computation.
  */
 public static double haversinSortKey(double lat1, double lon1, double lat2, double lon2) {
   double x1 = lat1 * TO_RADIANS;
   double x2 = lat2 * TO_RADIANS;
   double h1 = 1 - cos(x1 - x2);
   double h2 = 1 - cos((lon1 - lon2) * TO_RADIANS);
   double h = h1 + cos(x1) * cos(x2) * h2;
   // clobber crazy precision so subsequent rounding does not create ties.
   return Double.longBitsToDouble(Double.doubleToRawLongBits(h) & 0xFFFFFFFFFFFFFFF8L);
 }
 // haversin
 // TODO: remove these for java 9, they fixed Math.toDegrees()/toRadians() to work just like this.
 public static final double TO_RADIANS = Math.PI / 180D;
 public static final double TO_DEGREES = 180D / Math.PI;
 
 // Earth's mean radius, in meters and kilometers; see http://earth-info.nga.mil/GandG/publications/tr8350.2/wgs84fin.pdf
 private static final double TO_METERS = 6_371_008.7714D; // equatorial radius
 private static final double TO_KILOMETERS = 6_371.0087714D; // equatorial radius
 
/**
  * Returns the Haversine distance in meters between two points
  * specified in decimal degrees (latitude/longitude).  This works correctly
  * even if the dateline is between the two points.
  * <p>
  * Error is at most 4E-1 (40cm) from the actual haversine distance, but is typically
  * much smaller for reasonable distances: around 1E-5 (0.01mm) for distances less than
  * 1000km.
  *
  * @param lat1 Latitude of the first point.
  * @param lon1 Longitude of the first point.
  * @param lat2 Latitude of the second point.
  * @param lon2 Longitude of the second point.
  * @return distance in meters.
  */
 public static double haversinMeters(double lat1, double lon1, double lat2, double lon2) {return haversinMeters(haversinSortKey(lat1, lon1, lat2, lon2));
 }

3. 如何不便在互联网分享经纬度坐标？

Geohash 是 2008-02-26 由 Gustavo Niemeyer 在本人的集体博客上颁布的算法服务。其初衷在于通过对经纬度的编码对外提供简短的 URL 标识地图地位，不便在电子邮件、论坛和网站中应用。

实际上 Geohash 的价值不仅仅是提供简短的 URL，它更大的价值在于：

1. Geohash 给地图上每个坐标提供了举世无双的 ID，这个惟一 ID 就相当于给每个地理位置提供了一个身份证。惟一 ID 在数据库中利用场景十分丰盛。
2. 在数据库中给坐标点提供了另一种存储形式，将二维的坐标点转化成为一维的字符串，对于一维数据就能够借助 B 树等索引来减速查问。
3. Geohash 是一种前缀编码，地位相近的坐标点前缀雷同。通过前缀提供了高性能的邻近地位 POI 查问，而邻近地位 POI 查问是 LBS 服务的外围能力。

对于 Geohash 的编码规定，这里不开展。这里最要害的点在于：

Geohash 是一种前缀编码，地位相近的坐标点前缀雷同。Geohash 编码长度不同，所笼罩区域范畴不同。

在后面常识的铺垫下，最简略的求一个坐标点指定半径范畴内的坐标汇合的计划就出炉了。

• 暴力算法

核心坐标点顺次跟汇合中每个坐标点计算间隔，筛选出合乎半径条件的坐标点。

这个算法大家太相熟了，就是最常见的暴力 (Brute Force) 算法。这个算法在海量数据背景下是没法满足毫秒级响应工夫要求的，所以多用于离线计算。对于毫秒级响应的业务诉求，这个算法能够基于 geohash 进行革新。

• 二次筛选

1. 基于坐标中心点计算出 geohash, 基于半径确定 geohash 前缀。
2. 通过 Geohash 前缀初筛出大抵符合要求的坐标点(须要将中心点所在 Geohash 块四周 8 个 Geohash 块纳入初筛范畴)。
3. 对于初筛后果应用 Haversine 公式进行二次筛选。

除了上述计划，Elasticsearch 在天文信息处理上有哪些奇思妙想呢？

三、计划演进

Elasticsearch 从 2.0 版本开始反对 geo_distance 查问，到以后已更新到 7.14 版本。

从 2015 年至今曾经经验了 6 年的倒退，建设了如下的能力：

技术迭代大抵能够分为 3 个阶段：

倒退的成效显著，从性能测试的后果能够略窥一二：

总的来说，资源耗费升高的前提下搜寻和写入数据效率都有大幅度晋升。上面就具体介绍 Elasticsearch 对地理信息索引的思路。

3.1 史前时代

Elasticsearch 是基于 Lucene 构建的搜索引擎。Lucene 最开始的构想是一个全文检索工具箱，即反对字符串检索，并没有思考数值类型的解决。其核心思想非常简单，将文档分词后，为每个词构建一个 term => array[docIds]的映射。

这样用户输出关键词只须要三步就能够取得想要的后果：

第一步: 通过关键词找到对应的倒排表。这一步简略来说就是查词典。例如：TermQuery.TermWeight 获取该 term 的倒排表，读取 docId+freq 信息。

第二步: 依据倒排表失去的 docId 和词频信息对文档进行打分，返回给用户分值最高的 TopN 后果。例如：TopScoreDocCollector — collect()办法，基于小顶堆，保留分数最大的 TopN 文档。

第三步: 基于 docId 查问正排表获取文档字段明细信息。

这三步看起来简略，但几乎是数据结构利用最佳战场，它须要综合思考磁盘、内存、IO、数据结构工夫复杂度，十分具备挑战性。

例如：查词典能够用很多数据结构实现，比方跳跃表，均衡树、HashMap 等，而 Lucene 的外围工程师 Mike McCandless 实现了一个只有他本人能懂的 FST, 是综合了无限自动机和前缀树的一种数据结构，用来均衡查问复杂度和存储空间，比 HashMap 慢，然而空间耗费低。文档打分通常用小顶堆来保护分值最高的 N 个后果，如果有新的文档打分超过堆顶，则替换堆顶元素即可。

问题：对于实在业务场景而言，只有字符串匹配查问是不够的，字符串和数值是利用最宽泛的两种数据类型。如果须要进行区间查问怎么办呢？这是一个数据库产品十分根底的能力。

Lucene 提供了一种适配计划 RangeQuery。就是用枚举来模仿数值查问。简略来说：RangeQuery=BooleanQuery+TermQuery，所以限度查问是整数且区间最大不能超过 1024。这种实现是能够说是十分鸡肋的，好在 Lucene 2.9.0 版本真正反对数值查问。

LUCENE-1470,LUCENE-1582,LUCENE-1602,LUCENE-1673,LUCENE-1701, LUCENE-1712

Added NumericRangeQuery and NumericRangeFilter, a fast alternative to RangeQuery/RangeFilter for numeric searches. They depend on a specific structure of terms in the index that can be created by indexing using the new NumericField or NumericTokenStream classes. NumericField can only be used for indexing and optionally stores the values as string representation in the doc store. Documents returned from IndexReader/IndexSearcher will return only the String value using the standard Fieldable interface. NumericFields can be sorted on and loaded into the FieldCache. (Uwe Schindler, Yonik Seeley, Mike McCandless)

这个实现很弱小，反对了 int/long/float/double/short/byte，也不限度查问区间了。它的外围思路是将数值字节数组化，而后利用前缀分层治理区间。

如下图所示：

实质上还是 RangeQuery=BooleanQuery+TermQuery，只不过在后面做了一层转换：通过前缀树治理一个区间实现了匹配词数量的缩减，而这个缩减是十分无效的。所以这里就有一个专家参数：precisionStep。就是用来管制每个数值字段在分词是生成 term 的数量，生成 term 数量越多，区间管制粒度越细，占用磁盘空间越大，查问效率通常越高。

例如：如果 precisionStep=8, 则象征前缀树叶子节点的下层管制着 255 个叶子。那么，当查问范畴在 1~511 时，因为跨了相邻的 2 个非叶子节点，所以须要遍历 511 个 term。然而如果查问范畴在 0~512，又只需遍历 2 个 term 即可。这样的实现用起来真的有过山车的感觉。

综上，Elasticsearch 外围的 Lucene 倒排索引是一种经典的以不变应万变：字符串和数值索引外围都是查倒排表。了解这个外围，对于前面了解地理位置数据存储和查问十分要害。接下来咱们以 geo_distance 的实现思路为摸索主线条，摸索一下 ES 各个版本的实现思路。

3.2 Elasticsearch 2.0 版本

这个版本实现 geo\_distance 查问的思路十分奢侈，是建设在数值区间查问 (NumericRangeQuery) 的根底上。它的 geo\_point 类型字段其实是一个复合字段，或者说是一个构造体。在底层实现时别离用两个独立字段索引来防止暴力扫描。即 Elasticsearch 的 geo_point 字段在实现上是 lat,lon，加上编码成的 geohash 综合提供检索聚合性能。

字段定义如下所示：

public static final class GeoPointFieldType extends MappedFieldType {

    private MappedFieldType geohashFieldType;
    private int geohashPrecision;
    private boolean geohashPrefixEnabled;

    private MappedFieldType latFieldType;
    private MappedFieldType lonFieldType;

    public GeoPointFieldType() {}
}

算法的执行分为三个阶段：

第一步：依据中心点以及半径计算出一个大抵合乎需要的矩形区域，而后利用矩形区域的 最小最大经度失去一个数值区间查问 ，利用矩形区域的 最小最大纬度失去一个区间查问。

外围代码如下图所示：

// 计算经纬度坐标 + 间隔失去的矩形区域
// GeoDistance 类
public static DistanceBoundingCheck distanceBoundingCheck(double sourceLatitude, double sourceLongitude, double distance, DistanceUnit unit) {
     // angular distance in radians on a great circle
     // assume worst-case: use the minor axis
     double radDist = unit.toMeters(distance) / GeoUtils.EARTH_SEMI_MINOR_AXIS;
 
     double radLat = Math.toRadians(sourceLatitude);
     double radLon = Math.toRadians(sourceLongitude);
 
     double minLat = radLat - radDist;
     double maxLat = radLat + radDist;
 
     double minLon, maxLon;
     if (minLat > MIN_LAT && maxLat < MAX_LAT) {double deltaLon = Math.asin(Math.sin(radDist) / Math.cos(radLat));
         minLon = radLon - deltaLon;
         if (minLon < MIN_LON) minLon += 2d * Math.PI;
         maxLon = radLon + deltaLon;
         if (maxLon > MAX_LON) maxLon -= 2d * Math.PI;
     } else {
         // a pole is within the distance
         minLat = Math.max(minLat, MIN_LAT);
         maxLat = Math.min(maxLat, MAX_LAT);
         minLon = MIN_LON;
         maxLon = MAX_LON;
     }
 
     GeoPoint topLeft = new GeoPoint(Math.toDegrees(maxLat), Math.toDegrees(minLon));
     GeoPoint bottomRight = new GeoPoint(Math.toDegrees(minLat), Math.toDegrees(maxLon));
     if (minLon > maxLon) {return new Meridian180DistanceBoundingCheck(topLeft, bottomRight);
     }
     return new SimpleDistanceBoundingCheck(topLeft, bottomRight);
 }

第二步：两个查问通过 BooleanQuery 组合成一个取交加的复合查问，以实现初筛出在经纬度所示矩形区域内的 docId 汇合。

外围代码如下图所示：

public class IndexedGeoBoundingBoxQuery {public static Query create(GeoPoint topLeft, GeoPoint bottomRight, GeoPointFieldMapper.GeoPointFieldType fieldType) {if (!fieldType.isLatLonEnabled()) {throw new IllegalArgumentException("lat/lon is not enabled (indexed) for field [" + fieldType.names().fullName() + "], can't use indexed filter on it");
    }
    //checks to see if bounding box crosses 180 degrees
    if (topLeft.lon() > bottomRight.lon()) {return westGeoBoundingBoxFilter(topLeft, bottomRight, fieldType);
    } else {return eastGeoBoundingBoxFilter(topLeft, bottomRight, fieldType);
    }
}

private static Query westGeoBoundingBoxFilter(GeoPoint topLeft, GeoPoint bottomRight, GeoPointFieldMapper.GeoPointFieldType fieldType) {BooleanQuery.Builder filter = new BooleanQuery.Builder();
    filter.setMinimumNumberShouldMatch(1);
    filter.add(fieldType.lonFieldType().rangeQuery(null, bottomRight.lon(), true, true), Occur.SHOULD);
    filter.add(fieldType.lonFieldType().rangeQuery(topLeft.lon(), null, true, true), Occur.SHOULD);
    filter.add(fieldType.latFieldType().rangeQuery(bottomRight.lat(), topLeft.lat(), true, true), Occur.MUST);
    return new ConstantScoreQuery(filter.build());
}

private static Query eastGeoBoundingBoxFilter(GeoPoint topLeft, GeoPoint bottomRight, GeoPointFieldMapper.GeoPointFieldType fieldType) {BooleanQuery.Builder filter = new BooleanQuery.Builder();
    filter.add(fieldType.lonFieldType().rangeQuery(topLeft.lon(), bottomRight.lon(), true, true), Occur.MUST);
    filter.add(fieldType.latFieldType().rangeQuery(bottomRight.lat(), topLeft.lat(), true, true), Occur.MUST);
    return new ConstantScoreQuery(filter.build());
}
}

第三步：利用 FieldData 缓存 (正向信息) 依据 docId 获取矩形区域中每个坐标点的经纬度，而后利用后面的 Haversine 公式计算跟核心坐标点的间隔，进行准确筛选，失去符合条件的文档汇合。

外围代码如下所示：

// GeoDistanceRangeQuery 类的实现
 @Override
 public Weight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
     final Weight boundingBoxWeight;
     if (boundingBoxFilter != null) {boundingBoxWeight = searcher.createNormalizedWeight(boundingBoxFilter, false);
     } else {boundingBoxWeight = null;}
     return new ConstantScoreWeight(this) {
         @Override
         public Scorer scorer(LeafReaderContext context) throws IOException {
             final DocIdSetIterator approximation;
             if (boundingBoxWeight != null) {approximation = boundingBoxWeight.scorer(context);
             } else {approximation = DocIdSetIterator.all(context.reader().maxDoc());
             }
             if (approximation == null) {
                 // if the approximation does not match anything, we're done
                 return null;
             }
             final MultiGeoPointValues values = indexFieldData.load(context).getGeoPointValues();
             final TwoPhaseIterator twoPhaseIterator = new TwoPhaseIterator(approximation) {
                 @Override
                 public boolean matches() throws IOException {final int doc = approximation.docID();
                     values.setDocument(doc);
                     final int length = values.count();
                     for (int i = 0; i < length; i++) {GeoPoint point = values.valueAt(i);
                         if (distanceBoundingCheck.isWithin(point.lat(), point.lon())) {double d = fixedSourceDistance.calculate(point.lat(), point.lon());
                             if (d >= inclusiveLowerPoint && d <= inclusiveUpperPoint) {return true;}
                         }
                     }
                     return false;
                 }
             };
             return new ConstantScoreScorer(this, score(), twoPhaseIterator);
         }
     };
 }

这是一种非常简单且直观的思路实现了中心点指定半径范畴 POI 的搜寻能力。

简略总结一下要点：

1. 利用中心点坐标和半径确定矩形区域边界。
2. 利用 Bool 查问综合两个 NumericRangeQuery 查问，实现矩形区域初筛。
3. 利用 Haversine 公式计算中心点和矩形区域内每个坐标点间隔，进行第二阶段过滤操作，筛选出最终符合条件的 docId 汇合。

计划尽管简略，然而毕竟实现了 geo_distance 的能力。又不是不能用，对吧？那么该计划有什么问题呢？

3.3 Elasticsearch 2.2 版本

ES2.0 版本的实现有个问题，就是没有很好解决二维组合条件查问的数据筛选。它是别离获取合乎纬度范畴条件的文档汇合和合乎经度范畴条件的文档汇合而后进行交加，初筛了太多有效的文档汇合。

它的解决思路用一张图示意如下：

即抉择了那么多的记录，最终只有经纬度范畴交汇的红色区域是初筛的范畴。

针对下面的问题，ES 2.2 版本引入个性：基于四叉树 (Quadtree) 的地理位置查问(Lucene 5.3 版本实现)。

Quadtree 并非什么简单浅近的数据结构，相比二叉树，多了两个子节点。

作为一种根底的数据结构，Quadtree 利用场景十分宽泛，在图像处理、空间索引、碰撞检测、人生游戏模仿、分形图像剖析等畛域都能够看到它的身影。

在 Elasticsearch 地理位置空间索引问题上，Quadtree 用来示意区间，能够视为前缀树的一种。

• Region quadtree

The region quadtree represents a partition of space in two dimensions by decomposing the region into four equal quadrants, subquadrants, and so on with each leaf node containing data corresponding to a specific subregion. Each node in the tree either has exactly four children, or has no children (a leaf node). The height of quadtrees that follow this decomposition strategy (i.e. subdividing subquadrants as long as there is interesting data in the subquadrant for which more refinement is desired) is sensitive to and dependent on the spatial distribution of interesting areas in the space being decomposed. The region quadtree is a type of trie.

在区间划分上，Quadtree 跟 geohash 的解决思路有些类似。在一维世界，二分能够有限迭代。同理，在二维世界，四分也能够有限迭代。上面这个图能够十分形象展现 Quadtree 的区间划分过程。

ES 2.2 是如何应用 Quadtree 来实现 geo_distance 查问呢？

通常咱们应用一种数据结构，是先基于该数据结构存储数据，而后查问这个数据结构。ES 这里应用 Quadtree 的做法十分奇妙：存储的时候没有感觉用到 Quadtree，查问时却用其查问形式。

morton 编码：在了解 ES 的解决思路前，须要科普一个知识点，那就是 morton 编码。对于 morton 编码，跟 geohash 相似，是一种将二维数据按二进制位穿插编码成一维数据的一种网格编码，其用法和特点跟 geohash 也是相似的。对于 64 位的 morton 码，其经纬度定位精度范畴管制到了厘米级别，对于地理位置场景而言，是十分十分高的精度了。

数据存储：ES2.2 版本之前一个经纬度坐标须要三个字段存储：lat,lon,geohash。有了 Quadtree 后，只须要一个字段存储就能够了。具体的实现思路如下：将 lat,lon 坐标进行映射，使得经纬度的取值范畴从 [-180,180]/[-90,90] 映射到 [0,2147483520](整数好解决)，而后解决成一维的 mortonHash 数值。对于数值字段的解决思路，就又回到了前缀(trie) 的思路，就又回到了相熟的专家参数 precisionStep。在这里的前缀该如何了解？对于一维数据，每个前缀治理一段区间，对于二维数据每个前缀治理一个二维网格区域。例如一个坐标点利用 precisionStep= 9 来划分前缀，其可视化矩形区域如下：

(取 shift=27,36)

(取 shift=36,45)

数据查问：在查问时，首先将查问中心点坐标转换成一个矩形。这个解决思路咱们连续了 ES 2.0 的做法，不生疏了。

例如：对于坐标为(116.433322,39.900255)，半径为 1km 的点，生成的矩形如下所示：

double centerLon = 116.433322;
double centerLat = 39.900255;
double radiusMeters = 1000.0;
GeoRect geoRect = GeoUtils.circleToBBox(centerLon, centerLat, radiusMeters);
System.out.println(geoRect);

用高德 API 生成对应的可视化图形如下：

有了这个矩形后，前面的做法就跟 ES 2.0 有些不同了。ES 2.2 版本的思路是利用 Quadtree 对 整个世界 地图进行网格化。具体的流程如下：

• Quadtree 解决流程

第一步: 以经纬度 (0,0) 为起始中心点，将整个世界切分成 4 个区块。并判断参数生成的矩形在哪个区块。

第二步: 对于矩形区域不在的区域，略过。对于矩形区域所在的区块，持续四分，切成 4 个区块。

第三步： 当满足如下任一条件时，将相干的文档汇合收集起来，作为第一批粗筛的后果。

• 条件一：切分到正好跟前缀的 precisionStep 符合，并且 quad-cell 在矩形外部时。
• 条件二：切分到最小层级 (level=13) 时且 quad-cell 跟矩形区域有交加时。

第四步: 利用 lucene 的 doc_values 缓存机制，获取每个 docId 对应的经纬度，利用间隔公式计算是否在半径范畴内，失去最终的后果。(这个操作也是惯例思路了)

另外 ES 在解决时进行了版本兼容。

例如：ES 2.2 版本对于 geo\_distance 的实现关键点，判断索引版本是否是 V\_2\_2\_0 版本当前创立，如果是则间接用 Lucene 的 GeoPointDistanceQuery 查问类，否则沿用 ES 2.0 版本的 GeoDistanceRangeQuery。

IndexGeoPointFieldData indexFieldData = parseContext.getForField(fieldType);
final Query query;
if (parseContext.indexVersionCreated().before(Version.V_2_2_0)) {query = new GeoDistanceRangeQuery(point, null, distance, true, false, geoDistance, geoFieldType, indexFieldData, optimizeBbox);
} else {distance = GeoUtils.maxRadialDistance(point, distance);
    query = new GeoPointDistanceQuery(indexFieldData.getFieldNames().indexName(), point.lon(), point.lat(), distance);
}
 
if (queryName != null) {parseContext.addNamedQuery(queryName, query);
}

外围代码参考：GeoPointDistanceQuery、GeoPointRadiusTermsEnum

3.4 Elasticsearch 5.0 版本

计划优化的摸索是没有没有止境的，Lucene 的外围工程师 Michael McCandless 受到论文《Bkd-Tree: A Dynamic Scalable kd-Tree》启发，基于 BKD tree 再次降级了地理位置数据索引建模和查问性能。

这个数据结构不仅仅是用于解决地理位置查问问题，更是数值类数据索引建模的通用计划。它能够解决一维的数值，从 byte 到 BigDecimal, IPv6 地址等等；它也能够解决二维乃至于 N 维的数据检索问题。

• LUCENE-6825

This can be used for very fast 1D range filtering for numerics, removing the 8 byte (long/double) limit we have today, so e.g. we could efficiently support BigInteger, BigDecimal, IPv6 addresses, etc.

It can also be used for > 1D use cases, like 2D (lat/lon) and 3D (x/y/z with geo3d) geo shape intersection searches.

…

It should give sizable performance gains (smaller index, faster searching) over what we have today, and even over what auto-prefix with efficient numeric terms would do.

在后面的版本中，对于数值区间查问的解决思路实质上都是 term 匹配，通过前缀实现了一个 term 治理一个区间，从而升高了区间查问须要遍历的 term 数量。而从 ES 5.0 版本开始，彻底优化了数值查问(从一维到 N 维)，其底层是 Lucene 6.0 版本实现的 BKD tree 的独立索引。其实现不仅升高了内存开销，而且晋升了检索和索引速度。

对于 bkd-tree 的原理，其大体思路如下。在面对数值查问区间查问的问题上，大体分为两个档次：

【优化内存查问】：BST(binary-search-tree) > Self-balanced BST > kd-tree。

【优化外存 (硬盘) 查问】：B-tree > K-D-B-tree > BKD tree。

kd-tree 其实就是多维的 BST。例如：

【数据存储】：BKD tree 的外围思路是非常简单的，将 N 维点汇合造成的矩形空间 (southWest,northEast) 递归宰割成更小的矩形空间。跟常见的 kd-tree 不同，当宰割到网格区域外面坐标点的数量小于肯定数量 (比方 1024) 就进行了。

例如：

通过区域的宰割，确保每个区域 POI 的数量大抵相等。

【数据查问】：搜寻的时候，就不再是像 Quadtree 从整个世界开始定位，而是基于以后的点汇合造成的空间来查找。例如以 geo_distance 查问为例。

其流程如下：

第一步: 中心点坐标 + 半径生成一个矩形(shape boundary)。这一步是惯例操作了，后面的版本也都是这么做的。

第二步：该矩形跟 BKD tree 叶子节点造成的矩形 (cell) 进行 intersect 运算，所谓 intersect 运算，就是计算两个矩形的地位关系：相交、内嵌还是不相干。query 和 bkd-tree 造成的区域有三种关系。

对于 CELL\_CROSSES\_QUERY，如果是叶子节点，则须要判断 cell 中的每个 POI 是否合乎 query 的查问条件；否则查问子区间；对于 CELL\_OUTSIDE\_QUERY，间接略过；对于 CELL\_INSIDE\_QUERY，整个 cell 中的 POI 都满足查问条件。

外围代码：LatLonPoint/LatLonPointDistanceQuery

3.5 后续倒退

Geo 查问能力的迭代和变迁，其实也是 Elasticsearch 作为一个数据库对数值查问能力的降级和优化，扩大产品的实用场景，让使用者突破对 Elasticsearch 只能做全文检索的偏见。从全文检索数据库扩大到剖析型数据库，Elasticsearch 还有很长的路要走。

依照 Michael McCandless 的构想，以后的多维数据只能是单个点，然而有些场景须要将形态作为一个维度进行索引。在这种需要下，须要通过一种更普适化的 k -d tree，即 R -Tree 来实现。

路漫漫其修远兮，ES 从 2.0 版本反对 geo-spatial 开始经验 6 年的倒退，曾经走了很远，然而仍然有很多值得摸索的畛域和场景。

参考:

• https://www.elastic.co/cn/blog/lucene-points-6.0
• https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/kdtrees.pdf
• https://www.csee.usf.edu/~tuy/Literature/KDtree-CACM75.pdf