1996 TheLogStructuredMergeTreeLSMTre

(O'Neil et al., 1996) ⇒ Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil. (1996). “The Log-structured Merge-tree (LSM-tree).” In: Acta Informatica, 33(4). doi:10.1007/s002360050048

Subject Headings: Database Index, Log-Structured Merge Tree, B-Tree.

Notes

Cited By

2006

(Chang et al., 2006) ⇒ Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. (2006). “Bigtable: A Distributed Storage System for Structured Data.” In: Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation.
- QUOTE: The manner in which Bigtable uses memtables and SSTables to store updates to tablets is analogous to the way that the Log-Structured Merge Tree (26 ] stores updates to index data. In both systems, sorted data is buffered in memory before being written to disk, and reads must merge data from memory and disk.

Quotes

Author Keywords

Abstract

High-performance transaction system applications typically insert rows in a History table to provide an activity trace; at the same time the transaction system generates log records for purposes of system recovery. Both types of generated information can benefit from efficient indexing. An example in a well-known setting is the TPC-A benchmark application, modified to support efficient queries on the History for account activity for specific accounts. This requires an index by account-id on the fast-growing History table. Unfortunately, standard disk-based index structures such as the B-tree will effectively double the I/O cost of the transaction to maintain an index such as this in real time, increasing the total system cost up to fifty percent. Clearly a method for maintaining a real-time index at low cost is desirable. The Log-Structured Merge-tree (LSM-tree) is a disk-based data structure designed to provide low-cost indexing for a file experiencing a high rate of record inserts (and deletes) over an extended period. The LSM-tree uses an algorithm that defers and batches index changes, cascading the changes from a memory-based component through one or more disk components in an efficient manner reminiscent of merge sort. During this process all index values are continuously accessible to retrievals (aside from very short locking periods), either through the memory component or one of the disk components. The algorithm has greatly reduced disk arm movements compared to a traditional access methods such as B-trees, and will improve costperformance in domains where disk arm costs for inserts with traditional access methods overwhelm storage media costs. The LSM-tree approach also generalizes to operations other than insert and delete. However, indexed finds requiring immediate response will lose I/O efficiency in some cases, so the LSM-tree is most useful in applications where index inserts are more common than finds that retrieve the entries. This seems to be a common property for History tables and log files, for example. The conclusions of Section 6 compare the hybrid use of memory and disk components in the LSM-tree access method with the commonly understood

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
1996 TheLogStructuredMergeTreeLSMTre	Patrick O'Neil Edward Cheng Dieter Gawlick Elizabeth O'Neil			The Log-structured Merge-tree (LSM-tree)