LSM 木
log-structured merge-tree
高性能トランザクション處理システムでは、通常、履歷テーブルに行を插入することで操作履歷を記錄する。同時に、システム復舊を目的としてログレコードも生成される。これらの生成される情報はいづれも效率的な索引附けによって恩惠を受けることができる。代表的な適用例として、TPC-A ベンチマークアプリケーションを特定アカウントの口座取引履歷に對する效率的なクエリ處理に對應させたケースが擧げられる。これを實現するには、急速に成長する履歷テーブルに對して口座 ID をキーとする索引を作成する必要がある。殘念ながら、B 木などの標準的なディスクベースの索引構造では、この種の索引をリアルタイムで維持するためにトランザクションの I/O コストが實質的に 2 倍になり、システム全體のコストが最大 50% 增加するといふ問題が生じる。明らかに、低コストでリアルタイム索引を維持するための手法が求められてゐる。ログ構造化マージツリー (LSM-tree) は、長期閒にわたって大量のレコード插入 (および削除) が發生するファイルに對して、低コストな索引機能を提供するために設計されたディスクベースのデータ構造である。LSM 木は、索引変更を遲延させてバッチ處理するアルゴリズムを採用してをり、メモリベースのコンポーネントから 1 つ以上のディスクコンポーネントへと變更を效率的に傳播させる。この處理過程において、すべての索引値は連續的に參照可能であり (ごく短時閒のロック期閒を除く)、メモリコンポーネントまたはいづれかのディスクコンポーネントを通じてアクセスできる。本アルゴリズムは、B 木などの從來のアクセス方法と比較してディスクヘッドの移動囘數を大幅に削減してをり、從來のアクセス方法での插入時におけるディスクヘッドコストがストレージメディアコストを壓倒するやうな用途において、コスト效率の向上をもたらす。LSM 木アプローチは、插入と削除以外の操作にも一般化可能である。ただし、卽時應答を必要とするインデックス檢索では、場合によっては I/O 効率が低下するため、LSM 木は特にインデックスへの插入操作が檢索操作よりも頻繁に行はれるアプリケーションにおいて有用である。これは例へば、履歷テーブルやログファイルといったデータ構造に共通する特性と言へる。第 6 節の結論では、LSM 木アクセス方式におけるメモリコンポーネントとディスクコンポーネントのハイブリッド利用と、ディスクページをメモリにバッファリングするといふハイブリッド方式の一般的な利點との比較を行ってゐる。