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)为分界线。对于大多数业务场景，由经纬度组成的二维坐标曾经足以应答业务问题，可能重庆山城会有些例外。

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

对于立体坐标系，由勾股定理能够不便计算出两个点的间隔。然而因为地球是一个不完满球体，且不同地位有不同海拔高度，所以准确计算两个间隔地位是一个非常复杂的问题。在不思考高度的状况下，二维坐标间隔通常应用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)); }
  1. 如何不便在互联网分享经纬度坐标？

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