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 mergetree (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 cost-performance 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 Sect. 6 compare the hybrid use of memory and disk components in the LSM-tree access method with the commonly understood advantage of the hybrid method to buffer disk pages in memory.

Patrick O’Neil

Edward Cheng

Dieter Gawlick

Elizabeth O’Neil

Acta Informatica

ACTA INFORMATICA 提供关于程序、计算系统和信息结构的设计和分析的形式化方法的文章的国际传播，以及理论计算机科学的相关领域，如自动机理论、计算机科学中的逻辑和算法。感兴趣的主题包括:• 编程语言的语义• 用于并发、分布式、反应式和移动系统的模型和建模语言• 用于定时、混合和概率系统的模型和建模语言• 规范、程序分析和验证• 模型检查和定理证明• 模态、时间、一阶和高阶逻辑及其变体• 约束逻辑、SAT/SMT 求解技术• 数据库、半结构化数据和有限模型理论的理论方面• 人工智能的理论方面、知识表示、描述逻辑• 自动机理论、形式语言、术语和图形重写• 基于游戏的模型、综合• 类型理论RY，类型演算• 代数、代数和分类方法• 性能、可靠性和可靠性分析的形式方面• 信息和网络安全的基础• 并行、分布式和随机算法• 算法的设计和分析• 网络和通信协议的基础。

The journal Acta Informatica is dedicated to the international dissemination of research articles on formal methods for the design and analysis of programs, computational systems, and information structures. It covers relevant areas of theoretical computer science, including automata theory, logic, and algorithms in computer science. Topics of interest include: semantics of programming languages, models and modeling languages for concurrent, distributed, reactive, and mobile systems, models and modeling languages for timed, hybrid, and probabilistic systems, specifications, program analysis and verification, model checking and theorem proving, modal logic, temporal logic, first-order and higher-order logics and their variants, constraint logic, SAT/SMT solving techniques, theoretical aspects of databases, semi-structured data, and finite model theory, theoretical aspects of artificial intelligence, knowledge representation, description logic, automata theory, formal languages, term and graph rewriting, game-based models and synthesis, type theory, type calculi, algebraic, categorical, and algebraic methods, formal aspects of performance, reliability, and dependability analysis, foundations of information and network security, parallel, distributed, and randomized algorithms, design and analysis of algorithms, and foundations of network and communication protocols.

《Acta Informatica》期刊致力于国际传播程序、计算系统和信息结构设计与分析的形式化方法的研究文章。它涵盖了理论计算机科学的相关领域，包括自动机理论、计算机科学中的逻辑与算法等。感兴趣的主题包括：编程语言的语义、并发、分布式、反应式和移动系统的模型与建模语言、定时、混合和概率系统的模型与建模语言、规范、程序分析与验证、模型检查与定理证明、模态逻辑、时间逻辑、一阶和高阶逻辑及其变体、约束逻辑、SAT/SMT求解技术、数据库、半结构化数据和有限模型理论的理论方面、人工智能的理论方面、知识表示、描述逻辑、自动机理论、形式语言、术语和图形重写、基于游戏的模型与综合、类型理论、类型演算、代数、代数和分类方法、性能、可靠性和可靠性分析的形式方面、信息和网络安全的基础、并行、分布式和随机算法、算法的设计与分析、网络和通信协议的基础。

The log-structured merge-tree (LSM-tree)

The log-structured mergetree (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.

Category	Quartile
计算机科学	4
计算机科学, 计算机信息系统	4

The log-structured merge-tree (LSM-tree)

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
COMPUTER SCIENCE, INFORMATION SYSTEMS	4