levelDB源码剖析(1)--概述levelDB项目结构

概述levelDB项目结构

levelDB 是一个持久化kv存储数据库，kv均为任意的字节数组。

其随机写、顺序写/读的性能很高，但是随机读的性能一般。

其实现原理为LSM Tree，简单来说就是讲磁盘的随机写转换成顺序写.

由于磁盘的寻址非常耗时，因此顺序写的速度远远超过随机写.

LSM Tree由两部分组成分别是Log structed和Merge Tree.

其中Log structed是日志结构，而日志本身是不会修改的，只需要追加写.

Merge Tree是合并树，即将多个树合并成一个更大的树.

所以，LSM Tree是数据以追加写的方式写入文件，成为一颗小树，然后合并成更大的树.

在LSM Tree中，更新一个数据不需要修改过去的旧数据，但是此时，
其写的性能很强大，但是需要支付额外的存储空间来作为代价。为了同步提升其读的性能，levelDB也同样支付了一些存储空间作为读性能提升的代价。

具体而言，将索引树结构拆分成多个大小逐渐变大的结构、...，其均为有序的。

最小的位于内存，是所有操作数据的落脚点，保存了最近写入的kv，其也可以随时原地更新，支持随时查询。

其余的...均位于磁盘中，但是每棵树也是有序的。

当执行写操作时：首先将数据加入到层索引树中，当层数据大小达到一定程度时，会执行与层的合并。由于两者均为有序的，所以这个过程类似一个归并，而归并这个操作只需要用到有序写，合并出来的新的会取代掉旧的，当到达指定大小后，也会同样向后合并。

当执行读操作时：在、...中逐层查找，直到找到为止，因此，即使数据没有更新到较高的层中，也不影响数据的正确性。

当然，levelDB具体的实现还是存在一些细节的。

include: 函数库的头文件

port: 可移植性相关的功能

util: 项目用到的一些功能函数

table: SSTable的实现

helpers/memenv：简单完全内存的文件系统，提供操作目录文件接口

benchmarks：性能测试相关代码

db: 数据库实现，版本管理，Compaction，WAL和MemTable实现

cache.h: 缓存接口，提供了默认的LRU缓存，也可以自己实现缓存

comparator.h: 定以数据库比较器的接口，用来比较键，可以使用默认的基于字节的比较，可以定义自己的比较器

dumpfile.h: 以可读文本形式导出一个文件，调试使用

export.h: 可移植性相关

iterator.h: 迭代器接口

slice.h: 实现一个字符串，存储指针和长度，指向字符串

table_builder.h: 构造一个SSTable

write_batch.h: 实现批量写入的接口

c.h: 实现C语言相关的接口

db.h: 操作数据库的主要接口

env.h: 定义操作系统相关的功能，如读写文件之类的

filter_policy.h: 定义布隆过滤器接口

options.h: 配置选项

status.h: 定义数据库操作的返回状态

table.h: SSTable相关的接口