考虑一下未来个人使用的设备,它将是一个机械化的个人图书馆,它需要一个名字引起人们的注意:"MEMEX"就可以.MEMEX是这样一个机械化设备,人们可以在其中存储书籍、记录和信件,同时可以以很高的速度和极强的灵活性完成检索.作为辅助设备,它是人脑的无限扩大.——Bush，1945
说到提高检索效率，就必然提到索引。今天就来为大家讲述搜索引擎中最常见的索引方式——倒排索引。
没有索引的时代走入一个书店，这个书店的书只是乱糟糟的摆在一起，你现在想要找到一本叫做《Spring in action》的书，你要怎么办？嗯……是的，你只能一本一本的翻，直到翻到这本书为止。结果你翻到最后一本才发现，这个书店并没有你想要的书。你已经在这里花费了一整天的时间（好在这个书店不大），你身心疲惫地骂了句“操蛋”，离开了这个书店。
这种在没有任何索引的情况下检索信息（或者说查找）的方式，我们可以称之为grep。我们一般在类UNIX系统中使用的grep命令就是用类似的方法进行检索的，win系统中常用的文本检索（Ctrl+F）也是如此。对于计算机来讲，扫描整个文件的速度会远快于一个人翻阅整个书店，因此在检索少量信息时（例如，单个文本文件的信息）是足够的。但是当信息量变得十分庞大时，就会变得十分缓慢。比如在类UNIX系统中的grep命令，去扫描大文件夹的时候，就可能慢得无法忍受。
传统索引你实在是需要《Spring in action》这本书，你今天又来到了一个看起来十分古老的图书馆。这个图书馆的藏书不少，但是并没有什么图书管理信息系统，但是他们有一套自己的索引系统——书名书目检索柜。大概就是这么个东西：
你回忆起来你小时候似乎见过这个东西（大概，上个世纪末吧）这个柜子上每一个抽屉都对应着一个分类，比如历史、法律、计算机等等。你找到了计算机分类的抽屉，然后拉开了抽屉，你看到里边有非常非常多的卡片：
这些卡片被一些标着字母的大卡片分组隔开，分为了26组。你知道这意味着每一组都是标题以某一字母或某一拼音开头的图书的信息。这些卡片叫做索引卡片。这些卡片都是按照字母或拼音顺序进行排序的。有了这个排序，你很快就从S分组中找到了《Spring in action》这本书。然后根据索引卡片上关于图书存放位置的指示很快的找到了这本书。你心满意足的回家去了~
这种索引技术其实和电脑上传统的索引技术是相同的。这就相当于为图书的分类信息和书名信息做了索引。而且还是联合索引。我们同样也发现联合索引的一个局限性，就是联合索引是有先后顺序的。比如说你先对分类做索引，再对书名做索引。这时你在查找的时候，如果你不先查找分类，而是先查找了书名，这个索引就不起作用了。对我们的另一个启示就是，索引之所以快的原因，是因为有序（从计算机的角度讲，有序就可以使用二分查找，这是十分高效的）。
词汇文档矩阵你看完《Spring in action》之后还想深入学习一些关于依赖注入的内容，然而你不知道什么书会讲这部分内容。你想去图书馆再找找。然后你又一次来到了那个老旧的图书馆，你再一次打开了计算机分类的抽屉，看着数以千计的卡片，陷入了深深的沉思……这根本找不到嘛……这和翻书店有什么区别？更何况光看标题可能也看不出什么。
我们发现此时此刻你的需求变了，你不是要找具体的某本书了，你要找的是具有某个主题的书。这个主题可能是一句话，可能是一个词。而我们发现一句话的最小组成粒度也是词（或字）。所以我们发现我们最终要做的其实是对词做索引。那么我们要怎么做呢？首先我们可以做一个“词汇-文档矩阵”，横坐标为文档id，纵坐标为具体词汇：
我们可以让纵坐标的词汇有序排列（比如按照字母/拼音顺序排列），这样我们就可以快速的定位到一个词汇。然后我们再去找都有哪些文档对应着这些词汇。但是“词汇-文档矩阵”只是一个概念模型，我们如何在计算机中使用数据结构实现这个概念呢？