零 版本
Lucene-Core 版本 8.8.2
一 简介
Lucene 的 Index 设计根本依赖磁盘存储，而倒排索引是依赖大量冗余数据来实现分词搜寻的技术，所以 Lucene 在设计的时候用了很多工夫换空间的数据压缩技术，以此保障能在起码的磁盘资源来贮存最多的数据。VInt 就是其中一个很有意思的结构设计。
二 技术原理
1 概要
Java 中一个一般的 int 占据 4 个 byte。
然而当 int 的值为 -128 ～ 127 的时候，其实只须要一个 byte 就能够放得下了，其它三个 byte 都是无意义的冗余（其它几个 byte 所能代表的区间以此类推），实在可能用满这四个 byte 的状况并不多。VInt 的意思是 variant int，也就是可变的 int。其本质是按需分配，缩小这种冗余。
2 byte 批示位
一个失常的 byte 有八个数据无效位，而 VInt 中只有七个，最高位变成了后一个 byte 的批示位。
- 最高位为 1，代表后一个 byte 仍然是以后数据
最高位为 0，代表前面没有数据了
3 VInt 的副作用
- 对于负数来说，因为只有七个数据位，所以当 int 的值比拟大的时候，可能会须要 5 个 byte 能力表述以后的数据（这个问题无奈被解决，VInt 也感觉无需解决，因为状况在实在生产中并不多）
对于正数来说，最高位为 1，无奈被压缩（引入 zigzag 编码）
4 zigzag 编码
应用位移和异或操作将首位的符号位挪到数据的最初一位。
三 Demo
如果须要别离序列化 1 / 200 / -1 这三个 int 数，则 VInt 算法的具体步骤为（无效数据标黄）：
1 二进制化
- 1 的二进制数为 00000000 00000000 00000000 00000001
- 200 的二进制数为 00000000 00000000 00000000 11001000
-1 的二进制数为 11111111 11111111 11111111 11111110
2 向前位移一位，前面补 0
- 1 解决后的二进制数为 00000000 00000000 00000000 00000010
- 200 解决后的二进制数为 00000000 00000000 00000001 10010000
-1 解决后的二进制数为 11111111 11111111 11111111 11111100
3 异或操作
异或操作的实质是不同为 0，雷同是 1。
对于负数，异或一个 11111111 11111111 11111111 11111111
- 1 的解决表达式为 00000000 00000000 00000000 00000010 ^ 11111111 11111111 11111111 11111111 = 00000000 00000000 00000000 00000010；
- 200 的解决表达式为 00000000 00000000 00000001 10010000 ^ 11111111 11111111 11111111 11111111 = 00000000 00000000 00000001 10010000
对于正数，异或一个 00000000 00000000 00000000 00000000
-1 的解决表达式为 11111111 11111111 11111111 11111100 ^ 00000000 00000000 00000000 00000000 = 00000000 00000000 00000000 00000011
4 八位为一个单位解决数字
以八位为一个单位读取数据，当读取到八位之后，将第一位看作是标记位，如果还有其它数据的话，再读取八位。
对于数字 1 来说
序列化过程：
- 先读取七位 0000010，之前都为 0，没有数据，则后面补 0，为 00000010
读取过程：
- 读取序列化数据 00000010，第一位是 0，代表只有一个 byte，前面没有其它数据，故数据为 00000010
- 最初一位是 0，代表是负数，与 11111111 异或操作，失去 00000010
- 将数据往后挪一位，前端补 0，最终为 00000001
对于数字 200 来说
序列化过程：
- 先读取七位 0010000，之前不都为 0，则后面补 1，为 10010000
- 再读取七位 0000011，之前都为 0，则后面补 0，为 00000011
- 组合数据为 10010000 00000011
读取过程：
- 读取序列化数据 10010000，第一位是 1，代表不止一个 byte，前面还有其它数据，故数据为 0010000
- 再读取 00000011，第一位是 0，代表没有其它数据来，数据为 0000011
- 组合数据为 00000001 10010000
- 最初一位是 0，代表是负数，与 11111111 11111111 异或操作，失去 00000001 10010000
- 将数据往后挪一位，前端补 0，最终为 00000000 11001000
对于数字 -1 来说
序列化过程：
- 先读取七位 0000011，之前都为 0，没有数据，则后面补 0，为 00000011
读取过程：
- 读取序列化数据 00000011，第一位是 0，代表只有一个 byte，前面没有其它数据，故数据为 00000011
- 最初一位是 1，代表是正数，与 00000000 异或操作，失去 11111100
将数据往后挪一位，前端补 1，最终为 11111110
四 源码
0 流程
以下源码的调用流程：
- lucene 确认一个 int 值
- 调用 zigZagEncode(...) 将 int 编码成 zint
- 调用 writeVInt(...) 办法将 zint 编码成 vint，并写入到磁盘或者其它内存容器中
- 调用 readVInt() 办法从磁盘或者其它内存容器中读取一个 vint 值，并将其反编码成 zint
调用 zigZagDecode(...) 办法将 zint 反编码成 int
1 writeZInt
writeZInt(...) 办法在 org.apache.lucene.store.DataOutput 中：
// 这个办法用于写入一个 zigzag 编码之后的 int 值public final void writeZInt(int i) throws IOException {// BitUtil.zigZagEncode(i) 用于 zigzag 编码writeVInt(BitUtil.zigZagEncode(i));}// 用于写入一个 VIntpublic final void writeVInt(int i) throws IOException {while ((i & ~0x7F) != 0) { // writeByte(...) 办法用于将 byte 长久化到文件中，临时无需关注 writeByte((byte)((i & 0x7F) | 0x80)); i >>>= 7;}writeByte((byte)i);}2 zigZagEncode
zigZagEncode(...) 办法在 org.apache.lucene.util.BitUtil 中：
// i >> 31 对于负数或者 0 来说，会返回全 0 的屏障// i >> 31 对于正数来说，会返回全 1 的屏障public static int zigZagEncode(int i) {return (i >> 31) ^ (i << 1);}3 readZInt
readZInt(...) 办法在 org.apache.lucene.store.DataOutput 中：
public int readZInt() throws IOException {return BitUtil.zigZagDecode(readVInt());}public int readVInt() throws IOException {// 此处从磁盘读取一个 bytebyte b = readByte();// b >= 0，代表最高位是 0，后续没有值了，以下雷同if (b >= 0) return b;int i = b & 0x7F;// 持续读取一个 byteb = readByte();i |= (b & 0x7F) << 7;if (b >= 0) return i;// 持续读取一个 byteb = readByte();i |= (b & 0x7F) << 14;if (b >= 0) return i;// 持续读取一个 byteb = readByte();i |= (b & 0x7F) << 21;if (b >= 0) return i;// 持续读取一个 byte，在 VInt 的编码下，最高五个 byteb = readByte();i |= (b & 0x0F) << 28;if ((b & 0xF0) == 0) return i;throw new IOException("Invalid vInt detected (too many bits)");}4 zigZagDecode
zigZagDecode(...) 办法在 org.apache.lucene.util.BitUtil 中：
// decode 的操作和 zigZagEncode(...) 是齐全相同的public static int zigZagDecode(int i) {return ((i >>> 1) ^ -(i & 1));}