什么是搜索引擎？深入搜索引擎原理( 四 ) _搜索引擎原理

从以上步骤可以看出， Geo Hash将原来大量的距离计算转化为字符串搜索并缩小范围，再进行小范围的距离计算，进行距离搜索又快又准。
Geo Hash 背后的数学原理

文章插图
如图，我们将二进制编码的结果填入空格。将空间分成四块时，编码顺序为左下角00、左上角01、右下脚10、右上角11 。它是一条类似于 Z 的曲线。当我们将每个块递归分解成更小的子块时，编码顺序是自相似的（分形），每个子块也形成一条 Z 曲线。这种曲线称为Peano空间填充曲线。
这种类型的空间填充曲线的优点是，它将二维空间转化为一维曲线（实际上是分形维数），并且大部分编码距离是相似的，但是皮亚诺空间填充曲线最大的缺点就是突变。有些代码是相邻的，但距离却大不相同。比如0111和1000 ，代码是相邻的，但是距离相差很大。

文章插图
除了Peano填空曲线，还有很多填空曲线，如图，其中效果一般认为是填空曲线。与皮亚诺曲线相比，该曲线没有大的突变。为什么不选择空间填充曲线？可能Peano曲线的思路和计算比较简单。其实Peano曲线就是四叉树的一种线性编码方式。
部分5、数值索引
倒排索引
确定索引内容是可排序的字符串。如果要查找数字，还需要将数字转换为字符串。这样，检索一个数字是没有问题的，但是如果你需要搜索一个范围的值呢？
进行范围搜索，需要转换为数字的字符串也是有序且单调的，只是数字本身的位数不同。最简单的版本是前缀加0 ，比如35、234、1 。补4位得到0035、0234、0001 ，保证：
数字(a) > 数字(b) ===> 字符串(a) > 字符串(b)
此时查询应该使用范围内的所有值或查询，比如查询范围[33, 36) ，对应的查询语法为：
33 || 34 || 35
嗯，它看起来是一个很好的范围查询解决方案，但是，这有 3 个问题：
多少空间合适？总有一个数字会超出您的填充范围。因为有，空间会大很多，这对于搜索引擎中宝贵的内存来说是无法接受的。如果是范围查询，需要多次使用或者查询，性能不好。不高
因此，当涉及到范围时，不能简单地进行字符串补码转换。有没有节省空间，能更高效解决问题的方案？
它是：
数值Trie树，详述如下

文章插图
上面提到了如何索引，那么Query呢？例如，如果我给你一个 423-642 的 Range Query ，如何找到这 6 个词？
我们可以先用 shift==0 找到范围的开始和结束（可能没有等号，比如搜索 422 ，我们也会找到 423）。然后一直向上查找直到我们找到一个共同的祖先（肯定可以找到，因为树的根是所有叶子节点的祖先），对应起点，每次往上走，左边的范围节点必须把它的兄弟节点加到右边，而右范围节点必须添加到左节点的兄弟节点，如果已经到达顶点，则添加左范围节点和右范围节点之间的节点。