LSM-Tree

The Log-Structured Merge-Tree(LSM-Tree)

摘要

高性能事务系统应用程序通常会在历史记录表中插入行，以提供活动跟踪，同时这个事务系统会产生日志记录用作系统恢复。两种类型的生成信息都可以从高效索引中受益。一个众所周知的例子是 TPC-A 基准应用程序，它经过修改以支持对特定帐户的帐户活动历史记录进行有效查询。这需要在快速增长的历史记录表上按帐户 ID 建立索引。遗憾的是，标准的基于磁盘的索引结构（例如 B 树）将有效地使实时维护此类索引的事务 I/O 成本加倍，从而使总系统成本增加高达百分之五十。显然，需要一种以低成本维护实时索引的方法。日志结构合并树 (LSM 树) 是一种基于磁盘的数据结构，旨在为长期经历高记录插入（和删除）率的文件提供低成本索引。LSM 树使用一种延迟和批量处理索引更改的算法，以一种类似于合并排序的有效方式将更改从基于内存的组件级联到一个或多个磁盘组件。在此过程中，所有索引值都可以通过内存组件或磁盘组件之一持续检索（除了非常短暂的锁定期）。该算法与传统的访问方法（如B树）相比，极大地减少了磁盘臂的运动次数，并将提高在那些传统访问方法中磁盘臂成本对于插入操作超过存储介质成本的领域中的性价比。LSM 树方法还可以推广到插入和删除以外的操作。但是，需要立即响应的索引查找在某些情况下会损失 I/O 效率，因此 LSM 树在索引插入比检索条目的查找更常见的应用程序中最为有用。例如，这似乎是历史表和日志文件的共同属性。第 6 节的结论将 LSM 树访问方法中内存和磁盘组件的混合使用与人们通常理解的在内存中缓冲磁盘页面的混合方法的优势进行了比较。