LSM-tree
Log-Structured Merge tree。書き込みの多い現代のデータベースを支えるデータ構造。書き込みはまずRAM（memtable）に入り、ディスク上の不変のソート済みファイル（SSTable）へフラッシュされ、バックグラウンドでコンパクションされる。
O'Neilらが1996年に発表した。書き込みではB木に勝る。ランダムI/Oの代わりにシーケンシャルI/Oを使い、インプレース更新がないためだ。読み取りはやや不利で、複数のレベルを確認する必要があるが、SSTableごとのブルームフィルタで補う。
LevelDB、RocksDB、Cassandra、ScyllaDB、HBase、BigTable、DynamoDB、MongoDBのWiredTiger、FoundationDBの基盤である。調整の要点はtiered型とleveled型のコンパクション、そして書き込み・読み取り・領域の増幅率だ。