从FST开始回答ES中的倒排索引是什么

A哥（嘿嘿嘿）面试的是后端开发，由于在上家公司的项目当中采用了ES+logstash技术进行日志分析，所以，A哥对DSL语句有所了解，自然也就写到了简历上，于是面试官看了看简历，就开始聊：

“用过ES？”

“是的，之前的项目采用的是ES+logstash做日志采集，当时我负责的是日志分析，DSL语句很熟悉”

"哦，可以说一下DSL当中的模糊查询吗"？听A哥这么说，面试官打起来精神。

"当然...."

一顿狂聊，A哥嘴角都起沫子了，面试官还是有点犹豫，

"你能再说说ES的倒排索引吗？"

ES

A哥推了推眼镜

首先，ES是基于文档和半结构化数据的分布式数据库,也有人说是搜索引擎或者文档分析引擎。它提供实时搜索和分析结构化、半结构化文档、数据的功能，可以实现大数据高效的搜索。

倒排索引

ES采用了倒排索引，聊到倒排索引就必须先提一下索引，这个感念从mysql开始就有了，以遍历新闻文章作为案例，如果对行为的内容添加索引，当发起搜索的时候，就会拿着搜索词到内容当中，一一匹配，而倒排索引则是先使用分词算法，（ES采用的是TF/IDF分词算法,这个A哥不熟，所以没有聊)内容分词，然后制作一个词表来收集词，制作一个映射表来用词指向内容，查询的时候，根据映射表指向内容，那么这种词典 + 映射表的数据结构就是倒排索引了，显然在这种场景下，索引的效率要低于倒排索引。

这里补一张模拟图：

聊到这里，面试官还是意犹未尽

FST

嗯，倒排索引的底层实现是基于：FST（Finite State Transducer）数据结构的，ES基于Lucene ，Lucene在4版本后就开始大量使用FST数据结构，因为es使用前缀字典树 （term index）和后缀字典树（term dictionary）对应Lucene后缀为tip和tim的文件。前缀树中存储词的前缀及对应前缀的词块的后缀字典树的地址，后缀字典树中存储着对应的后缀词块，及每个词对应的id列表地址，例如：

这里还是贴图一张：

而FST的作用是将输入的词构建上面的结构，这样，也就体现出他的好处：

1、通过前缀树，压缩了存储，减小使用空间（这谁不爱）。

2、查询也快，时间复杂度是O(n)，而n就是词的长度

后续

说到这里，面试官露出了满意的微笑：

“你的期望薪资是多少？啥时候能办理入职？” 桀桀桀