![]() LSM-tree was originally designed for write-intensive workloads. In order to keep down the cost of queries, the system must avoid a situation where there are too many runs.Įxtensions to the 'leveled' method to incorporate B+ tree structures have been suggested, for example bLSM and Diff-Index. For example, in Apache Cassandra, each value represents a row in a database, and different versions of the row may have different sets of columns. Some applications must combine the values in some way to get the proper aggregate value to return. Some applications simply want the newest key-value pair with a given key. The Stepped-Merge version of the LSM tree is a variant of the LSM tree that supports multiple levels with multiple tree structures at each level.Ī particular key may appear in several runs, and what that means for a query depends on the application. To perform a query on a particular key to get its associated value, one must search in the Level 0 tree and also each run. A run can be represented on disk as a single file, or alternatively as a collection of files with non-overlapping key ranges. Each run contains data sorted by the index key. The on-disk data is organized into sorted runs of data. Level 0 is kept in main memory, and might be represented using a tree. Most LSM trees used in practice employ multiple levels. The performance characteristics of LSM trees stem from the fact that each component is tuned to the characteristics of its underlying storage medium, and that data is efficiently migrated across media in rolling batches, using an algorithm reminiscent of merge sort.ĭiagram illustrating compaction of data in a log-structured merge tree If the insertion causes the C 0 component to exceed a certain size threshold, a contiguous segment of entries is removed from C 0 and merged into C 1 on disk. New records are inserted into the memory-resident C 0 component. C 0 is smaller and entirely resident in memory, whereas C 1 is resident on disk. As described by Patrick O'Neil, a two-level LSM tree comprises two tree-like structures, called C 0 and C 1. One simple version of the LSM tree is a two-level LSM tree. LSM trees maintain data in two or more separate structures, each of which is optimized for its respective underlying storage medium data is synchronized between the two structures efficiently, in batches. LSM trees, like other search trees, maintain key-value pairs. In computer science, the log-structured merge-tree (also known as LSM tree, or LSMT ) is a data structure with performance characteristics that make it attractive for providing indexed access to files with high insert volume, such as transactional log data. ![]() Patrick O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth O'Neil ( April 2013) ( Learn how and when to remove this template message) Please help to improve this article by introducing more precise citations. This article includes a list of general references, but it lacks sufficient corresponding inline citations.
0 Comments
Leave a Reply. |