ElasticSearch--软知识

蔚落 2023-01-03 01:55 86阅读 0赞

原文网址：[ElasticSearch--软知识\_IT利刃出鞘的博客-CSDN博客][ElasticSearch--_IT_-CSDN]

# 正排索引与倒排索引 #

**其他网址**

[什么是倒排索引？\_starzhou的专栏-CSDN博客][starzhou_-CSDN]  
[倒排索引是什么\_数据库\_weixin\_35833012的博客-CSDN博客][weixin_35833012_-CSDN]

《从Lucene到Elasticsearch：全文检索实战》=> 1.3 倒排索引

**正排索引**

正排索引：去所有的文档中查找，直到找出所有包含关键字的文档。

正排索引组织方法在建立索引的时候结构比较简单，建立比较方便且易于维护；

索引是基于文档建立的，新增文档新增索引块即可，删除文档找到对应的文档号直接删除，索引的更新过程相对来说比较简单。

在查询的时候需对所有的文档进行扫描以确保没有遗漏，这样就使得检索时间大大延长，检索效率低下。

![format_png][]

**倒排索引**

倒排索引（英语：Inverted index），也常被称为反向索引、置入档案或反向档案。

倒排索引：提前建立好关键字与所在文档（可能是多个）的关系，即：一个关键字对应多个文档。查找时，直接通过关键字找文档。

倒排索引以字或词为关键字进行索引，索引中关键字所对应的记录表项记录了出现这个字或词的所有文档，一个表项就是一个字表段，它记录该文档的 ID 和字符在该文档中出现的位置情况。

由于每个字或词对应的文档数量在动态变化，所以倒排索引的建立和维护都较为复杂，但是在查询的时候由于可以一次得到查询关键字所对应的所有文档，所以效率高于正排索引。

在全文检索中，检索的快速响应是一个最为关键的性能，而索引建立由于在后台进行，尽管效率相对低一些，但不会影响整个搜索引擎的效率。

![format_png 1][]

**举个例子**

假设现在有三篇文档，如何使用倒找出包含 “杏仁” 这个词的文档。

<table> 
 <tbody> 
 <tr> 
 <td> 文档ID(docID) </td> 
 <td> 内容 </td> 
 </tr> 
 <tr> 
 <td> 0 </td> 
 <td> 杏仁医生是一款可以帮助医生和患者沟通的APP。 </td> 
 </tr> 
 <tr> 
 <td> 1 </td> 
 <td> 杏仁医生和企鹅医生宣布合并。 </td> 
 </tr> 
 <tr> 
 <td> 2 </td> 
 <td> 我是一名研发工程师。 </td> 
 </tr> 
 </tbody> 
</table>

**正排索引**就是遍历每篇文档，通过字符串匹配算法找到包含 “杏仁” 关键词的文档。一般来说字符串匹配的算法效率都不会很高，因为不管怎么样，都需要将文档整体遍历一次，得到的最终结果如下。（正排索引的做法）

<table> 
 <tbody> 
 <tr> 
 <td> 文档ID(docID) </td> 
 <td> 内容 </td> 
 </tr> 
 <tr> 
 <td> 0 </td> 
 <td> 杏仁医生是一款可以帮助医生和患者沟通的 APP。 </td> 
 </tr> 
 <tr> 
 <td> 1 </td> 
 <td> 杏仁医生和企鹅医生宣布合并。 </td> 
 </tr> 
 </tbody> 
</table>

**这样查询的效率比较低下，若使用倒排索引是如何处理呢。**

1.  首先需要对文档内容进行分词，分词需要词库，分词器等（这里先不管）。假设上面 3 篇文档可以分词成 杏仁，医生，是， 一款， 患者， 沟通， APP， 企鹅，合并，我，研发，工程师。
2.  第二步是去掉一些连词和助词，假设最终文档分词之后的词有 杏仁，医生，患者，沟通，APP，企鹅， 研发，工程师。
3.  第三步是将词和文档 ID 建立映射关系。

<table> 
 <tbody> 
 <tr> 
 <td style="width:215px;"> Key(词) </td> 
 <td> Value（docID） </td> 
 </tr> 
 <tr> 
 <td style="width:215px;"> 杏仁 </td> 
 <td> 0，1 </td> 
 </tr> 
 <tr> 
 <td style="width:215px;"> 医生 </td> 
 <td> 0，1 </td> 
 </tr> 
 <tr> 
 <td style="width:215px;"> 患者 </td> 
 <td> 0 </td> 
 </tr> 
 <tr> 
 <td style="width:215px;"> 沟通 </td> 
 <td> 0 </td> 
 </tr> 
 <tr> 
 <td style="width:215px;"> APP </td> 
 <td> 0 </td> 
 </tr> 
 <tr> 
 <td style="width:215px;"> 企鹅 </td> 
 <td> 1 </td> 
 </tr> 
 <tr> 
 <td style="width:215px;"> 研发 </td> 
 <td> 2 </td> 
 </tr> 
 <tr> 
 <td style="width:215px;"> 工程师 </td> 
 <td> 2 </td> 
 </tr> 
 </tbody> 
</table>

对于映射表的 Key 进行查找是完全匹配的，所以我们通过字符串二进制进行排序，查找 Key 通过二分查找即可。比如查找包含 “杏仁” 的文档的时间复杂度从 O(n) 变成 O(log(n))。

现实生活中的例子可能比较复杂一些，在进行搜索时通常是一个一个问题，比如 “杏仁医生APP是什么”？对于这样一句话首先我们要进行分词，假设可以分成 杏仁，医生，APP 三个词。然后用这三个词作为 Key 去搜索文档。

*  杏仁：匹配到文档 0，1
 *  医生：匹配到文档 0，1
 *  APP：匹配到文档 0

从以上匹配关系能看出，文档 0 匹配到 3 个关键词，文档 1 匹配到 2 个关键词。然后对于匹配的文档如何排序返回，一般来说可能需要通过相关性计算，比如 文档 0 匹配到三个关键词，所以优先返回。但是现实的生活中可能很多文档匹配到的关键词数量一样，如何选择文档优先显示？目前主流的做法是按照多种不同的维度算相关性得分，得分多的靠前。

**结论**

倒排索引有着广泛的应用场景，比如搜索引擎、大规模数据库索引、文档检索、多媒体检索/信息检索领域等等。总之，倒排索引在检索领域是很重要的一种索引机制。

[ElasticSearch--_IT_-CSDN]: https://knife.blog.csdn.net/article/details/112297449
[starzhou_-CSDN]: https://blog.csdn.net/starzhou/article/details/87519973
[weixin_35833012_-CSDN]: https://blog.csdn.net/weixin_35833012/article/details/88096583
[format_png]: /images/20221119/5e2aa73541e74718924305904dcd72a1.png
[format_png 1]: /images/20221119/41cd4e41142041fd83cdb280a6a9bdb8.png