• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

leveldb

开发技术 开发技术 2周前 (04-29) 4次浏览

1.varint压缩算法

varint是一种对正整数进行可变长字节编码的方法,大多数情况下可起到数据压缩的作用。通常,一个int型整数占4个字节,若该整数的数值小于256,显然一个字节的空间就能存储,浪费了3个字节的空间,而varint就起到了压缩数据的作用。整数数值越小,需要存储的字节数就越少。

variant是可变长的编码方式,但是,它总得知道要读取多少个字节结束啊,总不能一直读下去吧。通常我们需要指定length信息,而variant编码天然包含了length,也就是通过msb位来识别,如果某个数的variant编码的字节的msb位为1,就意味着还要继续读取,没有结束,直到后面的某个字节的msb为0。正是msb的存在可以让数值小的数占用更少的空间,提高了空间利用率。由于每个字节都拿出一个bit做为msb,那么,4个字节最大额能表示的数为 2^{28} ,而不是 2^{32} ,在实际情况下,大于2^{28}的数很少出现,所以在实际工程中并不会影响高效性。
将一个32位无符号int进行编码保存到dst指向的空间:

//dst目标地址的起始地址,返回的ptr压缩后的结束地址
char* EncodeVarint32(char* dst, uint32_t v) { // Operate on characters as unsigneds unsigned char* ptr = reinterpret_cast<unsigned char*>(dst); static const int B = 128;//128 = 2^7 = (1000 0000)2 最高位为1,表示没有完 if (v < (1<<7)) { *(ptr++) = v; } else if (v < (1<<14)) { *(ptr++) = v | B; *(ptr++) = v>>7; } else if (v < (1<<21)) { *(ptr++) = v | B; *(ptr++) = (v>>7) | B; *(ptr++) = v>>14; } else if (v < (1<<28)) { *(ptr++) = v | B; *(ptr++) = (v>>7) | B; *(ptr++) = (v>>14) | B; *(ptr++) = v>>21; } else { *(ptr++) = v | B; //一次取7位加上结束位,后面类似,只是把v的低7位移除 *(ptr++) = (v>>7) | B; *(ptr++) = (v>>14) | B; *(ptr++) = (v>>21) | B; *(ptr++) = v>>28; //最后一位(小端模式),最高位为0,表示已经结束 } return reinterpret_cast<char*>(ptr); }

2.


程序员灯塔
转载请注明原文链接:leveldb
喜欢 (0)