google早期的索引结构介绍
最近一直在做索引压缩方面的事情，无意中看到了Jeff Dean大牛分享的google早期的索引结构，对于我们这种刚刚起步的搜索公司，还是很有启发意义的，收获还是比较大，所以就简单记录下。
1. 索引压缩常用的压缩算法
淘宝的一篇技术blog分享了一些比较常用的压缩算法：
- varint (变长压缩)： 字节对齐，压缩比不高
- group varint: 变长压缩的变形，比varint的解压速率高很多，这里有它的实现
- Gamma: 对比较小的数字压缩比会比较高，将数值分为两个部分： 一元编码（num_bits）+二进制编码
- Simple9 + simple16: 对于32bit的空间进行组织，可存储多个数值
- PForDelta + NewPForDelta: 比较新的压缩算法，压缩比和解压缩比都比较高效，适合于docid_delta的压缩
关于这些算法的相关介绍可以看下www.wikipedia.org，或者搜下对应的paper.
2. Google的索引结构
可以看到，对于token的doclist是以Block的方式进行组织的，如果doclist比较长，还会使用skip table来快速查找；
Block的组织方式：
a. block header: 使用变长存储与上一个block的delta, 并存储block 实际的存储长度（可能是作为验证）
b. 第二行使用Gamma来压缩编码类型及在block中出现的docs的数目（因为这些数值都比较小）
c. 使用Rice压缩对应docld delta, 其实这里可以使用比较新的压缩算法PFDelta，更高效一些
d. 使用Gamma来压缩对应token在doc中出现的frequence, 即hit的数目
e. 使用length-limit Huffman 来存储Hit Attribute信息，这里主要是利用Attribute的重复的比例会很高，也就是说大部分hit attribute
都会是相同的，所以用到了Huffman压缩，然后对length进行了限制
f: positions用Huffman-Int 来压缩位置信息，由于position分布不确定性很多，对position的压缩一直是业界的难题，压缩比不会很高。
Huffman-Int : 类似于Gamma压缩，但是对于一元编码部分，使用了Huffman code.
优化
这里其实可以将doclist和hit 信息进行分离存储，因为只有在打分的时候才会用到hit的相关信息，访问次数会比较少，而doclist就会访问比较频繁
可以对其进行Cache，这样Cache命中率会更高一些