Key/Value存儲引擎——Bitcask的Java實作
在關系資料庫存儲上，Btree一直是主角，但在讀寫性能要求更高的場景下，log(n)的讀寫操作并不是總是讓人滿意。 Bitcask是一種連續寫入很快速的Key/Value資料存儲結構，讀寫操作的時間複雜度均為常量。它是怎麼做到的呢？
BitCash連續寫入操作
Bitcask具有高效的連續寫入操作，連續寫操作像是不停的向log檔案append message，是以Bitcash也叫Log結構存儲。
BitCash中一個記錄由兩部分組成：
記憶體中的HashMap用來儲存索引索引
磁盤檔案存儲資料
當有資料需要寫入時，磁盤無需周遊檔案，直接寫入到資料塊或者檔案的末尾，避免了磁盤機械查找的時間，寫入磁盤之後，隻需要在記憶體的HashMap中更新相應的索引,記憶體中用HashMap來儲存一條記錄的索引部分，一條索引包含的資訊如下：
[Key: Jason, Filename: employee.db, Offset:0, Size:146, ModifiedDate:2343432312]
[Key: Bill, Filename: employee.db, Offset:146, Size:146, ModifiedDate:5489354345]
Key表示一條記錄的主鍵，查找通過它在HashMap中找到完整索引資訊
Filename是磁盤檔案名字，通過它和Offset找到Value在磁盤的開始位置
Offset是Value在檔案中偏移量，通過它和Size可以讀取一條記錄
Size是Value所占的磁盤大小，機關是Byte
假設目前資料庫中已有上述兩條的記錄，當我要寫入key為 "Jobs"， value為: object的一條新記錄時， 隻需要在檔案employee.db的末尾寫入value=object，在HashMap中添加索引：[Key: Jobs, Filename: employee.db, Offset:292, Size:146, ModifiedDate:9489354343] 即可。
最後資料庫就包含了三條索引資訊：
[Key: Jason, Filename: employee.db, Offset:0, Size:146, ModifiedDate:2343432312]
[Key: Bill, Filename: employee.db, Offset:146, Size:150, ModifiedDate:5489354345]
[Key: Jobs, Filename: employee.db, Offset:294, Size:136, ModifiedDate:948965443]
BitCash随機讀取操作
由于資料在記憶體當中使用HashMap作為索引，查找索引的時間為常量，比如查找Bill，直接通過Key就可以找到它的索引資訊，再根據索引資訊，找到value在檔案位置和大小，精确讀取出bytes，反序列化成value對象。 當然在value存入檔案時需要序列化記憶體對象成bytes。磁盤讀取的過程的時間複雜度也是常量， 并不會随時資料的增大而增大。
BitCash 資料删除和更新
一條記錄包含了索引和資料兩個部分,删除索引容易，但要徹底的删除資料不是件容易的事情(不讨論，參考磁盤空間整理)。對于更新資料，Bitcash通常采用的政策是append一條新資料，并更新已有的索引，至于舊資料則在清理資料的時候把它删除掉。
BitCash适合的場景
适合連續寫入，随機的讀取，連續讀取性能不如Btree
記錄的key可以完全的載入記憶體
value的大小比key大很多,否則意義不大
key/value存儲結構
BitCash Java 實作
代碼：https://github.com/darlinglele/bitcask