倒排索引(一)

毕业以后在网页搜索组，所以抽空就看看了《这就是搜索引擎--核心技术详解》，书比较白话文，对于我这样的入门小白再合适不过了，还有一本《信息检索导论》比较系统和专业化，感兴趣的可以买来看看。

海量的网页数据，如何快速的找到包含用户查询的所有网页至关重要，如同我们拿到一本很厚的书时，如果没有目录，我们可能要花费很长的时间找自己需要的内容，但是有了目录，我们就能快速定位，这里的目录就相当于索引的功能。常见的搜索引擎索引是倒排索引，倒排索引是单词到文档映射关系的最佳实现方式，应用最为广泛。

倒排索引

倒排索引是单词-文档举证的一种存储方式。通过倒排索引可以快速根据单词找到包含这个单词的所有文档。

如上图所示，倒排索引主要由单词词典和倒排文件组成，单词词典存放在内存中，是组成所有文档的单词的集合，单词词典内的每条索引项记载了单词本身的一些信息和指向倒排列表的指针，通过这个指针就可以找到对应的倒排列表，而倒排列表记载了出现过某个单词的所有文档的文档列表和单词在文档中出现的位置信息，每条记录称为倒排向项。而倒排文件是倒排列表在磁盘上的物理存储。

以下是三种倒排索引

记录单词频率,文档频率和单词在文档中出现的位置将作为搜索结果排序的一个重要因子,可以利用倒排索引的其他信息计算文档得分，优化排序。

单词词典

如何快速的在单词词典中定位到某个单词，通过指针获得倒排索引项对于搜索的相应速度非常重要。随着网络新词的出现，单词词典需要自身维护，如何高效的构建和查找，对于单词词典非常中嗯要。常用的数据结构有哈希加链表和树形词典结构。

主体部分是哈希表，哈希表的每一项都会保存一个指针，指针指向冲突链，冲突链中保存相同哈希值的单词，不同的单词可能存在相同的哈希值，所以会形成链表结构。

建立哈希加链表结构

在建立索引的过程中，单词词典会被建立起来，在解析文档的过程中，对于文档中出现的某个单词T，首先利用哈希函数获得的哈希值，找到对应的哈希项，找到对应的冲突链表，遍历冲突链表，如果存在这个单词则说明之前出现过，则继续下一个单词。如果在冲突链表中没有这个单词，说明首次碰到，则加入到冲突链表中，当所有文档都解析完成后，单词词典就建立起来了。

在哈希加链表结构中查找某个单词

对单词T哈希，定位哈希表，通过指针找到冲突链表，遍历相应的哈希链表找到这个单词，进而获得这个单词的倒排列表，如果没有找到这个单词则返回空，说明没有文档包含这个单词。

树形结构

主要利用B树高效查找的特点。B树和哈希的查找方式不同，需要字典项进行排序，而哈希并不要求此过程，形成层级查找结构，先找到子树，再进行顺序遍历即可找到匹配的叶子节点。最底层的叶子节点存储单词的地址信息。

倒排列表

倒排列表主要记录那些文档包含某个单词，一个单词会被很多文档包含，这里记录的是文档编号(docId),单词在这个文档出现的TF,以及单词在文档的哪些位置出现，最终形成倒排项。

在实际存储中，为了减少存储空间，通常不会直接的存储docId,而是存储文档编号的差值，文档差值指的是倒排列表中相邻两个倒排索引项DocID的差值，这是因为在索引构建过程中，可以保证后面出现的文档编号要大于前面出现的文档编号。

这实际也是数据压缩的最简单的方法，后面还会更为详细的介绍索引结构的建立，动态索引的维护和更新以及索引在查询中是如何起作用的。