首页 > 其他 > 详细

[Table] block_builder.md

时间:2021-08-20 15:56:04      阅读:14      评论:0      收藏:0      [点我收藏+]

class BlockBuilder

[功能]

class BlockBuilder生成prefix-compressed key的数据块, 输出为一个 Slice

每个key-value块的存储格式为:

form data type
shared_bytes of key: varint32
unshared_bytes of key: varint32
bytes of value: varint32
key_delta: char[unshared_bytes]
value: char[value_bytes]

shared_bytes of key 表示当前 key 与前一个 key 共享的前缀字节数

key1 = "abdkejf"
        |||
key2 = "abdjieksljd"
shared_bytes = 3

前缀带来的问题是keykey之间的依赖, 无法利用数据的有序性来进行快速二分查找, leveldb的作者提供了一个Options::block_restart_interval字段来设置restart点, 每隔Options::block_restart_interval条数据都重新共享前缀, 因此leveldb可以通过直接二分查找restart点对应的key

restart点的存储格式为:

form data type
restarts uint32[num_restarts]
num_restarts uint32

restarts[i]存储着相对于blockoffset

[idea]

block的设计不是太难理解, 主要的地方应该就是前缀与重启点的设计了, 权衡了存储空间与查找效率, 与stl::sort算法的 快速排序->(堆排序,插入排序) 的设计有异曲同工之妙

[Table] block_builder.md

原文:https://www.cnblogs.com/lhcmaple/p/15165826.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!