本文主要结合开源lucene谈谈整形值的压缩问题，共分为基于内存的压缩和基于磁盘的压缩，此篇为基于内存的压缩。

假如需将一堆正整数保存在一个集合中，并且能够任意的读写，一般最容易想到的方法是创建一个整形数组或者链表进行保存，但直接保存的缺点在于浪费空间，比如给定100个1-10之间的数只需100*4bit=400bit的空间（10最多需要4个bit），正常需要100*32bit=3200bit的空间，这正是lucene的实现方式。因此一般在压缩前需要算出这一串数字中最大值占用的bit位，然后通过时空的权衡选择合适的实现方法。因为不同的位数可能会跨数据块，如8位、16位、24位、32位、48位、64位可以通过现有的数据类型byte、short、int、long的组合进行表达；5位、11位等等就需要跨long或者int了，比如long可以存12个5bit的值，其余的4位必须和下一个long的1位进行合并这就是所谓的跨块，跨块后速度一定是有影响的，所以lucene给了跨块和不跨块的实现方式。如果不跨块就会浪费空间，这就是时空权衡。

Direct8、Direct16、Packed8ThreeBlocks、Direct32、Packed16ThreeBlocks、Direct64、Packed64这几个类是没有空间浪费的，实际上Packed64就满足实现需求了，底层基于long数组，通过计算设置数值的位置和一些位运算进行实现，但Direct8、Direct16、Packed8ThreeBlocks、Direct32、Packed16ThreeBlocks、Direct64可以直接用byte、short、int、long进行表示，它的位置计算量比Packed64来的高效。

Packed64SingleBlock与Packed64类似，但是它不跨块，是空间换时间的一种实现。支持的数据位是1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16, 21, 32这几种，原因是用这些位数可以尽量减少浪费的空间。假设支持11位那么浪费9bit（64-5*11=9），13位浪费12bit（64-13*4=12），其余大家可以自己算一算，总之浪费的空间确实大了点。

GrowableWriter可在压缩的过程中动态计算值的最大bit位，并且动态扩充，它在某些场景下比如：数据集很大无法一下求出最大值占用的bit位，是很有用的。

PagedGrowableWriter在GrowableWriter基础上扩充了分段能力，即将数据集进行分段压缩比如1-16在段1，17-32在段2等等。同样对于GrowableWriter的使用场景，如果集合中有一个特大的值，那么所有的值都必须按照该值的bit位进行存储，很明显这也是浪费空间的。

PagedMutable与PagedGrowableWriter类似，提供了分段压缩，但是每段不会随着数值位数进行自动扩充，所以本质上跟Direct8、Direct16、Packed8ThreeBlocks、Direct32、Packed16ThreeBlocks、Direct64、Packed64和Packed64SingleBlock类似，只是分段后可以存储更多的值。

接下来说一说PackedLongValues，这个类提供随机读，但是不提供随机写，与PagedGrowableWriter很相似，在添加数值的时候内部会统计最大值所占的bit位，然后分段存储。

DeltaPackedLongValues是继承于PackedLongValues的，如果数值比较接近会将所有值减去最小值后然后再压缩，这样可以进一步减少占用空间。

MonotonicLongValues建立在DeltaPackedLongValues的基础上当给定序列是一个具有仿射函数序列时有较好的压缩效果，直接一点就是近似于一个线性函数序列时，首先通过求解函数的斜率将序列“放平”，得到一个平稳的序列之后，然后通过DeltaPackedLongValues方法进行二次压缩。

需要注意的是当数值bit位达到64的时候，可以存储负数了。