VInt 介绍
VInt (variable-length Integer) 变长整数，指的是使用动态变化的字节数来表示整数。我们熟悉的编程语言中，int 型都是由固定的 4 字节表示，好处是序列化和反序列化简单；缺点是，如果需要存储大量的整数，特别是数值较小的整数占比较大时，比较浪费存储空间。因此在很多存储系统中，往往使用变长整数来存储整型数据从从而达到数据压缩的效果。
原理
传统的整型数值一般使用 4 字节来表示，而变长整数使用 1 到 5 字节来表示整型数值，每个字节的最高位为标志位，代表是否还存在下个字节，低 7 位用来表示具体的数值内容，如下所示：
VInt 编码过程：
- 首先从二进制低位开始选取 7 位，并判断除低 7 位外，其他位是否全 0，如果是，执行步骤 2，否则执行步骤 3；
- 将低 7 位写入一个字节，高位补 0 代表该数值所表示的最后一个字节，编码完成；
- 将低 7 位写入一个字节，高位补 1 代表下一个字节依然需要存储该数值的部分数据，并将二进制无符号右移 (>>>) 7 位，进入步骤 1
举个例子，对于整数 129，4 字节二进制表示为 00000000 00000000 00000000 10000001，VInt 第一个字节写入的内容为 1000 0001（高位为 1 表示下一个字节还有数据），第二个字节为 0000 0001 （高位为 0 表示这是最后一个字节）。
VInt 解码过程：
- 从第一个字节开始读取，如果最高位为 0，代表最后一个字节，直接返回，否则，将最高位置 0，进入步骤 2；
- 读取下一个字节，如果高位为 0，代表最后一个字节，将该字节左移 7 位并或上上一次的结果，否则高位置 0，重复步骤 2
129 解码为：0（高位置 0）000 0001 | （0000 0001 << 7）= 0000 0000 1000 0001
lucene 实现
编码（类 DataOutput）
public final void writeVInt(int i) throws IOException {
while ((i & ~0x7F) != 0) {
writeByte((byte)((i & 0x7F) | 0x80));
i >>>= 7;
}
writeByte((byte)i);
}
解码（类 DataInput）
public int readVInt() throws IOException {
/* This is the original code of this method,
* but a Hotspot bug (see LUCENE-2975) corrupts the for-loop if
* readByte() is inlined. So the loop was unwinded!
byte b = readByte();
int i = b & 0x7F;
for (int shift = 7; (b & 0x80) != 0; shift += 7) {
b = readByte();
i |= (b & 0x7F) << shift;
}
return i;
*/
byte b = readByte();
if (b >= 0) return b;
int i = b & 0x7F;
b = readByte();
i |= (b & 0x7F) << 7;
if (b >= 0) return i;
b = readByte();
i |= (b & 0x7F) << 14;
if (b >= 0) return i;
b = readByte();
i |= (b & 0x7F) << 21;
if (b >= 0) return i;
b = readByte();
// Warning: the next ands use 0x0F / 0xF0 - beware copy/paste errors:
i |= (b & 0x0F) << 28;
if ((b & 0xF0) == 0) return i;
throw new IOException("Invalid vInt detected (too many bits)");
}
lucene 的代码实现的非常优雅，对照着上面的编解码过程来看，清晰易懂。要注意的是，readVInt 中，最多执行 5 次 readByte，原因是最多 5 个字节便能表示最大整型数值。每个字节除去一个标志位，真正表示数据的位数为 7 * 5 = 35，比 32 位还多，足够表示最大 int 数值。
总结
使用变长编码后，对于不同范围的整数可以使用不同数量的 byte 来表示，特别在小数比较多的情况下，压缩效率非常明显。因此，在一些存储系统（比如 lucene）中，常常使用变长编码来节约存储空间。
