『搜索引擎』索引数据结构和算法

最近一直在研究sphinx的工作机制，在［搜索引擎］Sphinx的介绍和原理探索简单地介绍了其工作原理之后，还有很多问题没有弄懂，比如底层的数据结构和算法，于是更进一步地从数据结构层面了解其工作原理。在网上搜了很多资料，发现没有很多介绍这方面的文章，后来找到了一本书，《这就是搜索引擎》，拜读了本书的第三章，介绍了主流搜索引擎用的数据结构及其工作原理，sphinx使用的数据结构也是一样的，用的也是倒排索引。注：本文不会对sphinx和搜索引擎严格区分开，同一作搜索引擎看待。先附图一枚索引基础先介绍与搜索引擎有关的一些基本概念，了解这些概念对后续了解工作机制非常重要。单词-文档矩阵单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型。如下图所示，每列代表一个文档，每行代表一个单词，打对钩的位置代表包含关系。从纵向看，可以得知每列代表文档包含了哪些单词；从横向看，每行代表了哪些文档包含了某个单词。搜索引擎的索引其实就是实现单词-文档矩阵的具体数据结构。可以有不同的方式来实现上述概念模型，比如倒排索引、签名文件、后缀树等方式。但实验数据表明，倒排索引是单词到文档映射关系的最佳实现方式。倒排索引基本概念文档（Document）：以文本形式存在的存储对象。如：网页、Word、PDF、XML等不同格式的文件。文档集合（DocumentCollection）：若干文档构成的集合。如：大量的网页。文档编号（DocumentID）：搜索引擎内部，唯一标识文档的唯一编号。单词编号（WordID）：搜索引擎内部，唯一标识单词的唯一编号。倒排索引（InvertedIndex）：实现单词–文档矩阵的一种具体存储形式。倒排索引主要有单词词典和倒排文件组成。单词词典（Lexicon）：文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息及指向倒排列表的指针。倒排列表（PostingList）：出现了某个单词的所有文档的文档列表及单词在该文档中出现的位置信息。列表中每条记录称为一个倒排项（Posting）。倒排文件（InvertedFile）：保存所有单词的倒排列表的文件，倒排文件是存储倒排索引的物理文件。概念之间的关系如图倒排索引简单实例下面举一个实例，这样对倒排索引有一个更直观的感受。假设文档集合包含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以及单词在文档中哪些位置出现过等信息。包含某单词的一些列倒排索引项形成了某个单词对应的倒排列表。下图是倒排列表示意图：建立索引前面介绍了索引结构，那么，有了数据之后索引是怎么建立的呢？主要有三种建立索引的方法。两遍文档遍历法此方法在内存里完成索引的创建过程。要求内存要足够大。第一遍收集一些全局的统计信息。包括文档集合包含的文档个数N，文档集合内所包含的不同单词个数M，每个单词在多少个文档中出现过的信息DF。将所有单词对应的DF值全部相加，就可以知道建立最终索引所需的内存大小是多少。获取信息后，根据统计信息分配内存等资源，同事建立好单词相对应倒排列表在内存中的位置信息。第二遍逐个单词建立倒排列表信息。获得包含某个单词的每个文档的文档ID，以及这个单词在文档中的出现次数TF，然后不断填充第一遍扫描时所分配的内存。当第二遍扫描结束的时候，分配的内存正好被填充满，每个单词用指针所指向的内存区域“片段”，其起始位置和终止位置之间的数据就是这个单词对应的倒排列表。排序法在建立索引过程中，始终在内存中分配固定大小的空间，用来存放词典信息和索引的中间结果，当分配的空间被消耗光的时候，把中间结果写入磁盘，清空内存里中间结果所占空间，以用做下一轮存放索引中间结果的存储区。参考下图：上图是排序法建立索引中间结果的示意图。建立过程：读入文档后，对文档进行编号，赋予唯一的文档ID，并对文档内容解析；将单词映射为单词ID；建立（单词ID、文档ID、单词频率）三元组；将三元组追加进中间结果存储区末尾；然后依次序处理下一个文档；当分配的内存定额被占满时，则对中间结果进行排序（根据单词ID-文档ID的排序原则）；将排好序的三元组写入磁盘文件中。注：在排序法建立索引的过程中，词典是一直存储在内存中的，由于分配内存是固定大小，渐渐地词典占用内存越来越大，那么，越往后，可用来存储三元组的空间越来越少。建立好索引后，需要合并。合并时，系统为每个中间结果文件在内存中开辟一个数据缓冲区，用来存放文件的部分数据。将不同缓冲区中包含的同一个单词ID的三元组进行合并，如果某个单词ID的所有三元组全部合并完成，说明这个单词的倒排列表已经构建完成，则将其写入最终索引中，同事将各个缓冲区中对应这个单词ID的三元组内容清空。缓冲区继续从中间结果文件读取后续的三元组进行下一轮合并。当所有中间结果文件都依次被读入缓冲区，并合并完成后，形成最终的索引文件。归并法归并法与排序法类似，不同的是，每次将内存中数据写入磁盘时，包括词典在内的所有中间结果都被写入磁盘，这样内存所有内容都可以被清空，后续建立索引可以使用全部的定额内存。归并法的示意图如下所示：与排序法的差异：1.排序法在内存中存放的是词典信息和三元组数据，词典和三元组数据并没有直接的联系，词典只是为了将单词映射为单词ID。归并法则是在内存中建立一个完整的内存索引结构，是最终文章索引的一部分。2.在将中间结果写入磁盘临时文件时，归并法将这个内存的倒排索引写入临时文件，随后彻底清空所占内存。而排序法只是将三元组数据排序后写入磁盘临时文件，词典作为一个映射表一直存储在内存中。3.合并时，排序法是对同一单词的三元组依次进行合并；归并法的临时文件则是每个单词对应的部分倒排列表，所以在合并时针对每个单词的倒排列表进行合并，形成这个单词的最终倒排列表。动态索引在真实环境中，搜索引擎需要处理的文档集合内有些文档可能被删除或者内容被修改。如果要在内容被删除或修改之后马上在搜索结果中体现出来，动态索引可以实现这种实时性需求。动态索引有三个关键的索引结构：倒排索引、临时索引和已删除文档列表。临时索引：在内存中实时建立的倒排索引，当有新文档进入系统时，实时解析文档并将其追加进这个临时索引结构中。已删除列表：存储已被删除的文档的相应文档ID，形成一个文档ID列表。当文档被修改时，可以认为先删除旧文档，然后向系统增加一篇新文档，通过这种间接方式实现对内容更改的支持。当系统发现有新文档进入时，立即将其加入临时索引中。有新文档被删除时，将其加入删除文档队列。文档被更改时，则将原先文档放入删除队列，解析更改后的文档内容，并将其加入临时索引。这样就可以满足实时性的要求。在处理用户的查询请求时，搜索引擎同时从倒排索引和临时索引中读取用户查询单词的倒排列表，找到包含用户查询的文档集合，并对两个结果进行合并，之后利用删除文档列表进行过滤，将搜索结果中那些已经被删除的文档从结果中过滤，形成最终的搜索结果，并返回给用户。索引更新策略动态索引可以满足实时搜索的需求，但是随着加入文档越来越多，临时索引消耗的内存也会随之增加。因此要考虑将临时索引的内容更新到磁盘索引中，以释放内存空间来容纳后续的文档，此时就需要考虑合理有效的索引更新策略。完全重建策略对所有文档重新建立索引。新索引建立完成后，老的索引被遗弃释放，之后对用户查询的响应完全由新的索引负责。在重建过程中，内存中仍然需要维护老的索引对用户的查询做出响应。如图所示：再合并策略有新文档进入搜索系统时，搜索系统在内存维护临时倒排索引来记录其信息，当新增文档达到一定数量，或者指定大小的内存被消耗完，则把临时索引和老文档的倒排索引进行合并，以生成新的索引。过程如下图所示：更新步骤：1.当新增文档进入系统，解析文档，之后更新内存中维护的临时索引，文档中出现的每个单词，在其倒排列表末尾追加倒排列表项，这个临时索引可称为增量索引2.一旦增量索引将指定的内存消耗光，增量索引和老的倒排索引内容需要进行合并。高效的原因：在对老的倒排索引进行遍历时，因为已经按照索引单词的词典序由低到高排好顺序，所以可以顺序读取文件内容，减少磁盘寻道时间。缺点：因为要生成新的倒排索引文件，所以老索引中的倒排列表没发生变化也需要读出来并写入新索引中。增加了I/O的消耗。原地更新策略原地更新策略的出发点是为了解决再合并策略的缺点。在索引合并时，并不生成新的索引文件，而是直接在原先老的索引文件里进行追加操作，将增量索引里单词的倒排列表项追加到老索引相应位置的末尾，这样就可达到上述目标，即只更新增量索引里出现的单词相关信息，其他单词相关信息不变动。为了能够支持追加操作，原地更新策略在初始建立的索引中，会在每个单词的倒排列表末尾预留出一定的磁盘空间，这样，在进行索引合并时，可以将增量索引追加到预留空间中。如下图：实验数据证明，原地更新策略的索引更新效率比再合并策略低，原因：1.由于需要做快速迁移，此策略需要对磁盘可用空间进行维护和管理，成本非常高。2.做数据迁移时，某些单词及其对应倒排列表会从老索引中移出，破坏了单词连续性，因此需要维护一个单词到其倒排文件相应位置的映射表。降低了磁盘读取速度及消耗大量内存（存储映射信息）。混合策略将单词根据其不同性质进行分类，不同类别的单词，对其索引采取不同的索引更新策略。常见做法：根据单词的倒排列表长度进行区分，因为有些单词经常在不同文档中出现，所以其对应的倒排列表较长，而有些单词很少见，则其倒排列表就较短。根据这一性质将单词划分为长倒排列表单词和短倒排列表单词。长倒排列表单词采取原地更新策略，而短倒排列表单词则采取再合并策略。因为长倒排列表单词的读/写开销明显比短倒排列表单词大很多，所以采用原地更新策略能节省磁盘读/写次数。而大量短倒排列表单词读/写开销相对而言不算太大，所以利用再合并策略来处理，则其顺序读/写优势也能被充分利用。查询处理建立好索引之后，如何用倒排索引来响应用户的查询呢？主要有下面三种查询处理机制。一次一文档以倒排列表中包含的文档为单位，每次将其中某个文档与查询的最终相似性得分计算完毕，然后开始计算另外一个文档的最终得分，直到所有文档的得分计算完毕为止。然后根据文档得分进行大小排序，输出得分最高的K个文档作为搜索结果输出，即完成了一次用户查询的响应。实际实现中，只需在内存中维护一个大小为K的优先级队列。如下图所