Stepped Merge Index Stepped-merge index:variant of LSM tree with k trees at each level on disk Memory When all k indices exist at a level,merge them into one Disk index of next level. ·Reduces write cost compared to LSM tree But queries are even more expensive since many trees need to be queries Optimization for point lookups Compute Bloom filter for each tree and store in- memory Query a tree only if Bloom filter returns a positive result Database System Concepts-7th Edition 24.8 @Silberschatz,Korth and SudarshanDatabase System Concepts - 7 24.8 ©Silberschatz, Korth and Sudarshan th Edition Stepped Merge Index ▪ Stepped-merge index: variant of LSM tree with k trees at each level on disk • When all k indices exist at a level, merge them into one index of next level. • Reduces write cost compared to LSM tree ▪ But queries are even more expensive since many trees need to be queries ▪ Optimization for point lookups • Compute Bloom filter for each tree and store in￾memory • Query a tree only if Bloom filter returns a positive result