经、纬
- 经纬线
经线：也称为“子午线”，是地球表面连接南北两极的弧线（半圆）。经度为0的线称为本初子午线。
纬线：是指地球表面某点随地球自转所形成的轨迹。所有的纬线都相互平行，并与经线垂直，纬线指向东西方向。纬线形状为圈。纬线圈的大小不等,赤道为最大的纬线圈,从赤道向两极纬线圈逐渐缩小,到南、北两极缩小为点。
- 经纬度
经度：地球上一点所在经线与地球球心组成的平面 与 本初子午线与地球球心组成的平面 的二面角。经度每隔15度为一个时区，相差一小时。范围为[-180,180]，东经为正，西经为负。
纬度：地球上一个点与地球球心的连线与赤道面所成的线面角。范围为[-90,90]，北纬为正数，南纬为负数。
查询附近的人 **— 查询范围固定**
如何查询附近的人？一个很容易想到的方案是，把所有人的坐标取出来，计算每个人和自己当前坐标的距离。然后把它们全排序，并且根据距离远近在地图上列出来。其实，这种方案在大规模的系统中并不可行，因为，如果系统中的人数到达了一定的量级，那计算和所有人的距离再排序，这会是一个非常巨大的代价。尽管，可以使用堆排序代替全排序来降低排序代价，但取出所有人的位置信息并计算距离，这本身就是一个很大的开销。
使用非精确检索的思路实现“查找附近的人”
事实上，“查找附近的人”和“检索相关的网页”这两个功能的本质是非常相似的。在这两个功能的实现中，都没有明确的检索目标，也就都不需要非常精准的检索结果，只需要保证质量足够高的结果包含在 Top K 个结果中就够了。所以，非精准 Top K 检索也可以作为优化方案，来实现“查找附近的人”功能。实现如下：
可以通过限定“附近”的范围来减少检索空间。一般来说，同一个城市的人往往会比不同城市的人距离更近。所以，不需要去查询所有的人，只需要去查询自己所在城市的人，然后计算出自己和他们的距离就可以了，这样就能大大缩小检索范围了。那在同一个城市中，也可以优先检索同一个区的用户，来再次缩小检索范围。这就是非精准检索的思路了。
在该方案中，为了进一步提高检索效率，可以将所有的检索空间划分为多个区域并做好编号，然后以区域编号为 key 做好索引。这样，当我们需要查询附近的人时，先快速查询到自己所属的区域，然后再将该区域中所有人的位置取出，计算和每一个人的距离就可以了。如何对区域进行划分和编号？
对于一个完整的二维空间，我们可以用二分的思想将它均匀划分。也就是在水平方向上一分为二，在垂直方向上也一分为二。这样一个空间就会被均匀地划分为四个子空间，这四个子空间，我们可以用两个比特位来编号。在水平方向上，我们用 0 来表示左边的区域，用 1 来表示右边的区域；在垂直方向上，我们用 0 来表示下面的区域，用 1 来表示上面的区域。因此，这四个区域，从左下角开始按照顺时针的顺序，分别是 00、01、11 和 10。
接下来，如果要继续划分空间，我们依然沿用这个思路，将每个区域再分为四块。这样，整个空间就被划分成了 16 块区域，那对应的编号也会再增加两位。比如说，01 编号的区域被划分成了 4 小块，那这四小块的编号就是在 01 后面追加两位编码，分别为 01 00、01 01、 01 10、 01 11。依次类推，我们可以将整个空间持续细分。具体划分到什么粒度，就取决于应用对于“附近”的定义和需求了。
这种区域编码的方式有 2 个优点：
- 区域有层次关系：如果两个区域的前缀是相同的，说明它们属于同一个大区域。
- 区域编码带有分割意义：奇数位的编号代表了垂直切分，偶数位的编号代表了水平切分，这会方便区域编码的计算（奇偶位是从右边以第 0 位开始数起的）。
- 如何快速查询同个区域的人？
区域编码的一个特点：区域编码能将二维空间的两个维度用一维编码表示。因此可以使用一维空间中常见的检索技术快速查找了。比如：可以将区域编码作为 key，用有序数组存储，这样就可以用二分查找进行检索了。
如果有效区域动态增加，还可以使用二叉检索树、跳表等检索技术来索引。在一些系统的实现中，比如 Redis，它就可以直接支持类似的地理位置编码的存入和检索，内部的实现方式是，使用跳表按照区域编码进行排序和查找。此外，如果希望检索效率更高，还可以使用哈希表来实现区域的查询。
这样一来，当查询附近的人时，只需要根据自己的坐标，计算出自己所属区域的编码，然后在索引中查询出所有属于该区域的用户，计算这些用户和自己的距离，最后排序展现即可。
不过，这种非精准检索的方案，会带来一定的误差。即，找到的“附近的人”，其实只是和你同一区域的人而已，并不一定是离你最近的。比如说，你的位置正好处于一个区域的边缘，那离你最近的人，也可能是在你的邻接区域里。
- 如何精准查询附近的人？
对于目标所在的当前区域，可以根据期望的查询半径，以当前区域为中心向周围扩散，从而将周围的区域都包含进来。假设，查询半径正好是一个区域边长的一半，那么只要将目标区域周围一圈，也就是 8 个邻接区域中的用户都加入候选集，这就肯定不会有遗漏了。这时，虽然计算量提高了 8 倍，但可以给出精准的解了。
如果要降低计算量，可以将区域划分的粒度提高一个量级。这样，区域的划分就更精准，在查询半径不变的情况下，需要检索的用户的数量就会更少（查询范围对比见下图中两个红框部分）。
知道了要查询的区域有哪些，那么如何快速确定这些区域的编码呢？
区域编码可以根据奇偶位拆成水平编码和垂直编码这两块，如果一个区域编码是 0110，那它的水平编码就是 01，垂直编码就是 10。那该区域右边一个区域的水平编码的值就比它自己的大 1，垂直编码则相同。因此，通过分解出当前区域的水平编码和垂直编码，对对应的编码值进行加 1 或者减 1 的操作，就能得到不同方向上邻接的区域编码了。
精准查询附近人的检索过程，可以总结为两步：
- 先查询出自己所属的区域编码，再计算出周围 8 个邻接区域的区域编码；
- 在索引中查询 9 次，取出所有属于这些区域中的人，精准计算每一个人和自己的距离，最后排序输出结果。
- Geohash编码
Geohash是一种地理坐标编码系统，可以将地理位置的经纬度按照二分法不断递归逼近实际坐标值，每二分一次就会产生两个二进制数（二分时，小于中间值为0，大于为1），其中，偶数位放经度，奇数位放纬度，最后将每5个二机制数转换为一个十进制数，并用BASE 32 对数字编码就得到GeoHash的最终编码了。
它将真实世界的地理位置根据经纬度进行区域编码，再使用 base32 编码生成一维的字符串编码，使得区域编码在显示和存储上都更加方便。
例如，将 经纬度坐标：[39.983429,116.490273] 转换为Geohash码，最终得到的就是 wx4g6y，步骤如下：
十进制转换为base32编码字符对照表：
不过，Geohash 编码也有缺点。由于 Geohash 编码的一个字符就代表了 5 个比特位，因此每当字符长度变化一个单位，区域的覆盖度变化跨度就是 32 倍（2^5），这会导致区域范围划分不够精细。因此，当发现粒度划分不符合自己应用的需求时，我们其实可以将 Geohash 编码转换回二进制编码的表示方式。这样，编码长度变化的单位就是 1 个比特位了，区域覆盖度变化跨度就是 2 倍，我们就可以更灵活地调整自己期望的区域覆盖度了。实际上，在许多系统的底层实现中，虽然都支持以字符串形式输入 Geohash 编码，但是在内存中的存储和计算都是以二进制的方式来进行的。
查询最近的加油站 _查询范围不固定
在一些基于地理位置的服务中，我们并不关心检索结果是否就在我们“附近”，而是必须要找到“最近”的一批满足我们要求的结果。比如说，我们要查询最近的医院有哪些，查询最近的超市有哪些。那对于这一类的查询，如果当前范围内查不到，系统就需要自动调整查询范围，直到能返回 k 个结果为止。对于这种需要动态调整范围的查询场景，我们有什么高效的检索方案呢？
直接进行多次查询会有什么问题？
以查找最近的加油站为例，一个直观的想法是，我们可以先获得当前位置的 GeoHash 编码，然后根据需求不停扩大查询范围进行多次查询，最后合并查询结果。具体例子如下：
假设当前地址的 GeoHash 编码为 wx4g6yc8，那我们可以先用 wx4g6yc8 去查找当前区域的加油站。如果查询的结果为空，我们就扩大范围。扩大查询范围的思路有两种：
- 一圈一圈扩大范围。即，我们第一次查询周边 8 个邻接区域，如果查询结果依然为空，就再扩大一圈，查询再外圈的 16 个区域。如果还是不够，下一次我们就查询再外圈的 24 个区域，依此类推。由此看出，这种方案的查询次数会成倍地增加，它的效率并不高。
- 每次都将查询单位大幅提高。比如说，直接将 GeoHash 编码去掉最后一位，用 wx4g6yc 再次去查询。如果有结果返回，但是不满足要返回 Top K 个的要求，那我们就继续扩大范围，再去掉一个编码，用 wx4g6y 去查询。就这样不停扩大单位的进行反复查询，直到结果大于 k 个为止。
和第一种查询思路相比，在第二种思路中，我们每次查询的区域单位都得到了大范围的提升，因此，查询次数不会太多。比如说，对于一个长度为 8 的 GeoHash 编码，我们最多只需要查询 8 次（如果要求精准检索，那每次查询就扩展到周围 8 个同样大小的邻接区域即可）。
这个检索方案虽然用很少的次数就能“查询最近的 k 个结果”，但我们还需要保证，每次的查询请求都能快速返回结果。这就要求我们采用合适的索引技术，来处理 GeoHash 的每个层级。
比如说，如果使用基于哈希表的倒排检索来实现，我们就需要在 GeoHash 每个粒度层级上都分别建立一个单独的倒排表。这就意味着，每个层级的倒排表中都会出现全部的加油站，数据会被复制多次，这会带来非常大的存储开销。
我们可以利用 GeoHash 编码一维可排序的特点，使用数组或二叉检索树来存储和检索。由于数组和二叉检索树都可以支持范围查询，因此我们只需要建立一份粒度最细的索引就可以了。这样，当我们要检索更大范围的区域时，可以直接将原来的查询改写为范围查询。具体做法如下：
在检索完 wx4g6yc8 这个区域编码以后，如果结果数量不够，还要检索 wx4g6yc 这个更大范围的区域编码，我们只要将查询改写为“查找区域编码在 wx4g6yc0 至 wx4g6ycz 之间的元素”，就可以利用同一个索引，来完成更高一个层级的区域查询了。同理，如果结果数量依然不够，那下一步我们就查询“区域编码在 wx4g6y00 至 wx4g6yzz 之间的元素”，依此类推。
但是，这种方案有一个缺点，那就是在每次调整范围查询时，都要从头开始进行二分查找，不能充分利用上一次已经查询到的位置信息，这会带来无谓的重复检索的开销。那该如何优化呢？
- 四叉树 _实现动态调整范围
许多系统对于 GeoHash 的底层实现，其实都是使用二进制进行存储和计算的。而二进制区域编码的生成过程，就是一个逐渐二分空间的过程，经过二分后的区域之间是有层次关系的。如果我们把这个过程画下来，它就很像我们之前讲过的树形结构。因此，我们可以尝试用树形结构来进行索引。
四叉树的树根节点代表了整个空间，每个节点的四个分叉分别表示四个子空间。其中，树根和中间节点不存储数据，只记录分叉指针。而数据只记录在最小的区域，也就是叶子节点上。
如果我们从根节点开始，不停地四分下去，直到每个分支的叶子节点都是最小粒度区域。那这样构建出来的四叉树，每个节点都有四个子节点，就叫作满四叉树。
对于满四叉树的每个节点，我们都可以编号。换句话说，我们可以按 00、01、10、11 的编号，来区分满四叉树的四个子节点。这样一来，只要我们从根节点遍历到叶子节点，然后将路径上每个节点的编号连起来，那最后得到的编码就是这个叶子节点所代表的区域编码。
通过下面的例子，我们来看看四叉树是如何完成自动调整范围 Top K 检索的：
假设一个人所属的最小区域编码是 0110，那我们在检索的时候，就以 0110 为 Key，沿着四叉树的对应分支去寻找相应的区域，查询路径为 01-10。如果查找到了叶子节点，并且返回的结果大于 k 个，就可以直接结束检索。如果返回结果不足 k 个，我们就得递归返回到上一层的父节点，然后以这整个父节点的区域编码为目标进行检索。这样，我们就避免了要再次从树根检索到父节点的开销，从而提升了检索效率。
- 非满四叉树 _优化存储空间
尽管，我们使用以最小区域单位为叶子节点的满四叉树，能够很好的提升检索效率，但是在数据稀疏的时候，许多叶子节点中的数据可能是空的，这就很有可能造成大量的空间浪费。为了避免出现空间浪费，我们有一种改进方案是，使用动态节点分裂的非满四叉树。
首先，我们可以给每个叶子节点规定一个容纳上限。比如说，我们可以将上限设置为 n。那么，一开始的四叉树只有一个根节点，这个根节点同时也是叶子节点，它表明了当前的全部空间范围。当有数据加入的时候，我们直接记录在这个节点中，查询时也只查询这个节点即可。因此，当插入的数据个数小于 n 时，我们不需要进行任何复杂的查找操作，只需要将根节点的所有数据读出，然后进行距离计算并排序即可。
随着加入的数据越来越多，如果一个叶子节点的容量超出了容纳上限，我们就将该节点进行分裂。首先，我们将该节点转为中间节点，然后，我们会为这个节点生成 1 至 4 个叶子节点（注意：不是一定要生成 4 个叶子节点），并将原来存在这个节点上的数据都转入到对应的叶子节点中。这样，我们就完成了分裂。
不过，有一种极端的情况是，这些数据都会转入到同一个下层叶子节点上。这时，我们就需要继续分裂这个叶子节点，直到每个叶子节点的容量在阈值下为止。
通过这种动态生成叶节点的方案，我们就能得到一棵非满四叉树。和满四叉树相比，它的叶子节点会更少，而且每个叶子节点表示的区域范围也可能是不一样的。这使得非满四叉树具有更好的空间利用率。非满四叉树的查询过程和满四叉树十分相似，也是根据当前的区域编码，找到对应的叶子节点，并根据该叶子节点上存储的数据数量，判断是否要递归扩大范围。
- 前缀树 _优化GeoHash编码的索引
上面，都是用二进制编码来说明的。如果我们使用了 GeoHash 编码方式，是否也可以用类似的检索技术来索引呢？当然是可以的。实际上，对于字符串的检索，有一种专门的数据结构，叫作前缀树（Trie 树）。
前缀树的思路和四叉树非常相似，它也是一种逐层划分检索空间的数据结构。它的根节点代表了整个检索空间，然后每个中间节点和叶子节点都只存储一个字符，代表一个分支。这样，从根节点到叶子节点的路径连起来，就是一个完整的字符串。因此，当使用 GeoHash 编码来表示区域时，我们可以建立一个前缀树来进行索引，前缀树的每个节点最多会有 32 个子节点。
那如何利用前缀树来检索呢？举个例子，当我们查询 wx4g6yc8 这个区域时，我们会沿着 w-x-4-g-6-y-c-8 的路径，检索到对应的叶子节点，然后取出这个叶子节点上存储的数据。如果这个区域的数据不足 k 个，就返回到父节点上，检索对应的区域，直到返回结果达到 k 个为止。由于整体思路和四叉树是十分相似的。
此外，前缀树除了用在 GeoHash 编码的检索上，也经常用于字典的检索，因此也叫字典树。字典树适用于匹配字符串的检索场合。
- k-d 树
利用树形结构来划分空间提高检索效率的方案，它的应用非常广泛。对于更高维度空间的最近邻检索，我们也可以使用类似的检索方案来划分空间。比如说，在三维空间中，八叉树就是常见的检索方案。那拓展到更高的维度，如 k 维，我们还可以使用 k-d 树（K-Dimensional Tree）来检索。
k-d 树一种是更通用的，对任意维度都可以使用的检索方案。k-d 树和四叉树、八叉树的检索思路并不相同，它在划分子空间的时候，并不是直接将整个空间划分为 2^k 个子空间，而是会选出最有区分度的一个维度，将该维度的空间进行二分，然后对划分出的子空间再进行同样的二分处理，所以，它实际上是一个二叉树。而且，由于它的分支数和维度 k 的具体值无关，因此具有更好的通用性。
事实上，k-d 树在维度规模不大的场景下，确实具有不错的检索效率。但是，在成百上千的超高维度的场景中，k-d 树的性能会急剧下降。那在高维空间中，我们又该如何快速地查找到最近的 k 个对象呢？这个问题，也是搜索引擎和推荐引擎在很多应用场景中都要解决问题。在后面两讲中，我们会对它作详细讲解。
总结
在二维空间中利用四叉树，来快速寻找最近的 k 个元素的方法。
在需要动态调整查询范围的场景下，对于二进制编码的二维空间的最近邻检索问题，我们可以通过四叉树来完成。四叉树可以很好地快速划分查询空间，并通过递归的方式高效地扩大查询范围。
但是满四叉树经常会造成无谓的空间浪费，为了避免这个问题，在实际应用的时候，我们会选择使用非满四叉树来存储和索引编码。
对于 GeoHash 编码的二维空间最近邻检索问题，我们也能通过类似的前缀树来提高检索效率。
讨论
如果一个应用期望支持“查找附近的人”的功能。在初期用户量不大的时候，我们使用什么索引技术比较合理？在后期用户量大的时候，为了加快检索效率，我们又可以采用什么检索技术？为什么？
初期用户量不大的时候：直接可以进行计算具体，这里因为用户的数据是一致在变化的，所以保存的数据结构可以使用 树 和 跳表， 都可以在 log(n) 的时间复杂度中进行查询；
用户量很大的时候，可以使用倒排索引， 以区域的 key 建 倒排索引如果之前的应用选择了 5 个字符串的 Geohash 编码，进行区域划分（区域范围为 4.9 km * 4.9 km），那当我们想查询 10 公里内的人，这个时候该如何进行查询呢？使用什么索引技术会比较合适呢？
这里可以利用区域编码的特性，在同一大区域下的小区域的前缀是一样的。
这里最小的区域范围为 4.9 km 4.9 km ，那么可以向上找大一级的区域，此时的区域范围为 9.8 km 9.8 km 此时还是不满足要查询的范围，所以向上找大一级的区域 此时的区域范围为 18.6 km * 18.6 km 就可以了在非满四叉树的分裂过程中，为什么一个节点不一定会生成 4 个叶子节点？请举例说明。
因为非满四叉树就是为了解决数据稀疏造成的叶子节点中的数据可能是空而导致的空间浪费问题。因此在有些区域的数据为空的情况下，在分裂时就不会生成其空的叶子节点。
文中所有树叶子节点里存放的是该区域内倒排索引的指针，还是倒排索引的所有key？
叶子节点其实存一个数组，记录所有属于这个区域的点就可以了。当然，如果你对于这个数组中的点还有其他的查询要求的话，也可以根据你的需要选用合适的数据结构，比如说不用数组，改用链表，或者位图。
在四叉树从当前子节点去搜索附近子节点时，需要去到上层父节点。如果子节点以双向链表类似B+树，是否可行呢？
如果是满四叉树的话，那么我们可以将所有叶子节点使用双向链表连接起来。当我们查询到一个叶子节点不满足k个结果时，我们需要扩大范围，那么我们可以沿着左右两个方向去扩展。但是，我们是要扩展多少才OK呢？我们并不好判断新节点和当前节点的位置关系。你可以结合我文中的满四叉树的例子看看，如果查询到的节点是0110，其实离它最近的点可能是在1001区域中(见13讲中的区域编码图)，它需要往右边走三个元素才能到达这个节点。因此，遍历并无法判断当前节点和新扩展节点之间的关系。不如递归便捷。
而如果是非满四叉树的话，叶子节点不是一个层级的，并且节点还会分裂。进行链表管理会更加麻烦。
详见：
https://time.geekbang.org/column/article/228924
https://time.geekbang.org/column/article/230018
若有收获，就点个赞吧
0 人点赞
