搜索引擎工作倒排索引原理和过程

这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件
一、倒排索引简介
倒排索引（英文：Inverted Index），是一种索引方法，常被用于全文检索系统中的一种单词文档映射结构。现代搜索引擎绝大多数的索引都是基于倒排索引来进行构建的，这源于在实际应用当中，用户在使用搜索引擎查找信息时往往只输入信息中的某个属性关键字，如一些用户不记得歌名，会输入歌词来查找歌名；输入某个节目内容片段来查找该节目等等。
面对海量的信息数据，为满足用户需求，顺应信息时代快速获取信息的趋势，聪明的开发者们在进行搜索引擎开发时对这些信息数据进行逆向运算，研发了“关键词——文档”形式的一种映射结构，实现了通过物品属性信息对物品进行映射时，可以帮助用户快速定位到目标信息，从而极大降低了信息获取难度。倒排索引又叫反向索引，它是一种逆向思维运算，是现代信息检索领域里面最有效的一种索引结构。
二、关于倒排索引
搜索引擎通常检索的场景是：给定几个关键词，找出包含关键词的文档。
怎么快速找到包含某个关键词的文档就成为搜索的关键。这里我们借助单词——文档矩阵模型，
通过这个模型我们可以很方便知道某篇文档包含哪些关键词，某个关键词被哪些文档所包含。
单词-文档矩阵的具体数据结构可以是倒排索引、签名文件、后缀树等。
倒排索引源于实际应用中需要根据属性的值来查找记录，lucene是基于倒排索引实现的。
这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。
由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。
带有倒排索引的文件我们称为倒排索引文件，简称倒排文件(inverted file)。
倒排索引一般表示为一个关键词，然后是它的频度（出现的次数），位置（出现在哪一篇文章或网页中，及有关的日期，作者等信息），它相当于为互联网上几千亿页网页做了一个索引，好比一本书的目录、标签一般。读者想看哪一个主题相关的章节，直接根据目录即可找到相关的页面。不必再从书的第一页到最后一页，一页一页的查找。
三、倒排索引概述：
在关系数据库系统里，索引是检索数据最有效率的方式,但对于搜索引擎，它并不能满足其特殊要求：
1、海量数据：搜索引擎面对的是海量数据，像Google、百度这样大型的商业搜索引擎索引都是亿级甚至百亿级的网页数量 ，面对如此海量数据 ,使得数据库系统很难有效的管理。
2、数据操作简单：搜索引擎使用的数据操作简单 ,一般而言 ,只需要增、 删、 改、 查几个功能 ,而且数据都有特定的格式 ,可以针对这些应用设计出简单高效的应用程序。而一般的数据库系统则支持大而全的功能 ,同时损失了速度和空间。最后 搜索引擎面临大量的用户检索需求 ,这要求搜索引擎在检索程序的设计上要分秒必争 ,尽可能的将大运算量的工作在索引建立时完成 ,使检索运算尽量的少。一般的数据库系统很难承受如此大量的用户请求 ,而且在检索响应时间和检索并发度上都不及我们专门设计的索引系统。
四、倒排索引由两个部分组成：单词词典和倒排文件。
(1) .倒排文件
所有单词的倒排列表顺序的存储在磁盘的某个文件里，这个文件即被称为倒排文件，倒排文件是存储倒排索引的物理文件。
(2) .单词词典
单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。
单词词典是倒排索引中非常重要的组成部分，它是用来维护文档集合中所有单词的相关信息，同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时，根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表。
对于一个规模很大的文档集合来说，可能包含了几十万甚至上百万的不同单词，
快速定位某个单词直接决定搜索的响应速度，所以我们需要很高效的数据结构对单词词典进行构建和查找。
常用的数据结构包含哈希加链表和树形词典结构。