leveldb表文件格式

赵星宇

本文介绍leveldb的表文件格式。leveldb的表文件是不可变的，一旦形成就不可以修改。下面介绍其布局：

<文件开始>

[数据块 1]

[数据块 2]

...

[数据块 N]

[meta块 1]

...

[meta块 K]

[meta索引块]

[索引块]

[Footer](固定大小; 其开始位置为：文件大小-Footer大小)

<文件结束>

名词介绍：

数据块：存放实际kv对数据的块。

meta块：存放元数据的块，其分为filter块和统计信息块，目前统计信息块还没有实现，所以目前meta块==filter块。

meta索引块：存放meta块名字即key和meta块开始位置和长度即value的kv对数据的块。

索引快：存放每个数据块起始key和数据块开始位置和长度的即value的kv对数据的块。

Footer：固定大小，其开始位置为：文件大小-Footer大小，存放meta索引块和索引块的开始位置和长度。

Footer布局：

metaindex_handle: char[p]; // Block handle for metaindex

index_handle: char[q]; // Block handle for index

padding: char[40-p-q]; // zeroed bytes to make fixed length

// (40==2*BlockHandle::kMaxEncodedLength)

magic: fixed64; // == 0xdb4775248b80fb57 (little-endian)

可以看出其中存放了meta索引块的开始位置和长度、索引块的开始位置和长度。

filter（bloom filter）块布局：

[filter 0]

[filter 1]

[filter 2]

...

[filter N-1]

[filter 0的偏移量] : 4 bytes

[filter 1的偏移量] : 4 bytes

[filter 2的偏移量] : 4 bytes

...

[filter N-1的偏移量] : 4 bytes

[filter偏移量数组的起始位置] : 4 bytes

lg(base) : 1 byte

可以看出一个filter块中会存很多filter，而且一般来说filter块只会有一个。

base表示数据块起始位置映射到filter号时需要除的偏移量。

数据块起始位置除以base就是其对应的filter号。

GET数据过程分析：(很多其实缓存在内存中不用去文件里面读)

GET数据时，首先根据文件大小和Footer的固定大小，找到Footer信息，解析出其中保存的meta索引块的开始位置和长度、索引块的开始位置和长度。并且据此读取出meta索引块和索引块，并根据meta索引块中的信息将filter块读取出来。根据索引块可以找到get的key对应的数据块偏移量。利用这个偏移量计算对应的filter号，找到filter后可以做bloom判断，如果不存在则不用读取数据块，如果存在则读取数据块从中读取数据。