开发者学堂课程【Lucene知识精讲与实战（下）：Lucene底层关键字数据结构(FST状态机)】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/701/detail/12352
Lucene底层关键字数据结构(FST状态机)
一、FST原理解析
1、FST也叫状态机，从 Lucene4.0 开始用状态机的结构存储 Lucene 里面索引的关键词，现在用的也是。
2、Lucene 现在采用的数据结构为 FST ,它的特点就是:
优点:内存占用率低，压缩率一般在3倍-20倍之间、模糊查询支持好、查询快。
缺点:结构复杂、输入要求有序、更新不易。
3、已知 FST 要求输入有序,所以 Lucene 会将解析出来的文档单词预先排序，然后构建FST,假设输入为 abd,abe,acf,acg ,那么整个构建过程如下:
（1）a 连 b，b 连 d。
（2）插入 abe。
（3）插入 acf。
（4）插入 acg.
4、比如输入 heimachengxuyuan。
String inputValues[] = ("hei", "ma" ,"cheng","xu" , "yuan", "good"];
long outputValues[] = [0,1,2,3,4,5];
存储结果如下：
只是把上图的结构横过来，左边是起点，右边是终点，没有标数字的是第0个。
输入的数据如下：
hei/0
ma/1
cheng/2
xu/3
yuan/4
good/5
没有重复的字母，所以没有交叉点，如果有重复的直接连，比较节省空间，省内存，查的时候很好查，根据输入的内容直接找即可。类似于树形结构，状态机结构。
5、从 Lucene4.0 一直都用的状态及结构，存的关键字。
存完之后查询时速度非常快，通过关键字找文档号，找到文档，文档词在索引中有出现位置，学习了Lucene底层存储结构（高级）以及存储结构算法，关键字是按照一定结构存储的，取的时候速度比较快，关键字对应词是从哪个文档中找出来的，又对应文档号，通过文档编号找到对应的文档，文档的词的位置在索引中，直接就能找到。通过索引找文档，通过复杂的结构，查找速度是非常快的。
