存儲2：井然有序——數據文件
的鍵值對都持久化到擴展名為ldb的文件中，一個ldb文件存儲了一定鍵范圍內的鍵值對。
文件分為5個部分，從頭到尾分別是Data Block、 Block、Meta Index Block、Index Block和。
下面就從開始來介紹每個結構，每個結構在內存里面會用一個類表示，為了表示方便，將它們轉換為。
在介紹之前，先介紹，它是一個文件指針，其中指向了文件的偏移量，而size表示這個Block的大小，通過就可以定位到文件里面的某一個Block。
// table/format.h
struct BlockHandler {
varint64 offset;
varint64 size;
}一個最長占用10字節，所以一個最長占用20字節。
而的結構如下:
// table/format.h
struct Footer {
BlockHandler meta_index_block; // 定位Meta Index Block
BlockHandler index_block; // 定位Index Block
byte[n] padding; // 補齊到48字節
int64 magic; // 魔數
}一個最長為20字節，魔數的大小是8字節，所以一個最長為48字節，但是如果長度不固定的話，無法知道開始的字節，所以通過將固定為48字節的大小，而魔數則增加了校驗功能。
拿到一個后數據結構讀取文件，讀取最后48個字節，就可以得到，根據里面的信息就可以讀取Meta Index Block和Index Block。
Block
除了，其它4個部分都是一種Block，可以讀出某個Block的內容，這些Block都有一個通用的結構:
struct Block {
byte[] data;
byte compress_type;
int32 crc;
}data就是數據部分，而表示使用了什么壓縮方式，而crc則是校驗上面兩個字段用的。
為了討論方便，下面介紹各種Block的時候，只專注data里的內容，而忽略其它字段。
Data Block的結構
Meta Index Block和Index Block的存儲格式和Data Black一樣，所以有必要先介紹Data Block的格式。
Data Block的大小默認是4KB（壓縮前），當然也不是精確的4KB，有可能會超過4KB，因為每次插入一個鍵值對的時候會判斷是否超過4KB，如果插入一個比較大的鍵值對，就會遠超過4KB，一個鍵值對只會保存在一個Data Block里。
相鄰的鍵很有可能包含相同的前綴，考慮到這個，Data Block做了優化，采用了前綴壓縮，也就是后面一個鍵只需要記錄前面一個鍵不同的部分，以及和前面一個鍵相同部分的長度，就可以通過前面一個鍵恢復出后一個鍵，這樣可以節省空間。
多個Kv連續存放，如下圖：
一個Kv的結構如下:
struct Kv {
varint32 shared_key_length; // 和前一個鍵相同的前綴長度
varint32 non_shared_key_length; // 不相同的鍵長度
varint32 value_length; // 值的長度
byte[] non_shared_key_content; // 不相同的鍵的內容
byte[] value; // 值的內容
}通過和前一個鍵的值可以得到當前鍵的前綴，然后根據這個Kv里面的后綴，便可以拼接得到這個鍵。
通過這種方式將多個Kv連續存放在Data Block里，可以進行鍵的前綴壓縮。然而這樣會有一個問題，不管得到哪一個鍵的值，都需要從Block的第一個鍵開始依次構造，搜索一個鍵的時候，也需要遍歷整個Block，如果一個Block里有大量的鍵的話，效率會比較低。
針對這個問題，設置了 point數據結構讀取文件，每16個Kv里第一個Kv是一個 point，這個Kv的始終為0，也就是這個Kv不采用前綴編碼，nt里的內容就是整個鍵的內容。這樣就不需要從每一個Data Block的開頭開始構造鍵了，只需要從每一個 point開始構造。另外在每個Data Block的末尾存儲了一個 point數組，指向了每一個 point所在Kv的在塊中的偏移，這樣便可以支持二分搜索，搜索出鍵屬于哪一個 point的組里，然后去搜索這個組里面的16個Kv就可以找到這個鍵。 point數組就像是一個Data Block的稀疏索引，可以加快鍵的查找。
Data Block的結構如下:
// table/block.h
struct DataBlock {
Kv[] kv; // Kv數組
int32[] restart_point_offsets; // restart point偏移數組，指向每一個restart point
int32 restart_point_count; // restart point數量
}根據這個結構，讀取一個Data Block末尾的4個字可以獲取，每個 point的大小是4字節，從末尾 * 4 + 4開始讀取 * 4個字節就可以讀取到 point的偏移數組。
搜索一個鍵：
Index Block
知道Data Block的結構后，Index Block就非常簡單了，它其實就是存儲了一個Kv數組，每一個Kv對應一個Data Block，其中鍵大于等于對應的Data Block中最后一個鍵，值為一個，可以定位到一個Data Block。Index Block就是Data Block的索引，搜索時可以對Index Block二分搜索，找到鍵對應的Data Block。
Index Block里面每一個Kv都是一個 point，也就是沒有采用前綴壓縮，相當于 point是一個稠密索引，每一個Kv都有一個 point對應。
Meta Index Block
和Index Block指向Data Block一樣，Meta Index Block指向 Block，是 Block的索引。不過目前只有一個 Block，也就是里面只有一個Kv。鍵是 Block的名字，而值是一個，指向對應的 Block。
對于目前存在的Bloom 而言，鍵是..。
Index Block的結構如下圖：
Block
目前存在的 Block只有一個，那就是布隆過濾器，如果沒有開啟布隆過濾器，那么就沒有這個 Block。
布隆過濾器是一種數據結構，一種巧妙的概率型數據結構（ data ），特點是高效地插入和查詢，可以用來告訴你某個鍵一定不存在或者可能存在。相比Map和Set布隆過濾器占用的空間少很多，但是結果具有假陽性，如果返回鍵不存在，那么鍵一定不存在，如果返回鍵存在，那么鍵有可能不存在、又有可能存在。具體的可以自己去搜索相關文檔。
如果為每個元素分配10bit，那么假陽率可以降低到1%，是個不錯的數值。
那么為什么需要布隆過濾器呢？
布隆過濾器用于快速判斷一個鍵是否在一個里。正常的查找流程如下:
理想情況下，Index Block可以緩存在內存中，但是Data Block很有可能沒有緩存在內存中，這樣就需要一次隨機磁盤IO。
布隆過濾器比較小，可以緩存在內存中，這樣就可以通過布隆過濾器快速判斷對應的鍵有沒有在這個里。另外如果判斷鍵在，只有1%的可能性最后鍵不在這個里。這是典型的一種空間換時間的思想，選擇布隆過濾器是因為布隆過濾器的空間占用非常小。
采用了多個布隆過濾器，默認情況下，每2KB的數據開啟一個布隆過濾器。
布隆過濾器的數據結構如下:
// table/filter_block.h
struct FilterEntry {
byte[] filter_content; // 表示一個布隆過濾器的內容
}
struct FilterBlock {
FilterEntry[n] entries; // 有多少個布隆過濾器
int32[n] entry_offsets; // 布隆過濾器數據的偏移數組
int32 offset_array_offset; // 偏移數組的偏移
int8 baselg; // 布隆過濾器的大小
}其中表示的是多少數據開啟一個布隆過濾器，默認是11，表示每2KB（2