LevelDB 的原理和动机

golist 323

写硬盘

为了持久化, 必须写硬盘.

Log 文件

为了快速写入硬盘, 必须采用追加方式顺序写到 log 文件. 这导致 log 文件中的数据是无序的.

sst 文件

为了快速从硬盘中读取数据, 基于查找算法和局部性原理考虑, 必须将数据排序组织到 sst 文件中.

多个 sst 文件而不是单个

为了快速的插入数据到 sst 文件中, 必须使用多个 sst 文件, 每个 sst 文件只保存一定范围的数据. 堆.

Levels

为了减少 log 文件合并所影响的 sst 文件个数, 将 sst 按层次组织, 层次越深, 文件数量越多. 最坏的情况, 每一次合并都会修改该层次所有的 sst 文件. 而层次越深, 合并发生的概率越小. 树.

Bloom Filter

由于 LevelDB 在某一层查找不存在的数据时, 会继续在下一层进行查找, 所以对于不存在的数据的查找会速度非常慢. 所以, 需要结合 Bloom Filter, 利用 Bloom Filter 能快速地判定”不存在”的特点.

登录发表评论

桂公网安备 45122402000014号