US Patent 11372823 File management with log-structured merge bush

Embodiments of the present invention provide a new multi-level data structure, log-structured merge bush (LSM-bush), to alleviate the performance compromise between LSH-table and LSM-tree data structures. Similar to LSM-tree, LSM-bush may buffer writes in memory, merge the writes as sorted runs across multiple levels in storage, and use in-memory fence pointers and Bloom filters to facilitate lookups. LSM-bush differs from LSM-tree in that it allows newer data to be merged more “lazily” than LSM-tree. This can be achieved by allowing larger numbers of runs to be collected at the smaller levels before merging them.