LSM Tree Basic Implementation

• Memtable
  • Implement SkipList Data Structure
  • Flush Memtable data to Disk
• SSTable
  • SSTable Files (*.sst 확장자)
    • Encoding Key/Value
  • Indexing SSTable for Efficient Access
• Write-Ahead Log
• Compaction
• Bloom Filters

           +-----+-------------+--+----+----------+--...-+-------------+
.sst File  | dataBlock  | dataBlock    | dataBlock | ...  | IndexBlock   |
           +-----+-------------+--+----+----------+--...-+-------------+

           +-----+-------------+--+----+----------+------+--------- ... ----+
dataBlock  | dataEntry  | dataEntry    | dataEntry  | dataEntry   |         |  
           +-----+-------------+--+----+----------+------+--------- ... ----+
           |<---------------- maxBlockSize -------------------------------->|

  maxBlockSize = 4KB

           +-----+-------------+---+----------+------+--  ...   --------+
indexBlock | offset  | offset  | offset  | offset   |     ...   | footer |  
           +-----+-------------+---+----------+------+--  ...   --------+
           
footer: (number of Offsets, index size)
offsets: (last key in dataBlock, offset)