Log Structured Merge Tree (LSM-tree) Implementations (a Demo and LevelDB)
Log structured merge tree, or LSM-tree, is a famous data structure that has been widely adopted by many modern “big data” products, such as BigTable, HBase, LevelDB, etc. Its core idea is very simple and perhaps somewhat counterintuitive if you’re used to the traditional database architecture.
LST-tree keeps data both in memory and on disk. The in-memory part is a conventional update-in-place data structure with necessary indexing. The on-disk part, however, consists of…