Log Structured Merge Tree (LSM-tree) Implementations (a Demo and LevelDB)

Eileen Pangu
8 min readDec 28, 2020

Background

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…

--

--

Eileen Pangu

Manager and Tech Lead @ FANG. Enthusiastic tech generalist. Enjoy distilling wisdom from experiences. Believe in that learning is a lifelong journey.