空间映射&编码
- 墨卡托模型: http://cdn.hujiulong.com/geohey/blog/mercator/play.html
- Geohash 是一种地理编码,由 Gustavo Niemeyer 发明的。它是一种分级的数据结构,把空间划分为网格。Geohash 属于空间填充曲线中的 Z 阶曲线(Z-order curve)的实际应用。
- s2 参考文档 https://github.com/halfrost/Halfrost-Field/blob/master/contents/Go/gospatialsearch.md
空间索引的方法
Lucene的方法:
- 2D空间下的索引:
- geo_point :前缀索引 可以解决附近点和区域内点的搜索
- geo_sharp : 形状索引的实现。 Tessellation Decomposition + Block K Dimensional Trees (Bkd),三角拆分+blockKDtree
-
3D空间下的索引
-
XYShape for Spatial…in Lucene 8.2+ Tessellating & Indexing Virtual Worlds
-
-
lucene geo索引原理参考文档
- https://www.slideshare.net/elasticsearch/geospatial-advancements-in-elasticsearch
- https://portal.opengeospatial.org/files/?artifact_id=90337
索引涉及的数据结构和发展
- 空间数据库中最基本的查询
- 正交范围查询(range query)
- 窗口查询(window query): 在二维坐标数据中,窗口查询是一个坐标对齐矩形,查询目标是数据库中的落在矩形内所有点。
- 支持窗口查询的的多维点索引结构有: k-d B-tree hB-tree Bkd-tree R-tree
kdtree 的发展:
-
K-d tree 1975 Jon Louis Bentley 发明(https://en.wikipedia.org/wiki/K-d_tree)
-
k-d树是每个节点都为k维点的二叉树。所有非叶子节点可以视作用一个超平面把空间分割成两个半空间。节点左边的子树代表在超平面左边的点,节点右边的子树代表在超平面右边的点。选择超平面的方法如下:每个节点都与k维中垂直于超平面的那一维有关。因此,如果选择按照x轴划分,所有x值小于指定值的节点都会出现在左子树,所有x值大于指定值的节点都会出现在右子树。这样,超平面可以用该x值来确定,其法线为x轴的单位向量。
-
基本结构&构建:
- 有很多种方法可以选择轴垂直分割面( axis-aligned splitting planes ),所以有很多种创建k-d树的方法。 最典型的方法如下:
- 随着树的深度轮流选择轴当作分割面。(例如:在三维空间中根节点是 x 轴垂直分割面,其子节点皆为 y 轴垂直分割面,其孙节点皆为 z 轴垂直分割面,其曾孙节点则皆为 x 轴垂直分割面,依此类推。)
- 选择的轴的具体座标的中位数作为作为分割面,同时该点放入子树。
- 这个方法产生一个平衡的k-d树每个叶节点的高度都十分接近。但是平衡的树不一定所有场景都是最佳的
- 有很多种方法可以选择轴垂直分割面( axis-aligned splitting planes ),所以有很多种创建k-d树的方法。 最典型的方法如下:
- 支持:最近邻查询和范围查询
- kdtree的主要问题:
- 因为k-d树是多维排序的,做到平衡比较复杂。不能使用树旋转技术来平衡它们,因为这可能会破坏不变量
- 平衡K-D树的几种算法:divided k-d tree, pseudo k-d tree, k-d B-tree, hB-tree and Bkd-tree
- 制约和限制:
- 维度灾难:在高维空间中,k-d树叶并不能做很高效的* 最邻近搜索。一般的准则是:在k维情况下,数据点数目N应当远远大于2^k时,k-d树的最邻近搜索才可以很好的发挥其作用
-
-
K-D-B-tree (k-dimensional B-tree) k-d-b-tree的目标是提高平衡k-d树的搜索效率,同时提高b-tree面向块的存储以优化外部内存访问
- J. T. Robinson. The K-D-B-tree: A search structure for large multidimensional dynamic indexes. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 10–18, 1981
- https://en.wikipedia.org/wiki/K-D-B-tree
- 原文: http://www.csee.usf.edu/~tuy/Literature/KDB-SIGMOD81.pdf
-
也有简称kdtree的
-
与k-d树类似,k-d-b树组织k维空间中的点,对于范围搜索和多维数据库查询等任务非常有用。k-d-b树通过比较单个域中的元素将空间划分为两个子空间。以二维b树(二维k-d-b树)为例,空间的细分方式与k-d树相同:仅使用其中一个域或轴中的一个点,在这种情况下,所有其他值都小于或大于当前值,并分别落在拆分平面的左侧和右侧。 与k-d树不同,每个半空间不是自己的节点。相反,与b-树一样,k-d-b-树中的节点存储为页,树存储指向根页的指针。
-
kdbtree基本结构
todo: https://en.wikipedia.org/wiki/K-D-B-tree
-
Bkd-tree 是 kd-tree 的扩展 2003发明
-
参考文档:https://users.cs.duke.edu/~pankaj/publications/papers/bkd-sstd.pdf
-
-
hB-tree
- http://www.cs.bu.edu/fac/gkollios/cs591/hb-tree.pdf
空间数据分割树
-
R树 R*树 R+树 X树 M树 线段树 可持久化线段树 希尔伯特R树 优先R树
-
R-tree 1984 Antonin Guttman 发明 (https://en.wikipedia.org/wiki/R-tree https://zh.wikipedia.org/wiki/R%E6%A0%91) 在空间索引应用上非常典型也非常成功。最典型的应用就是:附近两公里的餐厅这样的查询
-
R树也是平衡树(所以所有叶子节点都在同一深度)。它把数据按(内存)页存储,是为磁盘存储设计的(跟数据库的做法相同)。每一页可以存储不超过一个上限的条目,这个上限一般用M表示。R树会在除根节点以外的节点上维持数据条目不小于最小条目数
Elastic search中空间索引和lucene映射历史
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | ? Lucene 8.2+ XYShape for Spatial... Tessellating & Indexing Virtual Worlds Elasticsearch 7.0 bundles Lucene 8 2019年3月26日 - Elasticsearch 6.7.0, based on Lucene 7.7.0. 2019-2-4 6.6.0 Integrate Lucene's LatLonShape (BKD Backed GeoShapes) as default geo_shape Elasticsearch 6.5.0, based on Lucene 7.5.0. Elasticsearch 6.4.0, based on Lucene 7.4.0. 2018年6月13日 Elasticsearch 6.3.0, based on Lucene 7.3.0. Elasticsearch 6.2.0, based on Lucene 7.2.1. 6.6+ "triangle" encoding(Bkd-tree) pre 6.6 terms/postings encoding Elasticsearch 5.4.1, based on Lucene 6.5.1. Elasticsearch 5.4.0, based on Lucene 6.5.0. Elasticsearch 5.3.3, based on Lucene 6.4.2. Elasticsearch 2.4.0, based on Lucene 5.5.2. |
elastic search 7.4 Geo 相关支持情况
- Geo query(https://www.elastic.co/guide/en/elasticsearch/reference/current/geo-queries.html)
- ElasticSearch支持两种类型的地理数据:支持纬度/经度对的地理点域和支持点、线、圆、多边形、多多边形等的地理形状域。
-
支持的查询类型:
- 地理框查询(geoboundingbox)
- 查找具有落在指定矩形中的地理点的文档。(支持经纬度查询数组、字符串、或geohash编码构建的矩形区域进行查询)
- 地理距离查询(geo_distance)
- 查找地理点位于中心点指定距离内的文档。
- 地理多边形查询(geo_polygon)
- 查找指定多边形内具有地理点的文档。
- 地理图形查询(geo_shape)
- 查找具有与指定的地理形状相交、包含或不相交的地理形状的文档。
- 能够过滤带有geo_shap类型字段的索引
- 查询支持直接给的一个形状也支持在另外一个索引里面定义的形状。
- 空间关系运算符:
- intersects-(默认)返回其geo_shape字段与查询几何体相交的所有文档。
- DISJOINT-返回其geo_shape字段与查询几何图形没有任何共同点的所有文档。
- within-返回其geo_shape字段位于查询几何体中的所有文档。
- contains-返回其geo_shape字段包含查询几何图形的所有文档。注意:这只支持使用递归前缀树策略[6.6]
- 地理框查询(geoboundingbox)
-
Shap query(https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-shape-query.html)
- 查询带有shap类型的索引
- 和geo_shape类型查询很像,shap query 用 GeoJSON 或 Well Known Text (WKT)表征形状。
- 支持的空间关系运算:
- intersects-(默认)返回其geo_shape字段与查询几何体相交的所有文档。
- DISJOINT-返回其geo_shape字段与查询几何图形没有任何共同点的所有文档。
- within-返回其geo_shape字段位于查询几何体中的所有文档。
es lbs 查询实例
- 场景:查询当前点在可服务区域里面的所有doc并按照直线距离排序。 poi_zone 代表可服务区域 , poi_point 代表服务提供方所在位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | DELETE /shapes PUT /shapes { "mappings": { "properties": { "poi_zone": { "type": "geo_shape" }, "poi_point": { "type": "geo_point" } } } } PUT /shapes/_doc/deu { "poi_zone": { "type": "polygon", "coordinates" : [ [[116.402508,39.947163], [116.414653,39.94697], [116.414869,39.940083], [116.40276,39.939972],[116.402508,39.947163]] ] }, "poi_point":{ "lon":116.408401, "lat":39.943734 } } PUT /shapes/_doc/deu2 { "poi_zone": { "type": "polygon", "coordinates" : [ [[116.409443,39.947136], [116.420043,39.946997], [116.420043,39.945615], [116.409443,39.945587],[116.409443,39.947136]] ] }, "poi_point":{ "lon":116.414096, "lat":39.946513 } } GET /shapes/_search GET /shapes/_search { "query":{ "bool": { "must": { "match_all": {} }, "filter": { "geo_shape": { "poi_zone": { "relation": "intersects", "shape": { "coordinates": [116.409766,39.946389], "type": "point" } } } } } }, "sort": [{ "_geo_distance": { "poi_point": { "lon": 116.413503, "lat": 39.946776 }, "unit": "km", "order": "asc" } }] } |