索引构建

索引基础

单词 - 文档矩阵

单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型，如下图所示，每列代表一个文档，每行代表一个单词，打对钩的位置代表包含关系。

从纵向看，可以得知每列代表文档包含了哪些单词；从横向看，每行代表了哪些文档包含了某个单词。搜索引擎的索引其实就是实现单词-文档矩阵的具体数据结 构。可以有不同的方式来实现上述概念模型，比如倒排索引、签名文件、后缀树等方式。但实验数据表明，倒排索引是单词到文档映射关系的最佳实现方式。

倒排索引

文档(Document )：以文本形式存在的存储对象。如：网页、Word、PDF、XML 等不同格式的文件。文档集合(Document Collection )：若干文档构成的集合。如：大量的网页。文档编号(Document ID )：搜索引擎内部，唯一标识文档的唯一编号。单词编号(Word ID )：搜索引擎内部，唯一标识单词的唯一编号。倒排索引(Inverted Index )：实现单词 – 文档矩阵的一种具体存储形式。倒排索引主要有单词词典和倒排文件组成。单词词典(Lexicon )：文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息及指向倒排列表的指针。倒排列表(PostingList )：出现了某个单词的所有文档的文档列表及单词在该文档中出现的位置信息。列表中每条记录称为一个倒排项(Posting )。倒排文件(Inverted File )：保存所有单词的倒排列表的文件，倒排文件是存储倒排索引的物理文件。

倒排索引实例

下面举一个实例，这样对倒排索引有一个更直观的感受。

假设文档集合包含 5 个文档，每个文档内容如下图所示：

建立的倒排索引如下图：

单词 ID：记录每个单词的单词编号；

单词：对应的单词；

文档频率：代表再文档集合中有多少个文档包含某个单词

倒排列表：包含单词 ID 及其他必要信息

TF：单词在某个文档中出现的次数

POS：单词在文档中出现的位置

以单词 “ 加盟 ” 为例，其单词编号为 8，文档频率为 3，代表整个文档集合中有三个文档包含这个单词，对应的倒排列表为 {(2;1;<4>),(3;1;<7>),(5;1;<5>)}，含义是在文档 2，3，5 出现过这个单词，在每个文档的出现过 1 次，单词 “ 加盟 ” 在第一个文档的 POS 是 4，即文档的第四个单词是 “ 加盟 ”，其他的类似。

这个倒排索引已经是一个非常完备的索引系统，实际搜索系统的索引结构基本如此。

单词词典

单词词典用来维护文档集合中出现过的所有单词的相关信息，同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在查询时到单词词典里查询，就能获得相应的倒排列表，并以此作为后序排序的基础。常用数据结构：哈希加链表和树形词典结构。

哈希加链表

下图是哈希加链表词典结构的示意图。主体是哈希表，每个哈希表项保存一个指针，指针指向冲突连表，相同哈希值的单词形成链表结构。

构建过程：对文档进行分词；对于做好的分词，利用哈希函数获取哈希值；根据哈希值对应的哈希表项找到对应的冲突链表；如果冲突链表已经存在该单词 　　不处理否则 　　加入冲突连表

树形结构

使用 B 树或者 B+ 树的结构。与哈希表不同的是，需要字典项能按照大小排序，即使用数字或字符序。树形结构中，使用层级查找，中间节点保存一定顺序范围的词典项目存储在哪个子树中，最底层的叶子节点存储单词的地址信息。

倒排列表

倒排列表用来记录哪些文档包含了某个单词。倒排列表由倒排索引项组成，每个倒排索引项由文档 ID，单词出现次数 TD 以及单词在文档中哪些位置出现过等信息。包含某单词的一些列倒排索引项形成了某个单词对应的倒排列表。下图是倒排列表示意图:

索引建立

2-Pass In-Memory Inversion: 两遍文档遍历法

此方法在内存里完成索引的创建过程。要求内存要足够大。第一遍收集一些全局的统计信息。包括文档集合包含的文档个数 N，文档集合内所包含的不同单词个数 M，每个单词在多少个文档中出现过的信息 DF。将所有单词对应的 DF 值全部相加，就可以知道建立最终索引所需的内存大小是多少。获取信息后，根据统计信息分配内存等资源，同事建立好单词相对应倒排列表在内存中的位置信息。

第二遍逐个单词建立倒排列表信息。获得包含某个单词的每个文档的文档 ID，以及这个单词在文档中的出现次数 TF，然后不断填充第一遍扫描时所分配的内存。当第二遍扫描结束的时候，分配的内存正好被填充满，每个单词用指针所指向的内存区域 “ 片段 ”，其起始位置和终止位置之间的数据就是这个单词对应的倒排列表。

Sort-Based Inversion: 排序法

在建立索引过程中，始终在内存中分配固定大小的空间，用来存放词典信息和索引的中间结果，当分配的空间被消耗光的时候，把中间结果写入磁盘，清空内存里中间结果所占空间，以用做下一轮存放索引中间结果的存储区。参考下图:

上图是排序法建立索引中间结果的示意图。建立过程：读入文档后，对文档进行编号，赋予唯一的文档 ID，并对文档内容解析；将单词映射为单词 ID；建立(单词 ID、文档 ID、单词频率)三元组；将三元组追加进中间结果存储区末尾；然后依次序处理下一个文档；当分配的内存定额被占满时，则对中间结果进行排序(根据单词 ID-> 文档 ID 的排序原则)；将排好序的三元组写入磁盘文件中。注：在排序法建立索引的过程中，词典是一直存储在内存中的，由于分配内存是固定大小，渐渐地词典占用内存越来越大，那么，越往后，可用来存储三元组的空间越来越少。建立好索引后，需要合并。合并时，系统为每个中间结果文件在内存中开辟一个数据缓冲区，用来存放文件的部分数据。将不同缓冲区中包含的同一 个单词 ID 的三元组进行合并，如果某个单词 ID 的所有三元组全部合并完成，说明这个单词的倒排列表已经构建完成，则将其写入最终索引中，同事将各个缓冲区 中对应这个单词 ID 的三元组内容清空。缓冲区继续从中间结果文件读取后续的三元组进行下一轮合并。当所有中间结果文件都依次被读入缓冲区，并合并完成后，形成最终的索引文件。

Merge-Based Inversion: 归并法

归并法与排序法类似，不同的是，每次将内存中数据写入磁盘时，包括词典在内的所有中间结果都被写入磁盘，这样内存所有内容都可以被清空，后续建立索引可以使用全部的定额内存。归并法的示意图如下所示:

与排序法的差异: 1、排序法在内存中存放的是词典信息和三元组数据，词典和三元组数据并没有直接的联系，词典只是为了将单词映射为单词 ID。归并法则是在内存中建立一个完整的内存索引结构，是最终文章索引的一部分。2、在将中间结果写入磁盘临时文件时，归并法将这个内存的倒排索引写入临时文件，随后彻底清空所占内存。而排序法只是将三元组数据排序后写入磁盘临时文件，词典作为一个映射表一直存储在内存中。3、合并时，排序法是对同一单词的三元组依次进行合并；归并法的临时文件则是每个单词对应的部分倒排列表，所以在合并时针对每个单词的倒排列表进行合并，形成这个单词的最终倒排列表。

分布式索引(Parallel Indexing )

当搜索引擎需要处理的文档集合太多的时候，就需要考虑分布式解决方案。每台机器维护整个索引的一部分，有多台机器协作来完成索引的建立和对查询的响应。

按文档划分(Document Paritioning )

将整个文档集合切割成若干个子集合，而每台机器负责对某个文档子集合建立索引，并响应查询请求。按文档划分示意图如下：

工作原理：查询分发服务器接收到用户查询请求后，将查询广播给所有索引服务器。每个索引服务器负责部分文档子集合的索引维护和查询响应。当索引服务器接收到用户查询后，计算相关文档，并将得分最高的 K 个文档送返查询分发服务器。查询分发服务器综合各个索引服务器的搜索结果后，合并搜索结果，将得分最高的 m 个文档作为最终搜索结果返回给用户。

按单词划分(Term Paritioning )

每个索引服务器负责词典中部分单词的倒排列表的建立和维护。按单词划分示意图如下：

工作原理：一次一个单词。假设查询包含 A、B、C 三个单词，查询服务器接收到查询后，将查询转发到包含单词 A 倒排列表的索引服务器节点 1，索引服务器节点 1 提取 A 的倒排列表，并累计计算搜索结果的中间的分，然后将查询和中间结果传递给包含单词 B 倒排列表的索引服务器节点，索引服务器节点 2 也是类似处理，并继续到索引服务器节点 3。然后将最终结果返回给查询分发服务器，查询分发服务器计算得分最高的 K 个文档作为搜索结果输出。

两种方案比较

按文档比较常用，按单词划分只在特殊应用场合才使用。按单词划分的不足: 可扩展性 搜索引擎处理的文档是经常变动的。如果按文档来对索引划分，只需要增加索引服务器，操作起来很方便。但如果是按单词进行索引划分，则对几乎所有的索引服务器都有直接影响，因为新增文档可能包含所有词典单词，即需要对每个单词的倒排列表进行更新，实现起来相对复杂。

负载均衡 常用单词的倒排列表非常庞大，可能会达到几十 M 大小。如果按文档划分，这种单词的倒排列表会比较均匀地分布在不同的索引服务器上，而按单词进行索引划分，某个常见单词的倒排列表全部内容都由一台索引服务器维护。如果该单词同时是一个流行词汇，那么该服务器会成为负载过大的性能瓶颈。

容错性 假设某台服务器出现故障。如果按文档进行划分，那么只影响部分文档子集合，其他索引服务器仍然能响应。但如果按单词进行划分，若索引服务器发生故障，则某些单词的倒排列表无法访问，用户查询这些单词的时候，会发现没有搜索结果，直接影响用户体验。

对查询处理方式的支持 按单词进行索引一次只能查询一个单词，而按文档划分的不受此限制。

查询处理

建立好索引之后，如何用倒排索引来响应用户的查询呢？主要有下面三种查询处理机制。

Doc at a Time | 一次一文档

以倒排列表中包含的文档为单位，每次将其中某个文档与查询的最终相似性得分计算完毕，然后开始计算另外一个文档的最终得分，直到所有文档的得分计算完毕为 止。然后根据文档得分进行大小排序，输出得分最高的 K 个文档作为搜索结果输出，即完成了一次用户查询的响应。实际实现中，只需在内存中维护一个大小为 K 的 优先级队列。如下图所示是一次一文档的计算机制示意图:

虚线箭头标出查询处理计算的前进方向。查询时，对于文档 1 而言，因为两个单词的倒排列表中都包含这个文档，所以可以根据各自的 TF 和 IDF 等参数计算文档 和查询单词的相似性，之后将两个分数相加得到文档 1 和用户查询的相似性得分 Score1。其他的也是类似计算。最后根据文档得分进行大小排序，输出得分最 高的 K 隔文档作为搜索结果输出。

Term at a Time | 一次一单词

与一次一文档不同，一次一单词采取 “ 先横向再纵向 ” 的方式，首先将某个单词对应的倒排列表中的每个文档 ID 都计算一个部分相似性得分，也就是说，在单词 - 文档矩阵中首先进行横向移动，在计算完某个单词倒排列表中包含的所有文档后，接着计算下一个单词倒排列表中包含的文档 ID，即进行纵向计算，如果发现某个 文档 ID 已经有了得分，则在原先得分基础上累加。当所有单词都处理完毕后，每个文档最终的相似性得分计算结束，之后按照大小排序，输出得分最高的 K 个文档 作为搜索结果。下图是一次一单词的运算机制。

虚线箭头指示出了计算的前进方向，为了保存数据，在内存中使用哈希表来保存中间结果及最终计算结果。在查询时，对于文档 1，根据 TD 和 IDF 等参数计算这 个文档对 ” 搜索引擎 “ 的相似性得分，之后根据文档 ID 在哈希表中查找，并把相似性得分保存在哈希表中。依次对其他文档计算后，开始下一个单词(此处是 ” 技 术 “)的相似性得分的计算。计算时，对于文档 1，计算了相似性得分后，查找哈希表，发现文档 1 以及存在得分，则将哈希表对应的得分和刚刚计算得到的得分相 加作为最终得分，并更新哈希表 1 中文档 1 对应的得分，这样就得到文档 1 和用户查询最终的相似性得分，类似的计算其他文档，最后将结果排序后输出得分最高的 K 个文档作为搜索结果。

Skip Pointers: 跳跃指针

基本思想：将一个倒排列表数据化整为零，切分为若干个固定大小的数据块，一个数据块作为一组，对于每个数据块，增加元信息来记录关于这个块的一些信息，这样即使是面对压缩后的倒排列表，在进行倒排列表合并的时候也能有两个好处: 1、无须解压所有倒排列表项，只解压部分数据即可 2、无须比较任意两个文档 ID。下图是将 “Google” 这个查询词对应的倒排列表加入跳跃指针后的数据结构。

假设对于 “Google” 这个单词的倒排列表来说，数据块的大小为 3。然后在每块数据前加入管理信息，比如第一块的管理信息 是 «5,Pos1»，5 表示块中第一个文档 ID 编号，Pos1 是跳跃指针，指向第 2 块的起始位置。假设要在单词 “Google" 压缩后的倒排列表里查找文档 ID 为 7 的文档。首先，对倒排列表前两个数值进行数据解压缩，读取第一组的跳跃指针数据，发现其值 为 <5,Pos1>，其中 Pos1 指出了第 2 组的跳跃指针在倒排列表中的起始位置，于是可以解压缩 Pos1 位置处连续两个数值，得 到 <13,Pos2>。5 和 13 是两组数据中最小的文档 ID(即每组数据的第一个文档 ID)，我们要找的是 7，那么如果 7 号文档包含在单 词 ”Google“ 的倒排列表中的话，就一定会出现在第一组，否则说明倒排列表中不包含这个文档。解压第 1 组数据后，根据最小文档编号逆向恢复其原始的文 档编号，此处 <2,1> 的原始文档 ID 是：5+2=7，与我们要找的文档 ID 相同，说明 7 号文档在单词 ”Google“ 的倒排列表中，于是可 以结束这次查找。从上面的查找过程可知，在查找数据时，只需要对其中一个数据块进行解压缩和文档编号查找即可获得结果，而不必解压所有数据，很明显加快查找速度，并节省内存空间。缺点：增加指针比较操作的次数。实践表明：假设倒排列表的长度为 L(即包含 L 个文档 ID)，使用根号 L 作为块大小，则效果较好。

多字段索引

即对文档的多个字段进行索引。实现多字段索引的方式：多索引方式、倒排列表方式和扩展列表方式。

多索引方式

针对每个不同的字段，分别建立一个索引，当用户指定某个字段作为搜索范围时，可以从相应的索引里提取结果。当用户没有指定特定字段时，搜索引擎会对所有字段都进行查找并合并多个字段的相关性得分，这样效率较低。多索引方式示意图如下:

倒排列表方式

将字段信息存储在某个关键词对应的倒排列表内，在倒排列表中每个文档索引项信息的末尾追加字段信息，这样在读出用户查询关键词的倒排列表的同时，就可以根据字段信息，判断关键词是否在某个字段出现，以此来进行过滤。倒排列表方式示意图如下:

扩展列表方式

这是用得比较多的支持多字段索引的方法。为每个字段建立一个列表，该列表记录了每个文档这个字段对应的出现位置信息。下图是扩展列表的示意图：

为方便起见，只针对 ” 标题 “ 字段所建立扩展列表。比如第一项 <1,(1,4)>，代表对于文档 1 而言，其标题的位置为从第一个单词到第 4 个单词这个范围，其他项含义类似。对于查询而言，假设用户在标题字段搜索 ” 搜索引擎 “，通过倒排列表可以知道文档 1、3、4 包含这个查询词，接下来需要判断这些文档是否在标题字段中 出现过查询词？对于文档 1，” 搜索引擎 “ 这个查询词的出现位置是 6 和 10。而通过对应的标题扩展列表可知，文档 1 的标题范围是 1 到 4，说明文档 1 的标题内 不包含查询词，即文档 1 不满足要求。对于文档 3，” 搜索引擎出现的位置是 2、8、15，对应的标题扩展列表中，标题出现范围为 1 到 3，说明在位置 2 出现的 这个查询词是在标题范围内的，即满足要求，可以作为搜索结果输出。文档 4 也是类似的处理。

短语查询

短语查询的本质是如何在索引中维护单词之间的顺序关系或者位置信息。较常见的支持短语查询技术包括：位置信息索引、双词索引和短语索引。也可将三者结合使用。

位置信息索引(Position Index )

在索引中记录单词位置信息，可以很方便地支持短语查询。但是其付出的存储和计算代价很高。示意图如下：

<5,2,[3,7]> 的含义是，5 文档包含 “ 爱情 “ 这个单词，且这个单词在文档中出现 2 次，其对应的位置为 3 和 7，其他的含义与此相同。

查询时，通过倒排列表可知，文档 5 和文档 9 同时包含两个查询词，为了判断在这两个文档中，用户查询是否以短语的形式存在，还要判断位置信息。” 爱情 “ 这个单词在 5 号文档的出现位置是 3 和 7，而 ” 买卖 “ 在 5 号文档的出现位置是 4，可以知道 5 号文档的位置 3 和位置 4 分别对应单词 ” 爱情 “ 和 ” 买卖 “，即两者是一个短语形式，而根据同样的分析可知 9 号文档不是短语，所以 5 号文档会被作为搜索结果返回。

双词索引(Nextword Index )

统计数据表明，二词短语在短语中所占比例最大，因此针对二词短语提供快速查询，能解决短语查询的问题。但是这样做的话倒排列表个数会发生爆炸性增长。双词索引的数据结构如下图：

由图可知，内存中包含两个词典，分别是 ” 首词 “ 和 ” 下词 “ 词典，” 首词 “ 词典有指向 ” 下词 “ 词典某个位置的指针，” 下词 “ 词典存储了紧跟在 ” 首词 “ 词典的常用短语的第 2 个单词，” 下词 “ 词典的指针指向包含这个短语的倒排列表。比如 ” 我的 “ 这个短语，其倒排列表包含文档 5 和 7，” 的父亲 “ 这个短语，其倒排列表包含文档 5，其余词典也是类似的含义。

对于查询，用户输入 ” 我的父亲 “ 进行查询，搜索引擎将其进行分词得到 ” 我的 “ 和 ” 的父亲 “ 两个短语，然后分别查找词典信息，发现包含 ” 我的 “ 这个短语的是文档 5 和文档 7，而包含 ” 的父亲 “ 这个短语的有文档 5。查看其对应的出现位置，可以知道文档 5 是符合条件的搜索结果，这样就完成了对短语查询的支持。

双词索引会使得索引急剧增大，一般实现并非对所有单词都建立双词索引，而是只对计算代价高的短语建立双词索引。

短语索引(Phrase Index )

直接在词典中加入多次短语并维护短语的倒排列表。缺点就是不可能事先将所有短语都建好索引。通用做法就是挖掘出热门短语。下图是加入短语索引后的整体索引结构：

对于查询，当搜索引擎接收到用户查询后，现在短语索引里查找，如果找到，则计算后返回给用户搜索结果，否则仍然利用常规索引进行查询处理。

混合方法

将三者结合起来，接收到用户查询后，系统首先在短语索引中查找，如果找到则返回结果，否则在双词索引中查找，如果找到则返回结果，否则从常规索引中对短语进行处理，充分发挥各自的优势。3 种方式的混合索引结构如下图所示：

短语查询用来对热门短语和高频短语进行索引，双词索引对包含停用词等高代价短语进行索引。

对于查询，系统首先在短语索引中查找，如果找到则返回结果，否则在双词索引中查找，如果找到则返回结果，否则从常规索引中对短语进行处理，这样就充分发挥各自的优势。