LSMツリー

LSM-tree

書き込みをメモリに溜めてからディスクに順次書き出し、バックグラウンドで統合していく、書き込み性能に最適化されたストレージ用データ構造。

記事1本最終言及

LSMツリー(log-structured merge-tree)は、書き込み性能を高めるために設計されたストレージ用のデータ構造である。新しく届いたデータをまずメモリ内の構造に溜め、一定量に達するとソート済みの不変ファイルとしてディスクに順次書き出し、バックグラウンドの処理がこれらのファイルを複数の段階にわたって統合(コンパクション)し、より大きなファイルに整理する。1996年にPatrick O'Neilらが発表した論文で提案された。

ランダム書き込みを順次書き込みに変換するため書き込みの多い処理に有利で、読み取りは複数段階のファイルを確認する必要があるためブルームフィルタやインデックスで補う。GoogleのBigtableやLevelDB、MetaのRocksDB、Apache Cassandraなど多くのデータベースやキーバリューストアが採用している。

この説明は、AIPOSTの記事と広く知られた事実をもとにまとめたものです。誤りがあれば訂正依頼でお知らせください。

この項目を扱った記事

  • OpenAI、Git互換の新基盤「Pando」でpush遅延を約5分の1にAIニュース ·

    Pandoはこれを、LSMツリーを手本にしたバックグラウンドのコンパクション方式で解決します。

    記事を読む

説明の誤りや、見つからない項目はありますか?

事典の説明は、AIPOSTの記事と広く知られた事実をもとにまとめています。誤りは訂正依頼でお知らせいただければ、確認して修正します。新しい記事に登場した名前は、記事の公開後に事典に加わります。