索引其实在日常生活中是很常见的，比如书籍的目录就是一种索引结构，目的是为了让人们能够更快地找到相关章节内容。再比如像hao123这种类型的导航网站本质上也是互联网页面中的索引结构，目的类似，也是为了让用户能够尽快找到有价值的分类网站。

　　在计算机科学领域，索引也是非常常用的数据结构。其根本目的是为了在具体应用中加快查找速度。比如在数据库中，在很多高效数据结构中，都会大量采用索引来提升系统效率。

　　具体到搜索引擎，索引更是其中最重要的核心技术之一，面对海量的网页内容，如何快速找到包含用户查询词的所有网页?倒排索引在其中扮演了关键的角色。本文主要讲解与倒排索引相关的技术。

　　本文通过引入简单实例，介绍与搜索引擎有关的一些基本概念，了解这些基本概念对于以后深入了解索引的工作机制非常重要。

　　单词-文档矩阵

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

　　图1：单词-文档矩阵

　　从纵向即文档这个维度来看，每列代表文档包含了哪些单词，比如文档1包含了词汇1和词汇4，而不包含其他单词。从横向即单词这个维度来看，每行代表了哪些文档包含了某个单词。比如对于词汇1来说，文档1和文档4中出现过词汇1，而其他文档不包含词汇1，矩阵中其他的行列也可做此种解读。

　　搜索引擎的索引其实就是实现单词-文档矩阵的具体数据结构。可以有不同的方式来实现上述概念模型，比如倒排索引、签名文件、后缀树等方式。但是各项试验数据表明，倒排索引是单词到文档映射关系的最佳实现方式，所以本文主要介绍倒排索引的技术细节。

　　倒排索引基本概念

　　在这里向大家解释倒排索引常用的一些专用术语

　　文档：一般搜索引擎的处理对象是互联网网页，而文档这个概念要更宽泛些，代表以文本形式存在的存储对象。相比网页来说，涵盖更多形式，比如Word、PDF、XML等不同格式的文件都可以称为文档，再比如一封邮件、一条短信、一条微博也可以称为文档。

　　文档集合：由若干文档构成的集合称为文档集合。比如海量的互联网网页或者说大量的电子邮件，都是文档集合的具体例子。

　　文档编号：在搜索引擎内部，会为文档集合内每个文档赋予一个唯一的内部编号，以此编号来作为这个文档的唯一标识，这样方便内部处理。每个文档的内部编号即称为文档编号。

　　单词编号：与文档编号类似，搜索引擎内部以唯一的编号来表征某个单词，单词编号可以作为某个单词的唯一表征。

　　倒排索引：倒排索引是实现单词-文档矩阵的一种具体存储形式。通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：单词词典和倒排文件。

　　单词词典：搜索引擎通常的索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息及指向倒排列表的指针。

　　倒排列表：倒排列表记载了出现某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项。根据倒排列表，即可获知哪些文档包含某个单词。

　　倒排文件：所有单词的倒排列表往往顺序地存储在磁盘的某个文件里，这个文件即被称为倒排文件，倒排文件是存储倒排索引的物理文件。

　　关于这些概念之间的关系，通过图2可以比较清晰地看出来。

　　图2：倒排索引基本概念示意图

　　倒排索引简单实例

　　倒排索引从逻辑结构和基本思路上讲非常简单。下面我们通过具体实例来进行说明，使得大家能够对倒排索引有一个宏观而直接的感受。

　　假设文档集合包含5个文档，每个文档包含内容如下图所示，在图3中最左端一栏是每个文档对应的文档编号，我们的任务就是对这个文档集合建立倒排索引。

　　图3：文档集合