分类： C/C++
2012-07-31 11:33:04
提到搜索引擎，不得不说的就是索引，如果把搜索引擎比喻成一个人，那么索引就是它的大脑。
千万级数据的全文检索搜索引擎------索引。
我们用的这套索引格式和lucene的索引几乎完全一样，这里我们先介绍几个概念和数据类型。
（1）倒排索引（Invert Index）
正常的索引都是根据索引编号，直接找到对应的内容。我们这里做的是一种相反的映射，关键词到文档的映射，根据关键词可以方便找到包含这个关键词的所有文档。这就是倒排索引的概念。
（2）Vint数据类型
Int类型是占用4个字节的存储空间，无论是1还是10000000，占用的存储空间都是4个字节。为了节省存储空间，这里使用了一个Vint数据类型，以一个字节为单位，最高位表示是否还有未完成的数据，低七位用来存储真正的数据。例如：
000000001 ----------->1
011111111 ------------->127
000000001 100000000 ------------>128
000000001 100000001 ------------>129
（3）差分存储
有了2种的VInt数据类型，可以看出越小的整数，消耗的存储空间越小。这样我们就可以利用差分来存储连续出现的Vint数据，a1,a2-a1,a3-a2,......
有了上面的数据结构，我们来介绍索引文件的类型和格式。
（4）文档
文档对应了一条记录，对于电子商务网站来说，一个文档就是一件商品信息。对于Google来说，一个文档就是一个网页记录。后面的Docid对应的就是文档的编号。
（1）.frq文件
词频文件，存储关键词在索引字段中出现的次数。例如：“我爱我家”，‘我’这个关键词的词频就是2。存储内容：docid1，frq1，docid2- docid1，frq2......docidn-docid（n-1），frqn。其中doc使用的就是差分+Vint存储。
（2）.prx文件
词位置文件，存储关键词在索引字段中出现的位置。例如：”我爱我家“，‘我’这个关键词的位置就是1，4。存储内容：pos1，pos2-pos1，pos3-pos2，.....，posn-posn-1。其中pos使用的也是Vint存储。
（3）.wis文件
记录词频文件和词位置文件偏移的索引文件。存储内容：
[VInt]文件中记录总数
[VInt]当前词和前一个词公共前缀的长度
[vInt]当前词剩余长度
[char] 剩余部分的文本信息
[VInt]包含当前词的文档总数
[VInt]当前词的词频信息在.frq文件中出现的偏移
[VInt]当前词的词位置信息在.prx文件中出现的偏移
（4）.wii文件
.wii文件的格式和.wis文件的格式一样，只是对wis文件做了一个索引，虽然wis文件按照词的ascii编码从小到大排序存储，但是在查找时仍然 是很慢的，因为索引比较大原因。wii文件就对wis文件做了切分，每100条记录作为一个区间建立一条索引，每次查找时，先在wii文件中找到对应的区 间，然后定位到最近的偏移位置查找，可以大大提高索引的查找效率。
有了以上4个文件，我们基本上可以完成索引信息的读取了，现在看一下整个流程。对一个索引关键词“A”，现在wii文件中找到所在区间，然后读取低区间的 值，即wis文件中的偏移，然后再wis文件中从偏移开始，查找“A”所在的位置，读取整条记录，获取包含该词的文档总数N，读取在.frq文件中偏移， 直接定位到.frq文件中，读取N次（docid，frq），读取在.prx文件中的偏移，直接定位到.prx文件中，依次取出 frq1,frq2,frq3...,分别读取frq1次,frq2次，frqn 次。这样就可以获取到“A”出现的所有docid，以及在每个doc中出现的位置。得到这些索引信息后，就可以进行搜索了。
以上四个文件是最主要的索引文件，但是还有几个文件也很重要。
（5）dictionary
词典文件，记录当前系统中所有被分词算法切分出来的词。存储内容：
[Vint]词的总数
[Vint]词ID
[Vint]词文本的长度
[char]词文本
（6）Index.fdt
文档信息的集合，最庞大的一个文件，用来在搜索结束时，获取文档信息，返回给客户端。
（7）.fdx文件
对index.fdt文件建立索引，和上面的wis文件一样，如果文件太大，又是变长存储，一般都需要一个索引文件来做随机访问，这个文件的格式也很简单，如下：
[long long]直接记录文档n在fdt文件中的偏移
（8）index.idx文件
记录文档关键码到docid的映射，fdx文件实际上提供了根据docid访问文档的方法。但是我们还需要一种文档到docid的映射，用来在文档更新或者删除时，及时地更新索引数据，这里index.idx就提供了这样一种映射。格式如下：
[int]文档总数
[Vint]docid
[Vint]关键码的长度
[char]关键码的文本
这个文件在系统启动时会装载到内存中，建立hashmap，来做文档Key到docid的映射。
上面是索引系统的一些基本文件格式和数据类型，后面会说明索引的建立过程。
