倒排索引

看到有倒排索引，大家肯定会想知道什么是正排索引。
    1.正排索引：知道文档d，得到文档d的关键字的位置序列，实现方式是 文档编号+关键字数组；就像从翻书用页码去找自己想要找的关键字一样。
    2.倒排索引：知道关键字w，找到包含关键字的文档d1,d2,d3…. 实现方式是：关键字key做键的字典，值是文档编号数组；像翻书一样，根据关键字去找有这个关键字的页码
　　无论是哪一种索引，都要用一种能够快速检索的数据结构的来实现，否则它们都会面临大规模甚至超大规模的数据下无法工作的问题。
    倒排索引，索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件(inverted file)。

例题：给上千个文件，每个文件大小为1K—100M。给n个设计算法对每个词找到所有包含它的文件，你只有100K内存

①这个题目就可以用倒排索引。利用关键字key去找到每个含有 关键字的文件地址，从而找到文件。
②用key表示找到的每个词的地址。
③上千个文件，每个文件都单独用一个布隆过滤器进行存储（布隆过滤器使用多个哈希函数对文件内容进行多位置定位存储，不仅仅依赖一个哈希函数，缓解哈希冲突，可以使找到的key更加准确）
④建立一个哈希桶，用数组将每个词存储起来，用每个词去到每个已建立好布隆过滤器的文件去判断这个词是否存在，找到了就把文件地址作为key链接到数组对应位置。