5 index compression

compression对于想要高效使用index而言起着很大作用，第一，可以增加caching的利用率；第二，可以提高数据从disk到memory的传输速率。说到底就是用计算（compression & decompression）时间来换取空间。
常见的compression技术基本可以达到1:4的compression radios


Heap‘s law：估算文档中terms的个数。
其中T为文档中token的个数（字数），k和b为系数，30<=k<=100, b约等于0.5
这个公式略蛋疼，作为以下推断的论据：当文档数目增多时，用在index中作为key的terms也会增多，因而导致compression是很必要的操作。。。

Zipf's law：估算term的分布，用来改善compression算法
(128)the average length of a term in english is about eight characters

压缩dictionary的方式：
1.将search tree做优化，在部分树节点使用单链表方式链接
2.front coding. 将字典排序后根据位不同进行压缩，即将相同位省略


压缩postings file的方式：
（未完待续）