Skip to content

Instantly share code, notes, and snippets.

@kubosuke

kubosuke/log_structured_merged_tree.md

Created February 11, 2022 10:05
Show Gist options
  • Save kubosuke/7e0898da7f96b7360b9432fd93c674d1 to your computer and use it in GitHub Desktop.
Save kubosuke/7e0898da7f96b7360b9432fd93c674d1 to your computer and use it in GitHub Desktop.
Download ZIP
LSM Tree の まとめ
Raw
log_structured_merged_tree.md

LSM

Untitled Diagram

LSM vs B Tree

  • LSM Pros
  1. LSMの方がstorage効率が高い。BTree は pageの空き分storageを浪費してしまう。
  2. 木を管理する必要が無いため、LSMの方がwriteが早い。
  • LSM Cons
  1. compaction, merge処理によってr/wを遅延、待機させてしまうことがある。
  2. compactionが追い付かないくらいの頻度でwriteがあった場合、古いデータが蓄積されていってしまい、結果的にBTreeよりもstorageを浪費する場合がある。

どこで使われている

  • HBase, Cassandra, BigTable
  • Solr, ElasticSearchのエンジンLuceneも似たような構造で動作している。（key: word, value: wordを含むtextのid）
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment