深入搜索引擎原理搜索引擎其实也是一个什么系统( 五 ) _云知道

因为存在补位，就会多出很多的空间，这在搜索引擎里宝贵的内存是无法接受的

如果是范围查询，需要用多次或查询，性能并不高

故，涉及到范围不能简单的做字符串补位转换，是否存在及节省空间，又能更高效解决问题的方案呢？
就是：
数值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文件，依次类推。

但是，这会出现一个问题，就是大量的文件被创建，在最坏的情况下，所有的文件都要搜索。
Levelled Compaction
像 LevelDB 和 Cassandra解决这个问题的方法是：实现了一个分层的，而不是根据文件大小来执行合并操作。