文章很长，如果来不及看完，只需要记得，如果你需要一种高效的空间点索引算法来处理海量的空间点查找需求，那么Geohash和Google S2可以帮助到你。...并且 Z 阶曲线还具有局部保序性。 Z 阶曲线通过交织点的坐标值的二进制表示来简单地计算多维度中的点的z值。...解决多维空间点索引需要解决2个问题，第一，如何把多维降为低维或者一维？第二，一维的曲线如何分形？ 1....S2其实是来自几何数学中的一个数学符号 S²，它表示的是单位球。S2 这个库其实是被设计用来解决球面上各种几何问题的。...在 Google S2 中，它是把地球展开成如下的样子： 如果上面展开的6个面，假设都用5阶的希尔伯特曲线表示出来的话，6个面会是如下的样子： 回到 S2 上面来，S2是用的正方形。
并且 Z 阶曲线还具有局部保序性。 Z 阶曲线通过交织点的坐标值的二进制表示来简单地计算多维度中的点的z值。...解决多维空间点索引需要解决2个问题，第一，如何把多维降为低维或者一维？第二，一维的曲线如何分形？ 1....S2其实是来自几何数学中的一个数学符号 S²，它表示的是单位球。S2 这个库其实是被设计用来解决球面上各种几何问题的。...本篇文章讲解以 Go 的这个版本为主。 接下来就看看怎么用 S2 来解决多维空间点索引的问题的。 1. 球面坐标转换 按照之前我们处理多维空间的思路，先考虑如何降维，再考虑如何分形。...S2 Cell ID 数据结构 最后需要来谈谈 S2 Cell ID 数据结构，这个数据结构直接关系到不同 Level 对应精度的问题。 ? 在 S2 中，每个 CellID 是由64位的组成的。
可能你已经发现了一些规律，上图的每个网格中，它们都相同的前缀 wtw3。是的，Geohash 的特点是，两个网格的相同前缀部分越长，就表示它们的位置是邻近的。...如下图，比如确保每个网格的数量不超过10，如果超过，就拆分为四个小的网格。 请注意，四叉树是一种内存数据结构，它不是数据库解决方案。它运行在每个LBS 服务上，数据结构是在服务启动时构建的。...Google S2 和 希尔伯特曲线 Google S2 库是这个领域的另一个重要参与者，和四叉树类似，它是一种内存解决方案。它基于希尔伯特曲线把球体映射到一维索引。...希尔伯特曲线的一个重要特点是 降维，可以把多维空间转换成一维数组，可以通过动画看看它是如何实现的。 在一维空间上的搜索比在二维空间上的搜索效率高得多了。...总结 在本文中，我们设计了一个邻近服务，介绍了4种常见了实现方式，分别是二维搜索，Geohash, 四叉树和 Google S2。
笔者在《高效的多维空间点索引算法 — Geohash 和 Google S2》文章中详细的分析了 Google S2 的算法实现思想。文章发出来以后，一部分读者对它的实现产生了好奇。...前一篇文章《高效的多维空间点索引算法 — Geohash 和 Google S2》里面有谈到这个问题，读者有些疑惑点，这里再最终解释一遍。...至此已经说清楚了希尔伯特曲线的方向和在 Google S2 中生成希尔伯特曲线的阶数，五阶希尔伯特曲线。...关于希尔伯特曲线生成的动画，见上篇《高效的多维空间点索引算法 — Geohash 和 Google S2》—— 希尔伯特曲线的构造方法 这一章节。 那么现在我们再推算55就比较简单了。...---- 空间搜索系列文章： 如何理解 n 维空间和 n 维时空 高效的多维空间点索引算法 — Geohash 和 Google S2 Google S2 中的 CellID 是如何生成的 ？
但是对于空间上的一个点（二维，包括经度和纬度），如何排序呢？又如何索引呢？解决的方法很多，下文介绍一种方法来解决这一问题。...思想：如果能通过某种方法将二维的点数据转换成一维的数据，那样不就可以继续使用B树索引了嘛。那这种方法真的存在嘛，答案是肯定的。...这个问题往往产生在边界处。 解决的思路很简单，我们查询时，除了使用定位点的GeoHash编码进行匹配外，还使用周围8个区域的GeoHash编码，这样可以避免这个问题。 2....注意点 我们已经知道现有的GeoHash算法使用的是Peano空间填充曲线，这种曲线会产生突变，造成了编码虽然相似但距离可能相差很大的问题，因此在查询附近餐馆时候，首先筛选GeoHash编码相似的POI...计算出GeoHash值，然后和数据库中精度更高的GeoHash值做前缀比较 8.空间索引 常见问题：如何根据自己所在位置查询来查询附近50米的POI（point of interest，比如商家、景点等
地理空间索引用于基于空间谓词函数的的地理形状的快速过滤，如：ST_Intersects、ST_Covers 等。 Nebula 使用Google S2库做空间索引。...S2 库将地球表面投影到一个外切的正方体上，然后对正方体的每一个正方形表面递归地进行 n 次四等，最后使用一条空间填充曲线--希尔伯特曲线去连接这些小正方格子的中心。...当 n 无穷大时，这条希尔伯特曲线就几乎填满了正方形。 S2 库使用的是 30 阶的希尔伯特曲线。...因此，地理对象的空间索引就是构建完全覆盖该地理形状的 S2 格子的集合。 当构建地理空间对象的索引时，会构造一个完全覆盖被索引对象的不同 S2 单元格的集合。...S2 单元格来表示它，因此一个 point 对应一个索引条目；对于形状为 linestring 和 polygon 的地理数据，我们使用多个不同 level 的 S2 单元格来覆盖，因此会对应多个索引条目
但是对于空间上的一个点（二维，包括经度和纬度），如何排序呢？又如何索引呢？解决的方法很多，下文介绍一种方法来解决这一问题。 ...思想：如果能通过某种方法将二维的点数据转换成一维的数据，那样不就可以继续使用B树索引了嘛。那这种方法真的存在嘛，答案是肯定的。...GeoHash编码与我们一样（因为在同一个GeoHash区域块上），而较近餐馆的GeoHash编码与我们不一致。...这个问题往往产生在边界处。 ? 解决的思路很简单，我们查询时，除了使用定位点的GeoHash编码进行匹配外，还使用周围8个区域的GeoHash编码，这样可以避免这个问题。...2）我们已经知道现有的GeoHash算法使用的是Peano空间填充曲线，这种曲线会产生突变，造成了编码虽然相似但距离可能相差很大的问题，因此在查询附近餐馆时候，首先筛选GeoHash编码相似的POI点，
Geohash编码中，字符串相似的表示距离相近（特殊情况后文阐述），这样可以利用字符串的前缀匹配来查询附近的POI信息。...但是由于Peano曲线实现更加简单，在使用的时候配合一定的解决手段，可以很好的满足大部分需求，因此TD内部Geohash算法采用的是Peano空间填充曲线。 6. 使用注意点 a. ...GeoHash编码与我们一样（因为在同一个GeoHash区域块上），而较近餐馆的GeoHash编码与我们不一致。...这个问题往往产生在边界处。 解决的思路很简单，我们查询时，除了使用定位点的GeoHash编码进行匹配外，还使用周围8个区域的GeoHash编码，这样可以避免这个问题。 b. ...我们已经知道现有的GeoHash算法使用的是Peano空间填充曲线，这种曲线会产生突变，造成了编码虽然相似但距离可能相差很大的问题，因此在查询附近餐馆时候，首先筛选GeoHash编码相似的POI点，然后进行实际距离计算
寻找父亲节点和孩子节点 首先需要回顾一下希尔伯特曲线的生成方式，具体代码见笔者上篇文章的分析，在这个分析中，有4个方向比较重要，接下来的分析需要，所以把这4个方向的图搬过来。 ?...希尔伯特曲线生成的形式和这4个方向是密切相关的。如果忘记了这部分，还请回看之前笔者的文章分析。...查找父亲节点 在 Google S2 中，由于默认生成出来的 Cell 就是 Level 30 的，也就是 Level 最低的，位于树的最下层的叶子节点。...LCA 查找最近公共祖先 关于 CellID 的计算，还有很关键的一部分就是查找最近公共祖先的问题。问题背景：给定一棵四叉树中任意两个 Level 的 CellID ，如何查询两者的最近公共祖先。...---- 空间搜索系列文章： 如何理解 n 维空间和 n 维时空 高效的多维空间点索引算法 — Geohash 和 Google S2 Google S2 中的四叉树求 LCA 最近公共祖先 GitHub
希尔伯特曲线的起点0在左上角的方格中，终点63在右上角的方格中。...关于 CellID 的生成与数据结构，见笔者这篇《Google S2 中的 CellID 是如何生成的 ？》...全邻居 最后回来文章开头问的那个问题中。如何在四叉树上如何求希尔伯特曲线的邻居 ？经过前文的一些铺垫，再来看这个问题，也许读者心里已经明白该怎么做了。...---- 空间搜索系列文章： 如何理解 n 维空间和 n 维时空 高效的多维空间点索引算法 — Geohash 和 Google S2 Google S2 中的 CellID 是如何生成的 ？...Google S2 中的四叉树求 LCA 最近公共祖先 神奇的德布鲁因序列 四叉树上如何求希尔伯特曲线的邻居 ？
因此，接口只能用于计算近似值的方法，而不是具有各种各样的由所有子类型实现的虚拟方法。 6. Shape 形状 Shape 算是一切图形或者形状的“基类”了。它可以最灵活的方式表示几何多边形。...类似地，代表5个点的形状将具有由一个边缘组成的5个链。 Shape具有允许使用全局编号（边缘ID）或在特定链中访问边的方法。...特别是，如果minLevel> 0或者levelMod> 1，那么即使这不是必需的，它也可能返回比期望的 Cell 更多的值。 在上面的代码实现中标注了4处需要注意的地方。...---- 空间搜索系列文章： 如何理解 n 维空间和 n 维时空 高效的多维空间点索引算法 — Geohash 和 Google S2 Google S2 中的 CellID 是如何生成的 ？...Google S2 中的四叉树求 LCA 最近公共祖先 神奇的德布鲁因序列 四叉树上如何求希尔伯特曲线的邻居 ？ Google S2 是如何解决空间覆盖最优解问题的?
如果人短时间内倒时差可以是双向的，那情况就不同了。...这个背后的数据结构是怎样的呢？第一反应是想，如果可以经纬度分开处理，是不是就可以搞定？...本质上，类似这种二维到一维的降维方式，都属于空间填充曲线，比如说最有名的这种希尔伯特曲线，Google 的 s2geometry 用到。...我认为，这几个选项相对来说还是半夜里自动更新更好，只要被反复频繁唤醒的问题能够解决，其次是关机时更新。...让用户决策也是一种打扰用户的方式，因而不是一个最佳的解决方案，然而，在不经过用户无法做出比较合理的重要决定的时候，是一个可以考虑实行的方案。另外，对于不重要的更新，完全可以等待，攒一批一起操作。
但这种排序方法也只能对一个列的效果是好的，如果参与排序的列很多则会大大降低效果。所以我们需要找到一种方法来解决多列数据的组织优化，来提升dataskipping效果。...它可以将多维空间问题降维到低维或者一维空间问题。常见的有： Z阶曲线(Z-order curve)、皮亚诺曲线（Peano curve）、希尔伯特曲线（Hilbert curve）等。...image.png Z-Order曲线的一个典型应用就是Geohash地理位置编码，它是一种分级的数据结构，把空间划分成网格。...二维空间搜索范围通过Z-Order算法转换之后，可以变换为一维空间的搜索问题。他有一个重要的特性：一个点附近的hash字符串总有公共前缀，并且公共前缀越长，两个点的距离越近。...这给了我们启发，能否使用Z-Order算法来解决上面发现的数据分布问题？事实上是可以的，并且工业界也是这么做的。
但如果是中心点在国家边缘还是会有问题无法计算另一个国家的坐标，如果数据内出现类似中国、俄罗斯这种大范围的国家这数据这计算难度太不现实了。...6个面上，先得到6个大的区间块，然后再通过希尔伯特曲线【Hilbert Curve】进一步的进行划分，把每一个经纬度都转换成一个cell点。...，后面的32位4进制就是希尔伯特曲线一级一级下来的坐标系。...接下来我们考虑如何取出某一点为半径范围的所有块。...所以更多的时候要结合你的业务来看到底需要取多少块，精确到哪个级别。 思考 如果此次需求不是圆形呢？
当在社交网站和其他大多数需要查询半径的应用中使用时，这些偏差都不算问题。但是，在最坏的情况下的偏差可能是0.5%，所以一些地理位置很关键的应用还是需要谨慎考虑。 2. 它是如何工作的？...返回值 计算出的距离会以双精度浮点数的形式被返回。如果给定的位置元素不存在， 那么命令返回空值。...， 但是 GEORADIUSBYMEMBER 的中心点是由给定的位置元素决定的， 而不是像 GEORADIUS 那样， 使用输入的经度和纬度来决定中心点 指定成员的位置被用作查询的中心。...通常使用表示位置的元素使用不同的技术，使用Geohash位置52点整数编码。由于编码和解码过程中所使用的初始最小和最大坐标不同，编码的编码也不同于标准。...查询例子：http://geohash.org/sqdtr74hyu0. 与类似的前缀字符串是附近，但相反的是不正确的，这是可能的，用不同的前缀字符串附近。
寻找父亲节点和孩子节点 首先需要回顾一下希尔伯特曲线的生成方式，具体代码见笔者上篇文章的分析，在这个分析中，有4个方向比较重要，接下来的分析需要，所以把这4个方向的图搬过来。...希尔伯特曲线生成的形式和这4个方向是密切相关的。如果忘记了这部分，还请回看之前笔者的文章分析。...到此读者应该对查找 CellID 孩子节点的流程了然于心了。在 Google S2 中，查找孩子节点的具体实现代码如下。...查找父亲节点 在 Google S2 中，由于默认生成出来的 Cell 就是 Level 30 的，也就是 Level 最低的，位于树的最下层的叶子节点。...LCA 查找最近公共祖先 关于 CellID 的计算，还有很关键的一部分就是查找最近公共祖先的问题。问题背景：给定一棵四叉树中任意两个 Level 的 CellID ，如何查询两者的最近公共祖先。
Geohash提供了像任意精度这样的属性，以及逐渐从代码末尾删除字符以减小其大小（并逐渐失去精度）的可能性。由于逐步精度下降的结果，附近的地方往往（但不总是）呈现类似的前缀。...共享前缀越长，两个地方越接近。 原理 能将一个地球上的点表示成一串字母，并且相近的地点字母的共同前缀越多。这能让位置搜索在开发中变得很容易。它的原理就是依据上述说的geoHash值。...在PHP中的实现与应用 在了解了geo的位置算法原理后，PHP开发过程中我们便可以使用这一定位功能，目前解决位置定位和搜索功能的方案有很多种，基于PHP的，从本人自身实践中推荐一下几种： 利用现成的地图...API实现geo定位、搜索范围、计算距离等功能，如国内的百度、高德等，很多免费API可以使用；如需更大更精确的范围，可以使用google的geo api，缺点就是每日请求次数有限制，如果是企业级别的应用...如果业务需求复杂度不高，在这里并不推荐直接使用PHP写，毕竟效率会比较低，而且这也不是业务关注的重点，所以没必要重新造轮子。
通过GeoHash算法可以大幅度提高在庞大位置数据中的检索效率，同时为应用提供便捷的缓存机制。...，由于这些用户的GeoHash字符串都是WX4ER，所以可以把WX4ER当作key，把该区域的餐馆信息当作value来进行缓存，而如果不使用GeoHash的话，由于区域内的用户传来的经纬度是各不相同的，...我们已经知道现有的GeoHash算法使用的是Peano空间填充曲线，这种曲线会产生突变，造成了编码虽然相似但距离可能相差很大的问题，因此在基于个人位置查询附近Poi信息时，首先筛选GeoHash编码相似的...在研究IPFS存储性能的过程中，由于测试网络节点问题，有很严重的数据传输瓶颈，且不稳定，短期内，很难将需要频繁更新以及百万级别数据的检索逻辑事务放在IPFS这一层中来做。...recursive=false&quiet=false&hash=sha2-256" PS：这边Demo采用的是本地单节点的数据上传，为了保障服务的稳定性，建议使用ipfs-cluster的节点集群解决方案
文章目录 经纬度常识 基本原理 Geohash算法 问题 代码实现 geohash在mysql中的使用 最近需要实现一个功能，查找车辆附近的加油站，如果车和加油站距离在200米以内，则查找成功...在数据库中可以实现在一列上应用索引（某些情况下无法在两列上同时应用索引） GeoHash表示的并不是一个点，而是一个矩形区域 GeoHash编码的前缀可以表示更大的区域。...因此我们就可以通过比较GeoHash匹配的位数来判断两个点之间的大概距离。 问题 geohash算法有两个问题。首先是边缘问题。 ? 如图，如果车在红点位置，区域内还有一个黄点。...相邻区域内的绿点明显离红点更近。但因为黄点的编码和红点一样，最终找到的将是黄点。这就有问题了。 要解决这个问题，很简单，只要再查找周边8个区域内的点，看哪个离自己更近即可。 另外就是曲线突变问题。...不过仍然有一个问题需要解决，就是如何计算周边的8个区域key值呢 假设我们计算的key值是6位，那么二进制位数就是 6*5 = 30位，所以经纬度分别是15位。我们以纬度为例，纬度会均分15次。
GeoHash编码存在的问题 GeoHash 虽然能解决从二维到一维的转变，但也存在一些问题。...但是如果现在不仅仅是三个位置，如果是几十万甚至是更多的位置，我们应该如何处理呢？如果还是求任意两个位置的欧式距离显然那是灾难性的。...而GeoHash对这些位置进行编码，通过前缀匹配，匹配度越高的位置就越相近，但是仔细想想如果两个位置被分到两个不同的矩形区域中，它们的匹配度很低，但是两个位置距离很近，比如下面的和红点距离近的绿点显然和红点是在一个矩形区域中...出现这种问题的原因是因为GeoHash采用了Peano空间填充曲线，填充过程 ?...解决的思路很简单，我们查询时，除了使用定位点的GeoHash编码进行匹配外，还使用周围8个区域的GeoHash编码，这样可以避免这个问题。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
