Log Structured Merge (LSM)Tree Consider only inserts/queries for now Lo Records inserted first into in- Memory memory tree (Lo tree) When in-memory tree is full Disk records moved to disk(L1 tree) B+-tree constructed using bottom-up build by merging existing L1 tree with records from Lo tree When L1 tree exceeds some threshold,merge into L2 tree And so on for more levels 。 Size threshold for Li+1 tree is k times size threshold for Li tree Merge creates a new B+-tree using bottom-up build Database System Concepts-7th Edition 24.5 @Silberschatz,Korth and SudarshanDatabase System Concepts - 7 24.5 ©Silberschatz, Korth and Sudarshan th Edition Log Structured Merge (LSM) Tree ▪ Consider only inserts/queries for now ▪ Records inserted first into in￾memory tree (L0 tree) ▪ When in-memory tree is full, records moved to disk (L1 tree) • B + -tree constructed using bottom-up build by merging existing L1 tree with records from L0 tree ▪ When L1 tree exceeds some threshold, merge into L2 tree • And so on for more levels • Size threshold for Li+1 tree is k times size threshold for Li tree • Merge creates a new B+ -tree using bottom-up build