leveldb源代码分析系列1.3:变长编码实现

leveldb中记录user_key和user_value的相关结构使用“varint”编码记录其长度并置于首部,例如skiplist存储的项entry,以及Put时WriteBatch存储的批写入数据格式,对user_key和user_value的长度都采用变长编码。

这样做的目的是节省存储空间,如果采用固定字节的长度记录,如果固定字节太大而大部分的key和value的长度只用一个或两个字节的整形就可以记录,那么就会造成很多浪费,反之如果固定字节太小则限制了数据库存储key和value的长度,所以采用变长编码的方式可以适合于各种情况。

leveldb中关于变长编码和对应的解码函数在文件util/coding.h和util/coding.cc中。主要有定长编码/解码和变长编码/解码系列函数,关于leveldb中的编码策略,首先来看这个函数:

编码后的格式,每个字节分为两部分:最高位和其余位,最高位用来指示下一个字节是否还是编码存储字节,如果是则为1,否则为0,剩余的七位用来存储具体数据。

将一个32位数字v编码位可变长度,并存入以dst开头的地址中,返回结果为末尾存储位的下一位地址。数据由高位到低位存储。由于最高位不用来存储数据,所以一个uint32_t类型的数据最多会被编码为5个字节,当然,如果大部分数据编码后都小于4个字节,还是很赚的。

这个函数还有一个64位版本,原理是一摸一样的,大家自己去分析。

固定编码非常简单,只需要判断系统是大端存储还是小端存储,然后简单的copy一下就可以,此处略过。

对应的解码函数:

从p开始解码出数据并放入value中,首先判断最高位是否为1,如果是1意味着下一个字节中依然有数据存储,通过|操作获得底七位数据,循环继续。

这两个函数属于底层函数,其之上有如下函数:

put系列的函数将value编码然后append进dst中,get系列函数从input中读取数据解码放入value中,低层都是调用了上面介绍的函数。

总的来说leveldb中的变长存储这部分很清晰,不需要过多介绍。

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章