leveldb源码分析-1-varint

2016/12/29 leveldb

为了节省空间,LevelDB作者设计了一种变长编码方式来表示整型:varint。越小的数字所用的字节数越少。

varint是一种紧凑的表示数字的方法。它用一个或多个字节来表示一个数字,值越小的数字使用越少的字节数。这能减少用来表示数字的字节数。比如对于int32类型的数字,一般需要4个byte来表示。但是采用varint,对于很小的int32类型的数字,则可以用1个byte来表示。当然凡事都有好的也有不好的一面,采用varint表示法,大的数字则需要5个byte来表示。从统计的角度来说,一般不会所有的消息中的数字都是大数,因此大多数情况下,采用varint后,可以用更少的字节数来表示数字信息。

varint编码

varint中的每个 byte 的最高位 bit 有特殊的含义,如果该位为 1,表示后续的 byte 也是该数字的一部分,如果该位为 0,则结束。其他的 7 个 bit 都用来表示数字。因此小于 128 的数字都可以用一个 byte 表示。大于 128 的数字,会用两个字节。

例如:

0000 0001 #(1byte)表示1
1010 1100 0000 0010 #(2byte)表示300 (去除状态位010 1100 000 0010 反转 000 0010 010 1100 简化 1 0010 1100 计算 156 + 32 + 8 + 4 = 300)

举几个数值具体说明下编码规则:

对数字1进行varint编码后的结果为0000 0001,占用1个字节。相比int32字节前面补很多0占用4个字节,节省了3个字节的空间。这里也可以看出varint的想法就是:以标志位替换掉高字节的若干个0

对数字300进行varint编码,原码形式为:

00000000 00000000 00000001 00101100

编码后的数据:第一个字节为10101100,第二个字节为00000010(不够7位高位补0)。

具体的变化步骤:

varint编码

varint编码后的结果为10010110 00000001,即0x96 0x01

源码

相关源码位于

Search

    Table of Contents