VInt 介紹
VInt (variable-length Integer) 變長整數(shù)，指的是使用動態(tài)變化的字節(jié)數(shù)來表示整數(shù)脾还。我們熟悉的編程語言中肴楷，int 型都是由固定的 4 字節(jié)表示，好處是序列化和反序列化簡單荠呐；缺點是赛蔫，如果需要存儲大量的整數(shù)砂客，特別是數(shù)值較小的整數(shù)占比較大時，比較浪費存儲空間呵恢。因此在很多存儲系統(tǒng)中鞠值，往往使用變長整數(shù)來存儲整型數(shù)據(jù)從從而達到數(shù)據(jù)壓縮的效果。
原理
傳統(tǒng)的整型數(shù)值一般使用 4 字節(jié)來表示渗钉，而變長整數(shù)使用 1 到 5 字節(jié)來表示整型數(shù)值彤恶，每個字節(jié)的最高位為標志位，代表是否還存在下個字節(jié)鳄橘，低 7 位用來表示具體的數(shù)值內(nèi)容声离，如下所示：
VInt 編碼過程：
- 首先從二進制低位開始選取 7 位，并判斷除低 7 位外瘫怜，其他位是否全 0术徊，如果是，執(zhí)行步驟 2鲸湃，否則執(zhí)行步驟 3赠涮；
- 將低 7 位寫入一個字節(jié)，高位補 0 代表該數(shù)值所表示的最后一個字節(jié)暗挑，編碼完成笋除；
- 將低 7 位寫入一個字節(jié)，高位補 1 代表下一個字節(jié)依然需要存儲該數(shù)值的部分數(shù)據(jù)炸裆，并將二進制無符號右移 (>>>) 7 位垃它，進入步驟 1
舉個例子，對于整數(shù) 129烹看，4 字節(jié)二進制表示為 00000000 00000000 00000000 10000001嗤瞎，VInt 第一個字節(jié)寫入的內(nèi)容為 1000 0001（高位為 1 表示下一個字節(jié)還有數(shù)據(jù)），第二個字節(jié)為 0000 0001 （高位為 0 表示這是最后一個字節(jié)）听系。
VInt 解碼過程：
- 從第一個字節(jié)開始讀取，如果最高位為 0虹菲，代表最后一個字節(jié)靠胜，直接返回，否則毕源，將最高位置 0浪漠，進入步驟 2；
- 讀取下一個字節(jié)霎褐，如果高位為 0址愿，代表最后一個字節(jié)，將該字節(jié)左移 7 位并或上上一次的結(jié)果冻璃，否則高位置 0响谓，重復(fù)步驟 2
129 解碼為：0（高位置 0）000 0001 | （0000 0001 << 7）= 0000 0000 1000 0001
lucene 實現(xiàn)
編碼（類 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 的代碼實現(xiàn)的非常優(yōu)雅损合，對照著上面的編解碼過程來看，清晰易懂娘纷。要注意的是嫁审，readVInt 中，最多執(zhí)行 5 次 readByte赖晶，原因是最多 5 個字節(jié)便能表示最大整型數(shù)值律适。每個字節(jié)除去一個標志位，真正表示數(shù)據(jù)的位數(shù)為 7 * 5 = 35遏插，比 32 位還多捂贿，足夠表示最大 int 數(shù)值。
總結(jié)
使用變長編碼后胳嘲，對于不同范圍的整數(shù)可以使用不同數(shù)量的 byte 來表示厂僧，特別在小數(shù)比較多的情況下，壓縮效率非常明顯胎围。因此吁系，在一些存儲系統(tǒng)（比如 lucene）中，常常使用變長編碼來節(jié)約存儲空間白魂。
