LSM树（Log-Structured Merge Tree）是一种存储结构，被广泛应用于许多NoSQL数据库，如HBase、LevelDB和RocksDB。LSM树的核心思想是通过顺序写来提高写性能，同时通过分层的设计来稍微降低读性能，从而实现高性能的写入操作。

LSM树由以下三个重要组成部分构成：

1. MemTable（内存表）：MemTable是存储在内存中的数据结构，用于保存最近更新的数据。它按照键（Key）有序地组织数据。不同的LSM树实现可能使用不同的数据结构来保证内存中键的有序性，例如HBase使用跳跃表（Skip List）。由于数据存储在内存中，因此需要通过预写式日志（Write-ahead Logging，WAL）来保证数据的可靠性[1]。

2. Immutable MemTable（不可变内存表）：当MemTable达到一定大小后，会转化为Immutable MemTable。Immutable MemTable是将MemTable转换为SSTable（Sorted String Table）的一种中间状态。在转存过程中，不会阻塞数据更新操作[1]。

3. SSTable（有序键值对表）：SSTable是存储在磁盘中的数据结构，包含有序的键值对。为了加快SSTable的读取速度，可以通过建立键的索引和使用布隆过滤器来加速键的查找。LSM树将所有的数据操作记录保存在内存中，当操作记录达到一定数量后，批量顺序写入磁盘。与B+树不同，LSM树的数据更新是以日志的形式进行的，每次数据更新都是追加一条更新记录。这样的设计可以实现顺序写入，只需将Immutable MemTable顺序写入持久化存储即可，而无需修改之前的SSTable中的键，从而保证了顺序写入的性能。因此，当MemTable达到一定大小并转存为SSTable后，不同的SSTable中可能存在相同键的记录，而最新的记录才是准确的[1]。

LSM树的设计虽然大大提高了写性能，但也带来了一些问题：

1. 冗余存储：对于同一个键，除了最新的记录外，其他记录都是冗余的且无用的，但仍然占用存储空间。因此，需要进行Compact操作来清除冗余记录[1]。

2. 读放大：在LSM树中进行数据查找时，需要从最新的SSTable开始逆向查询，直到找到目标键的记录。在最坏情况下，需要查询所有的SSTable。为了优化查找速度，可以使用索引和布隆过滤器[1]。

下面介绍两种常见的LSM树的Compact策略：

1. Size-tiered策略：该策略保证每一层SSTable的大小相近，并限制每一层SSTable的数量。当某一层的SSTable数量达到限制后，会触发Compact操作，将这些SSTable合并成一个更大的SSTable，并写入下一层。然而，这种策略会导致空间放大问题，即同一层的SSTable中可能存在多份相同键的记录，只有执行Compact操作才能消除这些冗余记录[1]。

2. Leveled策略：该策略将每一层的总大小固定，并将每一层划分为多个大小相近的SSTable。这些SSTable在每一层中是全局有序的，即每个键在每一层至多只LSM树（Log-Structured Merge Tree）是一种存储结构，被广泛应用于许多NoSQL数据库，如HBase、LevelDB和RocksDB。LSM树的核心思想是利用顺序写来提高写性能，通过将数据分为内存和磁盘两部分来实现。

下面是对LSM树的详细讲解：

1. LSM树的核心思想

   • MemTable（内存表）：MemTable是在内存中的数据结构，用于保存最近更新的数据。它按照Key有序地组织数据，可以使用跳跃表等数据结构来保证内存中Key的有序性。由于数据保存在内存中，可能会丢失数据，因此通常会使用WAL（Write-ahead logging，预写式日志）来保证数据的可靠性。
   • Immutable MemTable（不可变内存表）：当MemTable达到一定大小后，会转化为Immutable MemTable。Immutable MemTable是将MemTable转换为SSTable（有序键值对集合）的中间状态。在转存过程中，不会阻塞数据更新操作。
   • SSTable（Sorted String Table）：SSTable是LSM树在磁盘中的数据结构，用于持久化存储数据。为了加快SSTable的读取，可以使用索引和布隆过滤器来加快Key的查找。LSM树会将所有的数据操作记录保存在内存中，当达到一定数据量后，再批量地顺序写入磁盘。这种设计保证了顺序写，而不需要修改之前的SSTable中的Key，从而提高写性能。

2. LSM树的Compact策略 LSM树的Compact操作是十分关键的，它用于合并多个SSTable并清除冗余记录，否则SSTable的数量会不断增加。LSM树有两种基本的Compact策略：size-tiered和leveled。

   • Size-tiered策略：该策略保证每层SSTable的大小相近，并限制每一层SSTable的数量。当某一层的SSTable数量达到限制后，会触发Compact操作，将这些SSTable合并成一个更大的SSTable。然而，size-tiered策略可能导致空间放大问题，因为同一层的SSTable中可能存在多份相同Key的记录。

   • Leveled策略：该策略将每一层的总大小固定，并将每一层切分成多个大小相近的SSTable。每一层的SSTable是全局有序的，即每个Key在每一层至多只有一条记录，不存在冗余记录。当某一层的SSTable大小超过限制时，会选择至少一个文件与下一层有交集的部分进行合并。这样可以保证全局有序性，并且避免了空间放大问题。

Learn more:

1. LSM树详解 - 知乎
2. 最容易理解的LSM树--以示例讲解合并查找过程_lsm tree 怎么好懂-CSDN博客
3. LSM Tree原理详解 - 简书