[Table] block_builder.md

class BlockBuilder

[功能]

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

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

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点的存储格式为:

restarts[i]存储着相对于block的offset

[idea]

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

[Table] block_builder.md

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