人气排行榜搜索引擎核心技术详解3—搜索引擎索引
倒排索引是搜索引擎用来快速查找包含某个单词的文档集合的数据结构。
倒排索引由单词词典和所有单词对应的倒排列表构成。
倒排列表由倒排列表项构成，一般倒排列表项包含文档ID、单词出现次数和单词在文档出现位置的信息，而文档ID则采取文档编号差值方式编码。
3种常用的建立倒排索引的方法是：两遍文档遍历法、排序法、归并法。
常用的索引更新策略有4种：完全重建策略、再合并策略、原地更新策略及混合策略。
目前有两种常见的查询处理机制，一种被称做一次一文档方式，另一种被称为一次一单词方式。
实现多字段索引有3种方式：多索引方式、倒排列表方式和扩展列表方式。
较常见的支持短语查询的技术方法包括：位置信息索引、双词索引及短语索引这3类，为了能够更有效地利用存储和计算资源，也可以将三者结合使用。
目前常用的分布式索引方案包括两种：按文档对索引划分和按单词对索引划分。
索引其实在日常生活中是很常见的，比如书籍的目录就是一种索引结构，目的是为了让人们能够更快地找到相关章节内容。再比如像haol23这种类型的导航网站本质上也是互联网页面中的索引结构，目的类似，也是为了让用户能够尽快找到有价值的分类网站。
在计算机科学领域，索引也是非常常用的数据结构。其根本目的是为了在具体应用中加快查找速度。比如在数据库中，在很多高效数据结构中，都会大量采用索引来提升系统效率。
单词一文档矩阵是表达两者之间所具有的一种包含关系的概念模型。
搜索引擎的索引其实就是实现单词一文档矩阵的具体数据结构。可以有不同的方式来实现上述概念模型，比如倒排索引、签名文件、后缀树等方式。但是各项实验数据表明，倒排索引是单词到文档映射关系的最佳实现方式。
文档（Document)：一般搜索引擎的处理对象是互联网网页，而文档这个概念要更宽泛些，代表以文本形式存在的存储对象。相比网页来说，涵盖更多形式，比如Word、PDF、html、XML等不同格式的文件都可以称为文档，再比如一封邮件、一条短信、一条微博也可以称为文档。
文档集合（DocumentCollection)：由若干文档构成的集合称为文档集合。比如海量的互联网网页或者说大量的电子邮件，都是文档集合的具体例子。
文档编号（DocumentID）：在搜索引擎内部，会为文档集合内每个文档赋予一个唯一的内部编号，以此编号来作为这个文档的唯一标识，这样方便内部处理。每个文档的内部编号即称为文档编号，后文有时会用DocID来便捷地代表文档编号。
单词编号（WordID)：与文档编号类似，搜索引擎内部以唯一的编号来表征某个单词，单词编号可以作为某个单词的唯一表征。
倒排索引（InvertedIndex)：倒排索引是实现单词一文档矩阵的一种具体存储形式。通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：单词词典和倒排文件。
单词词典（Lexicon)：搜索引擎通常的索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息及指向倒排列表的指针。
倒排列表（PostingList)：倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项（Posting）。根据倒排列表，即可获知哪些文档包含某个单词。
倒排文件（InvertedFile)：所有单词的倒排列表往往顺序地存储在磁盘的某个文件里，这个文件即被称为倒排文件，倒排文件是存储倒排索引的物理文件。
文档频率信息代表了在文档集合中有多少个文档包含某个单词，之所以要记录这个信息，其原因与单词频率信息一样，这个信息在搜索结果排序计算中是一个非常重要的因子。而单词在某个文档中出现位置的信息并非索引系统一定要记录的，在实际的索引系统里可以包含，也可以选择不包含这个信息，之所以如此是因为这个信息对于搜索系统来说并非必需，位置信息只有在支持短语查询的时候才能够派上用场。
带有单词频率、文档频率和出现位置信息的倒排索引
单词词典是倒排索引中非常重要的组成部分，它用来维护文档集合中出现过的所有单词的相关信息，同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时，根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表，并以此作为后续排序的基础。
对于一个规模很大的文档集合来说，可能包含几十万甚至上百万的不同单词，能否快速定位某个单词，这直接影响搜索时的响应速度，所以需要高效的数据结构来对单词词典进行构建和查找，常用的数据结构包括哈希加链表结构和树形词典结构。
这种词典结构主要由两个部分构成，主体部分是哈希表，每个哈希表项保存一个指针，指针指向冲突链表，在冲突链表里，相同哈希值的单词形成链表结构。之所以会有冲突链表，是因为两个不同单词获得相同的哈希值，如果是这样，在哈希方法里被称做是一次冲突，可以将相同哈希值的单词存储在链表里，以供后续查找。
建立过程：在建立索引的过程中，词典结构也会相应地被构建出来。比如在解析一个新文档的时候，对于某个在文档中出现的单词T，首先利用哈希函数获得其哈希值，之后根据哈希值对应的哈希表项读取其中保存的指针，就找到了对应的冲突链表。如果冲突链表里已经存在这个单词，说明单词在之前解析的文档里已经出现过。如果在冲突链表里没有发现这个单词，说明该单词是首次碰到，则将其加入冲突链表里。通过这种方式，当文档集合内所有文档解析完毕时，相应的词典结构也就建立起来了。
响应查询：在响应用户查询请求时，其过程与建立词典类似，不同点在于即使词典里没出现过某个单词，也不会添加到词典内。假设用户输入的查询请求为单词3，对这个单词进行哈希，定位到哈希表内的2号槽，从其保留的指针可以获得冲突链表，依次将单词3和冲突链表内的单词比较，发现单词3在冲突链表内，于是找到这个单词，之后可以读出这个单词对应的倒排列表来进行后续的工作，如果没有找到这个单词，说明文档集合内没有任何文档包含单词，则搜索结果为空。
B树（或者B树）是另外一种高效查找结构。B树与哈希方式查找不同，需要字典项能够按照大小排序（数字或者字符序），而哈希方式则无须数据满足此项要求。
B树形成了层级查找结构，中间节点用于指出一定顺序范围的词典项目存储在哪个子树中，起到根据词典项比较大小进行导航的作用，最底层的叶子节点存储单词的地址信息，根据这个地址就可以提取出单词字符串。
倒排列表用来记录有哪些文档包含了某个单词。一般在文档集合里会有很多文档包含某个单词，每个文档会记录文档编号（DocID)，单词在这个文档中出现的次数（TF）及单词在文档中哪些位置出现过等信息，这样与一个文档相关的信息被称做倒排索引项（Posting)，包含这个单词的一系列倒排索引项形成了列表结构，这就是某个单词对应的倒排列表。在文档集合中出现过的所有单词及其对应的倒排列表组成了倒排索引。
在实际的搜索引擎系统中，并不存储倒排索引项中的实际文档编号，而是代之以文档编号差值（D-Gap)。文档编号差值是倒排列表中相邻的两个倒排索引项文档编号的差值，一般在索引构建过程中，可以保证倒排列表中后面出现的文档编号大于之前出现的文档编号，所以文档编号差值总是大于0的整数。如图3-10所示的例子中，原始的3个文档编号分别是187、196和199，通过编号差值计算，在实际存储的时候就转化成了：187、9、3。
之所以要对文档编号进行差值计算，主要原因是为了更好地对数据进行压缩，原始文档编号一般都是大数值，通过差值计算，就有效地将大数值转换为了小数值，而这有助于增加数据的压缩率。
完全是在内存里完成索引的创建过程的，而另外两种方法则是通过内存和磁盘相互配合来完成索引建立任务的。
第一遍文档遍历：在第一遍扫描文档集合时，该方法并没有立即开始建立索引，而是收集一些全局的统计信息。比如文档集合包含的文档个数N，文档集合内所包含的不同单词个数M，每个单词在多少个文档中出现过的信息DF。将所有单词对应的DF值全部相加，就可以知道建立最终索引所需的内存大小是多少，因为一个单词对应的DF值如果是10，说明有10个文档包含这个单词，那么这个单词对应的倒排列表应该包含10项内容，每一项记载某个文档的文档ID和单词在该文档对应的出现次数TF。
在获得了上述3类信息后，就可以知道最终索引的大小，于是在内存中分配足够大的空间，用来存储倒排索引内容。在内存中可以开辟连续存储区域，因为第一遍扫描已经获得了每个单词的DF信息，所以将连续存储区划分成不同大小的片段，词典内某个单词根据自己对应的DF信息，可以通过指针，指向属于自己的内存片段的起始位置和终止位置，将来在第二遍扫描时，这个单词对应的倒排列表信息会被填充进这个片段中。
综上所述，第一遍扫描的主要目的是获得一些统计信息，并根据统计信息分配内存等资源，同时建立好单词相对应倒排列表在内存中的位置信息，即主要做些资源准备工作。
第二遍文档遍历：在第二遍扫描的时候，开始真正建立每个单词的倒排列表信息，即对某个单词来说，获得包含这个单词的每个文档的文档ID，以及这个单词在文档中的出现次数TF，这样就可以不断填充第一遍扫描所分配的内存空间。当第二遍扫描结束的时候，分配的内存空间正好被填充满，而每个单词用指针所指向的内存区域“片段”，其起始位置和终止位置之间的数据就是这个单词对应的倒排列表。
经过两遍扫描完成索引建立后，即可将内存的倒排列表和词典信息写入磁盘，这样就完成了建立索引的过程。从上述流程可以看出，索引的构建完全是在内存中完成的，这就要求内存一定要足够大，否则如果文档集合太大，内存未必能够满足需求。
从另外一个角度看，在建立索引的过程中，从磁盘读取文档并解析文档基本是最消耗时间的一个步骤，而两遍扫描法因为要对文档集合进行两遍遍历，所以从速度上不占优势，在实际中采用这种方法的系统并不常见。
两遍遍历法在建立索引的过程中，对内存的消耗要求较高，不同的文档集合包含文档数量大小不同，其所需内存大小是不确定的。当文档集合非常大时，可能因内存不够，导致无法建立索引。
中间结果内存排序
排序的原则是：主键是单词ID，即首先要按照单词ID由小到大排序；次键是文档ID，即在相同单词ID的情况下，按照文档ID由小到大排序。通过以上方式，三元组变为有序形式。
为了腾出内存空间，将排好序的三元组写入磁盘临时文件中，这样就空出内存来进行后续文档的处理。这里需要注意的是：在建立索引的过程中，词典是一直存储在内存中的，每次清空内存只是将中间结果写入磁盘。随着处理文档的增加，词典占用的内存会逐渐增加，由于分配内存是固定大小，而词典占用内存越来越大，也就是说，越往后，可用来存储三元组的空间是越来越少的。
改进：每次将内存中数据写入磁盘时，包括词典在内的所有中间结果信息都被写入磁盘，这样内存所有内容都可以被清空，后续建立索引可以使用全部的定额内存。
分为两个大的阶段，首先在内存里维护中间结果，当内存占满后，将内存数据写入磁盘临时文件，第二阶段对临时文件进行归并形成最终索引。
尽管从整体流程看，和排序法大致相同，但是在具体实现方式上有较大差异。
首先，排序法在内存中存放的是词典信息和三元组数据，在建立索引的过程中，词典和三元组数据并没有直接的联系，词典只是为了将单词映射为单词ID。而归并法则是在内存中建立一个完整的内存索引结构，相当于对目前处理的文档子集单独在内存中建立起了一整套倒排索引，和最终索引相比，其结构和形式是相同的，区别只是这个索引只是部分文档的索引而非全部文档的索引。
其次，在将中间结果写入磁盘临时文件时，归并法会将整个内存的倒排索引写入临时文件，对于某个单词的倒排列表在写入磁盘文件时，将词典项放在列表最前端，之后跟随相应的倒排列表，这样依次将单词和对应的倒排列表写入磁盘文件，随后彻底清空所占内存。而排序法只是将三元组数据排序后写入磁盘临时文件，词典作为一个映射表一直存储在内存中。
在最后的临时文件合并为最终索引的过程中，两者也有差异。排序法因为保存的是有序三元组信息，所以在合并时，是对同一单词的三元组依次进行合并；而归并法的临时文件则是每个单词对应的部分倒排列表，所以在合并时针对每个单词的倒排列表进行合并，形成这个单词的最终倒排列表。另外，归并法在最后的合并过程中形成最终的词典信息。
如果搜索引擎需要处理的文档集合是静态集合，那么在索引建立好之后，就可以一直用建好的索引响应用户查询请求。但是，在真实环境中，搜索引擎需要处理的文档集合往往是动态集合，即在建好初始的索引后，后续不断有新文档进入系统，同时原先的文档集合内有些文档可能被删除或者内容被更改。典型的例子就是桌面搜索，当新下载一篇文档，那么搜索系统需要及时将其纳入，删除某篇文档也需要在非常短的时间内在搜索结果里体现出来。大多数搜索引擎面临的应用场景是类似的动态环境。
动态索引中，有3个关键的索引结构：倒排索引、临时索引和已删除文档列表。
倒排索引就是对初始文档集合建立好的索引结构，一般单词词典存储在内存，对应的倒排列表存储在磁盘文件中。
临时索引是在内存中实时建立的倒排索引，其结构和前述的倒排索引是一样的，区别在于词典和倒排列表都在内存中存储。当有新文档进入系统时，实时解析文档并将其追加进这个临时索引结构中。
已删除文档列表则用来存储已被删除的文档的相应文档ID，形成一个文档ID列表。这里需要注意的是：当一篇文档内容被更改，可以认为是旧文档先被删除，之后向系统内增加一篇新的文档，通过这种间接方式实现对内容更改的支持。当系统发现有新文档进入时，立即将其加入临时索引中。有文档被删除时，则将其加入删除文档队列。文档被更改时，则将原先文档放入删除队列，解析更改后的文档内容，并将其加入临时索引中。通过这种方式可以满足实时性的要求。
如果用户输入查询请求，则搜索引擎同时从倒排索引和临时索引中读取用户查询单词的倒排列表，找到包含用户查询的文档集合，并对两个结果进行合并，之后利用删除文档列表进行过滤，将搜索结果中那些已经被删除的文档从结果中过滤，形成最终的搜索结果，并返回给用户。这样就能够实现动态环境下的准实时搜索功能。
动态索引通过在内存中维护临时索引，可以实现对动态文档和实时搜索的支持。但是服务器内存总是有限的，随着新加入系统的文档越来越多，临时索引消耗的内存也会随之增加。当最初分配的内存将被使用完时，要考虑将临时索引的内容更新到磁盘索引中，以释放内存空间来容纳后续的新进文档，此时要考虑合理有效的索引更新策略。
常用的索引更新策略有4种：完全重建策略、再合并策略、原地更新策略及混合策略。
完全重建策略是一个相当直观的方法，当新增文档达到一定数量，将新增文档和原先的老文档进行合并，然后利用前述章节提到的建立索引的方式，对所有文档重新建立索引。新索引建立完成后，老的索引被遗弃释放，之后对用户查询的响应完全由新的索引负责。
因为重建索引需要较长时间，在进行索引重建的过程中，内存中仍然需要维护老的索引，来对用户的查询做出响应。只有当新索引完全建立完成后，才能释放旧的索引，将用户查询响应切换到新索引上。
这种重建策略比较适合小文档集合，因为完全重建索引的代价较高，但是目前主流商业搜索引擎一般是采用此方式来维护索引的更新的，这与互联网本身的特性有关。
有新增文档进入搜索系统时，搜索系统在内存维护临时倒排索引来记录其信息，当新增文档达到一定数量，或者指定大小的内存被消耗完，则把临时索引和老文档的倒排索引进行合并，以生成新的索引。
在实际的搜索系统中，再合并策略按照以下步骤进行索引内容的更新。
当新增文档进入系统，解析文档，之后更新内存中维护的临时索引，文档中出现的每个单词，在其倒排列表末尾追加倒排列表项，这个临时索引可称为增量索引。
一旦增量索引将指定的内存消耗光，此时需要进行一次索引合并，即将增量索引和老的倒排索引内容进行合并，需要注意的是：倒排文件里的倒排列表存放顺序已经按照索引单词字典顺序由低到高进行了排序，增量索引在遍历词典的时候也按照字典序由低到高排列，这样对老的倒排文件只需进行一遍扫描，并可顺序读取，减少了文件操作中比较耗时的磁盘寻道时间，可以有效地提高合并效率。
在合并过程中，需要依次遍历增量索引和老索引单词词典中包含的单词及其对应的倒排列表，可以用两个指针分别指向两套索引中目前需要合并的单词。
如果两个单词指针指向的单词相同，说明这个单词在增量索引和老索引中同时出现，则将老索引中这个单词对应的倒排列表写入新索引的倒排列表，然后把增量索引中这个单词对应的倒排列表追加到其后，这样就完成了这个单词所有倒排列表的合并。
当两个索引的所有单词都遍历完成后，新索引建成，此时可以遗弃释放老索引，使用新索引来响应用户查询请求。
同样地，在按照这个策略进行索引合并的过程中，为了能够响应用户查询，在合并索引期间，需要使用老索引响应用户查询请求。
优点：再合并策略是效率非常高的一种索引更新策略，主要原因在于：在对老的倒排索引进行遍历时，因为已经按照索引单词的词典序由低到高排好顺序，所以可以顺序读取文件内容，减少磁盘寻道时间，这是其高效的根本原因。
缺点：因为要生成新的倒排索引文件，所以对于老索引中的很多单词来说，尽管其倒排列表并未发生任何变化，但是也需要将其从老索引中读取出来并写入新索引中，这种对磁盘输入输出的消耗是没有太大必要且非常耗时的。
改进：在索引更新过程中，如果老索引的倒排列表没有变化，可以不需要读取这些信息，而只对那些倒排列表变化的单词进行处理。甚至希望能更进一步：即使老索引的倒排列表发生变化，是否可以只在其末尾进行追加操作，而不需要读取原先的倒排列表并重写到磁盘另一个位置?如果能够达到这个目标，明显可以大量减少磁盘读/写操作，提升系统执行效率。
原地更新策略在索引合并时，并不生成新的索引文件，而是直接在原先老的索引文件里进行追加操作，将增量索引里单词的倒排列表项追加到老索引相应位置的末尾，这样就可达到上述目标，即只更新增量索引里出现的单词相关信息，其他单词相关信息不做变动。
问题：对于倒排文件中的两个相邻单词，为了在查询时加快读取速度，其倒排列表一般是顺序序列存储的，这导致没有空余位置用来追加新信息。为了能够支持追加操作，原地更新策略在初始建立的索引中，会在每个单词的倒排列表末尾预留出一定的磁盘空间，这样，在进行索引合并时，可以将增量索引追加到预留空间中。
补充：如果预留空间不足以容纳新增倒排列表，那么此时需要在磁盘中找到一块完整的连续存储区，这个存储区足以容纳这个单词的倒排列表，之后将老索引中的倒排列表读出并写入新的磁盘位置，并将增量索引对应的倒排列表追加到其后，这样就完成了一次倒排列表的“迁移”工作。
缺点：原地更新策略的出发点很好，但是实验数据证明其索引更新效率比再合并策略低，主要是出于以下两个原因。
在这种方法中，对倒排列表进行“迁移”是比较常见的操作，为了能够进行快速迁移，需要找到足够大的磁盘连续存储区，所以这个策略需要对磁盘可用空间进行维护和管理，而这种维护和查找成本非常高，这成为该方法效率的一个瓶颈。
对于倒排文件中的相邻索引单词，其倒排列表顺序一般是按照相邻单词的词典序存储的，但是由于原地更新策略对单词的倒排列表做数据迁移，某些单词及其对应倒排列表会从老索引中移出，这样就破坏了这种单词连续性，导致在进行索引合并时不能进行顺序读取，必须维护一个单词到其倒排文件相应位置的映射表，而这样做，一方面降低了磁盘读取速度，另外一方面需要大量的内存来存储这种映射信息。
混合策略的出发点是能够结合不同索引更新策略的长处，将不同的索引更新策略混合，以形成更高效的方法。
混合策略一般会将单词根据其不同性质进行分类，不同类别的单词，对其索引采取不同的索引更新策略。常见的做法是：根据单词的倒排列表长度进行区分，因为有些单词经常在不同文档中出现，所以其对应的倒排列表较长，而有些单词很少见，则其倒排列表就较短。根据这一性质将单词划分为长倒排列表单词和短倒排列表单词。长倒排列表单词采取原地更新策略，而短倒排列表单词则采取再合并策略。
之所以这样做，是由于原地更新策略更适合长倒排列表单词，因为这种策略能够节省磁盘读/写次数，而长倒排列表单词的读/写开销明显要比短倒排列表单词大很多，所以如果采用原地更新策略，效果体现得比较显著。而大量短倒排列表单词读/写开销相对而言不算太大，所以利用再合并策略来处理，则其顺序读/写优势也能被充分利用。
为搜索引擎构建索引，其目的是能更快速地提取与用户查询相关的文档信息。
搜索引擎对于用户查询的处理过程。目前有两种常见的查询处理机制，一种被称做一次一文档方式，另外一种被称为一次一单词方式。还有跳跃指针这种查询优化过程。
搜索引擎接收到用户的查询后，首先将两个单词的倒排列表从磁盘读入内存。所谓的一次一文档，就是以倒排列表中包含的文档为单位，每次将其中某个文档与查询的最终相似性得分计算完毕，然后开始计算另外一个文档的最终得分，直到所有文档的得分都计算完毕为止。所有文档都计算完毕后，根据文档得分进行大小排序，输出得分最高的K个文档作为搜索结果输出，即完成了一次用户查询的响应。
因为搜索系统的输出结果往往是限定个数的，比如指定输出10个结果，所以在实际实现一次一文档方式时，不必保存所有文档的相关性得分，而只需要在内存中维护一个大小为K的优先级别队列，用来保存目前计算过程中得分最高的K个文档即可，这样可以节省内存和计算时间，一般会采用根堆数据结构来实现这个优先级别队列，在计算结束时，按照得分大小输出就可以实现搜索的目标。
如果用户输入的查询包含多个查询词，搜索引擎一般默认是采取与逻辑来判别文档是否满足要求，即要求相关网页必须包含所有的查询词，比如用户输入查询“搜索引擎技术”，只有同时包含两个词汇的网页才会被认为是相关的，只包含其中任意一个关键词的网页不会作为搜索结果输出。
对于这种应用场景，一次一文档的查询处理方式是比较适合的。对于多词查询，找到包含所有查询词的文档，等价于求查询词对应的倒排列表的交集。
求交基本逻辑：如果倒排列表直接存储包含查询词的文档ID，那么计算交集是非常直观和简单的，其基本操作即是在一个倒排列表里查询某个文档ID是否存在，通过归并排序即可获得O（mn)时间复杂度的算法。如果文档ID是以文档编号差值（D-Gap）形式存储的，另外这个差值是以压缩后的方式编码的，那么如何求倒排列表的交集就会复杂化。为了求两个查询词对应倒排列表的交集，首先需要将两个单词对应的倒排列表读入内存，然后对数据解压缩恢复到文档编号差值的形式，之后还需要将其恢复成文档ID的有序列表，在此基础上才能进行集合交集运算。
跳跃指针：基本思想是将一个倒排列表数据化整为零，切分为若干个固定大小的数据块，一个数据块作为一组，对于每个数据块，增加元信息来记录关于这个块的一些信息，这样即使是面对压缩后的倒排列表，在进行倒排列表合并的时候也能有两个好处：一个好处是无须解压缩所有倒排列表项，只解压缩部分数据即可；另外一个好处是无须比较任意两个文档ID，通过这两种方式有效节省了计算资源和存储资源。
假设我们需要在单词“Google”压缩后的倒排列表里查找文档编号为7的文档。首先，对倒排列表前两个数值进行数据解压缩，读取第1组的跳跃指针数据，发现其值为<5，Posl>，其中Posl指出了第2组的跳跃指针在倒排列表中的起始位置，于是可以解压缩Posl位置处连续两个数值，得到<13，Pos2>。跳跃指针的数值5和数值13，分别表示两组数据中最小编号文档的文档ID，我们要查找的7号文档落在两者之间，说明如果7号文档包含在单词“Google”的倒排列表中的话，一定会在第1组中，否则说明倒排列表中不包含这个文档。于是可以依次对第1组中的数据进行解压缩，并根据最小文档编号逆向恢复其原始的文档编号，当读到2，1>的时候，可以知道这个文档对应的原始文档ID为：52=7，与我们正在查找的文档编号相同，说明7号文档在单词“Google”的倒排列表中，于是可以结束这次查找。而求两个查询词的倒排列表交集就是反复在两个倒排列表中查找某个文档是否存在，将同时在两个倒排列表中出现的文档ID作为计算结果。
从上面的查找过程可以看出，相对不包含跳跃指针的索引来说，我们只需要对其中一个数据块进行解压缩和文档编号查找即可获得结果，不用将所有索引数据都进行解压缩和比较操作，很明显这将加快查找速度，并节省内存空间。
而在实际应用中，如何设定数据块或者数据组的大小对于效率有影响。数据块越小，则使用跳跃指针向后进行跳跃的可能性越大，但是缺点是增加了指针比较操作的次数；数据块越大，则可以有效减少指针比较次数，但是使用跳跃指针向后跳跃的可能性越小。所以需要根据数据情况对块大小进行合理设置才能取得最优结果。实践表明一个简单有效的启发规则是：假设倒排列表长度为L（即包含L个文档ID)，使用作为块大小，则效果较好。
即使是对互联网网页，也可以切割为不同的字段，搜索关键词出现在不同字段里代表的权重是不同的。如果搜索关键词出现在标题，很明显这个网页的相关性会高于只在正文中出现关键词的网页。所以区分不同字段对于搜索引擎的相关性评分也有很大帮助。
为了能够支持以上的需求，搜索引擎需要能够对多字段进行索引，而实现多字段索引有3种方式：多索引方式、倒排列表方式和扩展列表方式。
多索引方式针对每个不同的字段，分别建立一个索引，当用户指定某个字段作为搜索范围时，可以从相应的索引里提取结果。我们假设要处理的文档分为“标题”、“摘要”和“正文”3个字段。
当用户没有指定特定字段时，搜索引擎会对所有字段都进行查找并合并多个字段的相关性得分，对于多索引方式来说，就需要对多个索引进行读取，所以这种方式的效率会比较低。
为了能够支持对指定字段的搜索，也可以将字段信息存储在某个关键词对应的倒排列表内，在倒排列表中每个文档索引项信息的末尾追加字段信息，这样在读出用户查询关键词的倒排列表的同时，就可以根据字段信息，判断这个关键词是否在某个字段出现，以此来进行过滤，并保留指定字段内出现过搜索词的文档作为搜索结果返回。
我们要处理的文档包含了3个字段，所以可以用3个比特位（Bit)来分别表示关键词是否在某个字段出现过，每个比特位对应一个字段。如果关键词在某个字段出现过，则相应的比特位设定为1，否则设定为0。我们假设3个比特位从左到右依次分别对应“标题”、“摘要”和“正文”这种顺序，如果比特位的值为“101”，则代表某个关键词在“标题”和“正文”中出现过，但是没有在“摘要”中出现。
扩展列表是实际中应用得比较多的支持多字段索引的方法。这个方法为每个字段建立一个列表，这个列表记载了每个文档这个字段对应的出现位置信息。
假设用户指定在标题字段里搜索“搜索引擎”这个查询，通过倒排列表可以知道文档1、文档3和文档4包含这个查询词，接下来需要判断：这些文档是否在标题中出现过查询词?对于文档1来说，“搜索引擎”这个查询词的出现位置是第6和第10这两个位置，而通过对应的标题扩展列表可知，文档1的标题范围是位置1到位置4，这说明文档1的标题内不包含查询词，即文档1不满足要求。对于文档3来说，“搜索引擎”在文档中的出现位置是2、8和15，而对应的标题扩展列表中，标题出现范围为位置1到位置3，说明在位置2出现的这个查询词是在标题范围内的，即满足要求，可以作为搜索结果输出。文档4也类似，是满足搜索条件的文档，于是可以输出文档3和文档4作为搜索结果。
短语是很常见的语言现象，几个经常连在一起被使用的单词就构成了短语，比如“你懂的”。短语强调单词之间的顺序，有时尽管是同样的单词，顺序颠倒后会产生完全不同的含义，比如“懂你的”和“你懂的”含义相差甚远。
搜索引擎如何能够支持短语呢?如果单词的倒排列表只存储文档编号和单词频率信息，其保留的信息是不足以支持短语搜索的，因为单词之间的顺序关系没有保留。搜索引擎支持短语查询，本质问题是如何在索引中维护单词之间的顺序关系或者位置信息。较常见的支持短语查询的技术方法包括：位置信息索引、双词索引及短语索引这3类，为了能够更有效地利用存储和计算资源，也可以将三者结合使用。
对于词典中某个单词的倒排列表，往往存储3种信息：文档ID、单词频率和单词位置信息。一般情况下不存储单词位置信息，因为这种信息数量过大，一旦加入位置信息，单词的倒排列表长度会剧烈增长，这样一方面消耗存储空间，另一方面影响磁盘读取效率，对快速响应用户查询不利。但是如果索引记载单词位置信息，则能很方便地支持短语查询。
假设用户输入短语查询“爱情买卖”，在单词倒排列表中存储了文档ID、单词频率及位置信息，比如
<5，2,[3，7]>索引项的含义是：5号文档包含“爱情”这个单词，且这个单词在文档中出现2次，其对应的位置为3和7，其他倒排列表项的含义与此相同。
搜索引擎获得了用户查询后，从磁盘分别读入两个单词的倒排列表，通过倒排列表记载的信息可知，文档5和文档9同时包含两个查询词，为了判断在这两个文档中，用户查询是否以短语的形式存在，还要判断位置信息。“爱情”这个单词在5号文档的出现位置是3和7，而“买卖”在5号文档的出现位置是4，可以看出5号文档的位置3和位置4分别对应单词“爱情”和“买卖”，即两者是一个短语形式，而对于9号文档，做同样的分析后可知，这两个查询词并没有连续在文档中出现，所以搜索引擎会将5号文档作为搜索结果返回，这样就通过位置信息完成了对短语查询的支持。对于超过两个查询词的短语，也可用类似的方式得到结果。
尽管位置索引可以支持短语查询，但是对于有些查询，其付出的存储和计算代价很高，可以思考一下“我的团长我的团”这种短语查询的存储和计算代价。
双词索引是另外一种可以对短语查询提供支持的索引结构。短语至少包含两个单词，也可能包含多个单词，统计数据表明，二词短语在短语中所占比例最大，所以如果能够针对二词短语提供快速查询，也能解决短语查询的问题。
对于两个单词构成的短语来说，一般称第1个单词为“首词”，第2个单词为“下词”。在内存中包含两个词典，分别是“首词”词典和“下词”词典，“首词”词典有指针指向“下词”词典某个位置，“下词”词典存储了紧跟在“首词”词典后的常用短语的第2个单词，“下词”词典的指针指向包含这个短语的倒排列表。比如对于“我的”这个短语，其倒排列表包含文档5和文档7，对于“的父亲”这个短语，其倒排列表包含文档5，词典中其他词典项也是类似的含义。
假设用户输入短语查询“我的父亲”，搜索引擎首先将其拆分成两个短语“我的”和“的父亲”，然后分别查找词典信息，发现包含“我的”这个短语的是文档5和文档7，而包含“的父亲”这个短语的有文档5。查看其对应的出现位置，可以知道文档5是符合条件的搜索结果。这样就完成了对短语查询的支持。
双词索引同样使得索引急剧增大，原先的索引结构中，词典是一维的，而双词索引词典结构是二维的，这样倒排列表个数会发生爆炸性增长，所以一般实现时并非对所有单词都建立双词索引，而是只对计算代价高的短语建立双词索引，比如包含“我”、“的”等停用词的短语，这些短语如果用常规方法处理的话，存储和计算代价太高，采用双词索引可以极大地缓解这种状况，对于一般的短语，可以使用位置信息等常规手段来达到目的。
位置索引和双词索引可以有效支持短语查询，但其实还有一种更直观的方法来解决这个问题，那就是直接在索引中加入短语索引。之前介绍的常规索引结构中，词典都是以单词作为查询和存储单位的，如果将其扩展，在词典中直接加入多词短语并维护短语的倒排列表，这样也可以对短语进行支持。
当搜索引擎接收到用户查询后，首先在短语索引里查找，如果找到，则计算后返回给用户搜索结果，否则仍然利用常规索引进行查询处理。
不同的短语索引结构有其各自的特点，位置索引适合处理常规的短语查询，即计算代价较小的短语，双词索引适合处理计算代价较高的短语查询，而短语索引则适合处理热门短语查询或者文本中高频度出现的短语，此三者是以互补关系存在的，如果能够在构建系统时有机集成三者，就能使系统效率发挥出综合优势。
短语索引用来对热门短语和高频短语进行索引，双词索引对包含停用词等高代价短语进行索引。接收到用户查询后，系统首先在短语索引中查找，如果找到则返回结果，否则到双词索引中查找，如果找到则返回结果，否则从常规索引中对短语进行处理，这样可以充分发挥各自的优势。
当搜索引擎需要处理的文档集合数量非常庞大时，靠单机往往难以承担如此重任，此时需要考虑分布式解决方案，即每台机器维护整个索引的一部分，由多台机器协作来完成索引的建立和对查询的响应。至于多台机器如何分工协作，目前常用的分布式索引方案包括两种：按文档对索引划分和按单词对索引划分。
将整个文档集合切割成若干子集合，而每台机器负责对某个文档子集合建立索引，并响应查询请求。假设文档集合包含5个文档，将其切割成两个子集合，分别交由两台机器建立索引。
查询分发服务器接收到用户查询请求后，将查询广播给所有索引服务器。每个索引服务器负责部分文档子集合的索引维护和查询响应，当索引服务器接收到用户查询后，按照本章前述小节所述计算相关文档，并将得分最高的K个文档送返查询分发服务器。查询分发服务器综合各个索引服务器的搜索结果后，合并搜索结果，将得分最高的m个文档作为最终搜索结果返回给用户，这样就完成了对一次用户查询的响应。
按单词划分索引方式与上述按文档划分索引方式不同，不是对文档集合进行切割，而是对单词词典进行划分，每个索引服务器负责词典中部分单词的倒排列表的建立和维护。假设单词词典包含了6个单词，这种方式将每3个单词的倒排列表存储在一台索引服务器上，以此协作方式来完成整个索引系统。
按照单词对索引进行划分的分布式方案中，如何响应用户查询？假设用户输入的查询包含3个单词Term1、Term2和Term3，查询分发服务器接收到用户查询后，将查询转发给包含单词Term1倒排列表的索引服务器节点1，索引服务器节点1提取Term1的倒排列表，并累计计算搜索结果的中间得分，然后将查询和中间结果传递给包含单词Term2倒排列表的索引服务器节点，索引服务器节点2也是类似处理，并继续传递到索引服务器节点3。索引服务器节点3处理完成后，将最终结果返回给查询分发服务器，查询分发服务器计算得分最高的K个文档作为搜索结果输出。很明显，这是典型的一次一单词的查询处理方式。
可扩展性：搜索引擎处理的文档集合往往是在不断变动的，如果是按文档来对索引划分，则很容易支持新增的文档，只要增加索引服务器，将新增的文档由新增索引服务器来负责处理即可，对系统其他部分影响很小，在实现上也非常方便。但是如果是按单词进行索引划分，则对几乎所有的索引服务器都有直接影响，因为新增文档可能包含所有词典单词，即需要对每个单词的倒排列表进行更新，实现起来相对复杂。
负载均衡：按单词进行索引划分在索引服务器的负载均衡方面做得也不是很好。有些单词比较常见，几乎出现在所有文档中，比如一些常用词，这些单词的倒排列表会非常庞大，可能会达到几十兆字节。如果是按文档进行索引划分，这种单词的倒排列表会比较均匀地分布在不同的索引服务器上，而按单词进行索引划分，某个常见单词的倒排列表全部内容都由一台索引服务器维护，如果这个单词同时又是一个流行词汇，会有很多用户搜索，维护这个单词倒排索引的索引服务器会成为负载过大的性能瓶颈。
容错性：假设在分布式索引系统里，某台索引服务器发生故障，对于按文档进行索引划分的方案来说，因为这只影响到部分文档子集合，即使某台索引服务器不能响应查询，其他索引服务器仍然能够响应，对于用户来说，并不会直接感受到这种故障的影响。但是对于按单词进行索引划分的情况，若索引服务器发生故障，则某些单词的倒排列表无法访问，用户查询这些单词的时候，会发现没有搜索结果，这直接影响用户体验。
对查询处理方式的支持：按单词进行索引划分只能支持一次一单词这种查询处理方式，而按文档进行索引划分则不受此限制，可以同时支持两种不同的查询处理方式。对于某些类型的搜索来说，需要一次一文档这种查询处理方式支持，否则在机制上就无法实现。按文档进行索引划分可以根据具体情况选择不同的查询处理方式，而按单词进行索引划分则没有这种灵活性。
搜索引擎高级命令
搜索引擎核心技术详解10—网页去重
搜索引擎核心技术详解8—网页反作弊
搜索引擎核心技术详解6—链接分析
搜索引擎核心技术详解5—检索模型与搜索排序
搜索引擎核心技术详解2—网络爬虫
搜索引擎核心技术详解1—搜索引擎及其技术架构
搜索引擎工作原理介绍
知识像烛光，能照亮一个人，也能照亮无数人
搜索引擎发展简史
搜索引擎工作原理介绍
搜索引擎核心技术详解5—检索模型与搜索排序
相关标签： 搜索引擎核心技术详解3—搜索引擎索引、 SEO教程网、
本文地址：https://www.badfl.com/article/b17c60ca5b3d01786173.html
<a href="https://www.badfl.com/" target="_blank">自动秒收录</a>