LSM Trees (Cont.) Deletion handled by adding special "delete"entries Lookups will find both original entry and the delete entry,and must return only those entries that do not have matching delete entry When trees are merged,if we find a delete entry matching an original entry,both are dropped. Update handled using insert delete LSM trees were introduced for disk-based indices But useful to minimize erases with flash-based indices The stepped-merge variant of LSM trees is used in many BigData storage systems Google BigTable,Apache Cassandra,MongoDB And more recently in SQLite4,LevelDB,and MyRocks storage engine of MySQL Database System Concepts-7th Edition 24.9 ©Silberscha乜，Korth and SudarshanDatabase System Concepts - 7 24.9 ©Silberschatz, Korth and Sudarshan th Edition LSM Trees (Cont.) ▪ Deletion handled by adding special “delete” entries • Lookups will find both original entry and the delete entry, and must return only those entries that do not have matching delete entry • When trees are merged, if we find a delete entry matching an original entry, both are dropped. ▪ Update handled using insert + delete ▪ LSM trees were introduced for disk-based indices • But useful to minimize erases with flash-based indices • The stepped-merge variant of LSM trees is used in many BigData storage systems ▪ Google BigTable, Apache Cassandra, MongoDB ▪ And more recently in SQLite4, LevelDB, and MyRocks storage engine of MySQL