Elasticsearch搜索的底层原理

ES搜索是分词后，每个字可以利用FST高速找到倒排索引的位置，并迅速获取文档id列表，大大的提升了性能，减少磁盘IO。

ES的搜索原理就是倒排索引 + TF-IDF打分算法。

倒排索引及其结构

传统的正向索引是通过文章，逐个遍历找到对应关键词的位置。

倒排索引也叫反向索引，是通过词找到词在文档中的出现位置。

在这里插入图片描述

Term（单词）：就是单词，或者叫分词。

Term Index（单词索引）：Term Index存储某些单词的前缀，它在内存中以有限状态转移器FST（Finite State Transducers）的数据结构保存的，可以更快的找到目标单词。

Term Dictionary（单词字典）：维护了单词Term的集合。Term Dictionary的单词非常多，所以会对它们进行排序，查找的时候就可以通过二分查找来查，不需要遍历整个Term Dictionary。

Posting List（倒排列表）：记录了出现过某单词的所有文档ID，和单词在这些文档中出现的位置信息，每条记录叫一个倒排项(Posting)，根据倒排列表，可以知道哪些文档包含目标单词。PostingList会使用Frame Of Reference（FOR）编码技术对里边的数据进行压缩，节约磁盘空间。（PS：实际的倒排列表中并不只是存了文档ID这么简单，还有一些其它的信息，比如：词频（Term出现的次数）、偏移量（offset）等，可以想象成是Python中的元组，或者Java中的对象）

在这里插入图片描述

倒排索引的Term Index实现是基于：FST（Finite State Transducer）数据结构。FST有两个优点：
1）空间占用小。通过对词典中单词前缀和后缀的重复利用，压缩了存储空间；
2）查询速度快。O(len(str))的查询时间复杂度。

FST是将单词拆成单个字母存在节点上，每个节点存一个字母，根节点不存，从根节点出发到特定节点所经过的字母就可以组成目标单词，具体可以参考：
http://examples.mikemccandless.com/fst.py?terms=mop%2F0%0D%0Acat%2F1%0D%0Adog%2F2%0D%0Amemory%2F3%0D%0Amax%2F4&cmd=Build+it%21

FST基于字典树，可以参考：
https://blog.csdn.net/forever_dreams/article/details/81009580

TF-IDF打分算法

TF-IDF打分算法：
TF: 词频，每一个ID中包含的关键字越多，值越高。
DF: 文档频率，即包含关键字的文档ID个数。
IDF: 对DF取倒数：1/DF
TF-IDF分值: TF * IDF。TF-IDF 分值越高则搜索的优先级越高。

在这里插入图片描述
如上图hello出现的在ID中的次数为3，即 DF = 3 ,IDF = 1/3
id为1中 hello 出现1次，TF-IDF = 1/3 = 0.33
id为2中 hello 出现3次，TF-IDF = 3/3 = 1
id为3中 hello 出现1次，TD-IDF = 1/3 = 0.33