深入搜索引擎原理( 四 ) _搜索引擎

文章插图

除Peano空间填充曲线外，还有很多空间填充曲线，如图所示，其中效果公认较好是Hilbert空间填充曲线，相较于Peano曲线而言，Hilbert曲线没有较大的突变。为什么GeoHash不选择Hilbert空间填充曲线呢？可能是Peano曲线思路以及计算上比较简单吧，事实上，Peano曲线就是一种四叉树线性编码方式。
Part 5、数值索引Lucene的倒排索引决定，索引内容是一个可排序的字符串，如果要查找一个数字，那么也需要将数字转成字符串。这样，检索一个数字是没问题的，如果需要搜索一个数值范围，怎么做呢？
要做范围查找，那么要求数字转成的字符串也是有序并单调的，但数字本身的位数是不一样的，最简单的版本就是前缀补0，比如 35, 234, 1 都补成 4 位，得到 0035, 0234, 0001，这样能保证：
数字(a) > 数字(b) ===> 字符串(a) > 字符串(b)这时候，查询应该用范围内的所有数值或查询，比如查询 [33, 36) 这个范围，对应的查询语法是：
33 || 34 || 35嗯看起来很好的解决了范围查询，但是，这样存在3个问题：

补位多少合适呢？总有一个数字会超出你的补位范围
因为存在补位，就会多出很多的空间，这在搜索引擎里宝贵的内存是无法接受的
如果是范围查询，需要用多次或查询，性能并不高

故，涉及到范围不能简单的做字符串补位转换，是否存在及节省空间，又能更高效解决问题的方案呢？
就是：
数值Trie树，下面详细介绍

文章插图

上面说了怎么索引，那么Query呢？比如我给你一个Range Query从423-642，怎么找到那6个term呢？
我们首先可以用shift==0找到范围的起点后终点（有可能没有相等的，比如搜索422，也会找到423）。然后一直往上找，直到找到一个共同的祖先（肯定能找到，因为树根是所有叶子节点的祖先），对应起点，每次往上走的时候, 左边范围节点都要把它右边的兄弟节点都加进去, 右边范围节点都要把它左边的兄弟节点加进去, 若已经到达顶点, 则是将左边范围节点和右边范围节点之间的节点加进行去
查找423到642之间的具体的区间：

423-429,640-642
43-49,60-63
5-5

另外还有一个问题，比如423会被分词成423，42和4，那么4也会被分词成4，那么4表示哪个呢？
所以intToPrefixCoded方法会额外用一个char来保存shift：buffer[0] = (char)(SHIFT_START_INT + shift);
比如423分词的4的shift是2（这里是10进制的例子，二进制也是同样的），423分成423的shift是0，4的shift是0，因此前缀肯定比后缀大。
最后，由于索引在判断时无需感知是否是数字，可以把所有的数字当成二进制处理，这样在存储和效率上更高。
三、搜索引擎的极致优化LSM思想
LSM (Log Structured Merge Tree)，最早是谷歌的 “BigTable” 提出来的，目标是保证写入性能，同时又能支持较高效率的检索，在很多 NoSQL 中都有使用，Lucene 也是使用 LSM 思想来写入。
普通的B+树增加记录可能需要执行 seek+update 操作，这需要大量磁盘寻道移动磁头。而 LSM 采用记录在文件末尾，顺序写入减少移动磁头/寻道，执行效率高于 B+树。具体 LSM 的原理是什么呢？
为了保持磁盘的IO效率，lucene避免对索引文件的直接修改，所有的索引文件一旦生成，就是只读，不能被改变的。其操作过程如下：

在内存中保存新增的索引, 内存缓存（也就是memtable）;
内存中的索引数量达到一定阈值时，触发写操作，将这部分数据批量写入新文件，我们称为segment；也就是 sstable文件
新增的segment生成后，不能被修改；
update操作和delete操作不会立即导致原有的数据被修改或者删除，会以Append的方式存储update和delete标记;
最终得到大量的 segment，为了减少资源占用，也提高检索效率，会定期的将这些小的 segment 合并成大的 segment，由于map中的数据都是排好序的，所以合并也不会有随机写操作；
通过merge，还可以把update和delete操作真正生效，删除多余的数据，节省空间。

合并的过程：
Basic Compaction
每个文件固定N个数量，超过N，则新建一个sstable；当sstable数大于M，则合并一个大sstable；当大sstable的数量大于M，则合并一个更大的sstable文件，依次类推。