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
前缀带来的问题是key与key之间的依赖, 无法利用数据的有序性来进行快速二分查找, 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]存储着相对于block的offset
[idea]
block的设计不是太难理解, 主要的地方应该就是前缀与重启点的设计了, 权衡了存储空间与查找效率, 与stl::sort算法的 快速排序->(堆排序,插入排序) 的设计有异曲同工之妙