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

每次文件只会被合并到上一层的一个文件。当一层的文件数满足特定个数时，合并到上一层。

所以，LSM 是日志和传统的单文件索引（B+ tree，Hash Index）的中立，他提供一个机制来管理更小的独立的索引文件(sstable) 。
通过管理一组索引文件而不是单一的索引文件，LSM 将B+树等结构昂贵的随机IO变的更快，而代价就是读操作要处理大量的索引文件(sstable)而不是一个，另外还是一些IO被合并操作消耗。
Lucene的Segment设计思想，与LSM类似但又有些不同，继承了LSM中数据写入的优点，但是在查询上只能提供近实时而非实时查询。
Segment在被flush或commit之前，数据保存在内存中，是不可被搜索的，这也就是为什么Lucene被称为提供近实时而非实时查询的原因。读了它的代码后，发现它并不是不能实现数据写入即可查，只是实现起来比较复杂。原因是Lucene中数据搜索依赖构建的索引（例如倒排依赖Term Dictionary），Lucene中对数据索引的构建会在Segment flush时，而非实时构建，目的是为了构建最高效索引。当然它可引入另外一套索引机制，在数据实时写入时即构建，但这套索引实现会与当前Segment内索引不同，需要引入额外的写入时索引以及另外一套查询机制，有一定复杂度。
FST数据字典 Term Dictionary，通常要从数据字典找到指定的词的方法是，将所有词排序，用二分查找即可。这种方式的时间复杂度是 Log(N)，占用空间大小是 O(N*len(term)) 。缺点是消耗内存，存在完整的term，当 term 数达到上千万时，占用内存非常大。
lucene从4开始大量使用的数据结构是FST（Finite State Transducer）。FST有两个优点：

空间占用小，通过读 term 拆分复用及前缀和后缀的重用，压缩了存储空间；
查询速度快，查询仅有 O(len(term)) 时间复杂度

那么 FST 数据结构是什么原理呢？先来看看什么是 FSM (Finite State Machine)，有限状态机，从“起始状态”到“终止状态”，可接受一个字符后，自循环或转移到下一个状态。
而FST呢，就是一种特殊的 FSM，在 Lucene 中用来实现字典查找功能(NLP中还可以做转换功能)，FST 可以表示成FST的形式
举例：对“cat”、 “deep”、 “do”、 “dog” 、“dogs” 这5个单词构建FST（注：必须已排序），结构如下：