LSM-Tree
LSM Tree vs B-Tree
B-Tree 和 LSM-Tree（ Log-Structured Merge-Tree）是两种广泛使用的数据结构，用于实现数据库中的索引和键值存储。B-Tree 通常用于关系型数据库，而 LSM-Tree 通常用于 NoSQL 数据库。
B-Tree 是一种基于页的存储结构，用于快速查找索引数据。每个页存储一定数量的键值对，以保证树的平衡性。查找一个键值对时，B-Tree 从根节点开始，沿着关键字的范围逐级下降，直到找到所需的键值对。B-Tree 适用于需要频繁查找的场景，因为它可以保证较快的查询速度。
相反，LSM-Tree 是一种基于磁盘的键值存储结构，使用 SSTable 来持久化存储键值对。LSM-Tree 的写入速度很快，因为所有写入操作都被追加到内存中的日志文件中。为了提高查询速度，LSM-Tree 使用了一种合并策略，即周期性地将较小的 SSTable 合并为较大的 SSTable。由于 SSTable 中的键值对是按照键有序存储的，因此 LSM-Tree 的查询速度也比较快。
总体而言，B-Tree 更适用于查询密集型的场景，而 LSM-Tree 更适用于写入密集型的场景。
- B-Tree 适用于查询密集型的场景，因为 B-Tree 通过保持树的平衡性和范围查询等优化方式，可以提供较快的查询速度。LSM-Tree 适用于写入密集型的场景，因为 LSM-Tree 通过将写入操作追加到内存中的日志文件中，并定期将较小的 SSTable 合并为较大的 SSTable，可以提供较快的写入速度。
- 许多数据库系统（如 MySQL 和 PostgreSQL）使用 B-Tree 作为索引结构，而 NoSQL 数据库系统（如 Cassandra 和 RocksDB）通常使用 LSM-Tree 作为键值存储结构。
早期 LSM-Tree
早期的 LSM-Tree 中通常使用了 C0-tree 和 C1-tree 来存储数据。
- C0-tree 存储在内存中。
- C1-tree 存储在磁盘上。
新插入的数据首先被写入到 C0-tree 中，这个过程非常快速。当 C0-tree 达到一定大小时，它会被刷新到磁盘上的一个新的 C1-tree 中。
查询操作会首先在 C0-tree 中查找数据，如果没有找到，则会继续在 C1-tree 中查找。
由于磁盘 I/O 通常比内存访问慢得多，因此这种方法可以减少对磁盘 I/O 带宽和延迟的需求，并提高查询效率。
现代 LSM-Tree
现代的 LSM-Tree 通常由三个部分组成：内存表（memtable）、不可变内存表（immutable memtable）和 SSTable。
这些部分各自扮演不同的角色：
- 内存表（memtable）：通常是一个基于内存的数据结构，用于缓存最新插入的数据。Memtable 可以使用各种有序高效的数据结构来实现，如跳跃表、红黑树等。在 KV 存储场景下，Memtable 中存储的是最近更新的键值对记录，可以简单地理解为一个 Map 中的 key-value 对。
- 不可变内存表（immutable memtable）
- 不可变内存表是在内存中创建的一个新的数据结构，它包含了内存表中所有的键值对，并且不能被修改。当内存表达到一定大小时，它会被刷新到一个新的不可变内存表中。
- 引入不可变内存表副本的主要目的是为了避免读写冲突和竞争条件，在高并发环境下提高系统性能。
- SSTable
- SSTable 是一种用于持久化数据到磁盘的数据结构。按照 key 有序排列的键值对，可以采用类似 Kafka 的线性索引来加速查询过程。
- 在持久化过程中，内存中有序的键值对会被 dump 成一个个 segment，后面存储的段和前面存储的段可能存在重复的 key，最靠后的段中的记录值就是某个 key 最新的状态。
- SSTable 存储方式的一个问题是可能存在大量的重复数据，这会导致磁盘空间的浪费。由于 SSTable 是不可变的，因此在进行更新操作时需要创建新的 SSTable，并将旧的 SSTable 标记为过期。这样会导致磁盘上存在大量过期但未被清理的 SSTable 文件，占用了宝贵的磁盘空间。为了解决这些问题，LSM-Tree 引入了 Compaction 机制来合并和清理过期的 SSTable 文件。
压缩数据
在 Compaction 过程中，会将多个 SSTable 文件按照顺序读取，并将其中相同 key 的记录进行合并和去重。最终生成一个新的 SSTable 文件，并更新索引信息。这样就可以减少磁盘上存在大量过期但未被清理的 SSTable 文件，同时也可以减少重复数据和冗余信息，提高查询效率和节约磁盘空间。
读取流程
现代 LSM-Tree 的读取操作通常采用了多层缓存的方式来提高查询效率。具体来说，现代 LSM-Tree 通常会采用三层缓存：内存缓存、Bloom Filter 和 Block Cache。
- 内存缓存是指将最近写入的数据保存在内存中，以提高读取效率。当需要查询某个 key 时，先在内存中查找是否存在该 key 对应的记录，如果存在则直接返回结果；否则继续查找下一层缓存。
- Bloom Filter 是一种快速判断某个元素是否存在于集合中的数据结构。在现代 LSM-Tree 中，每个 SSTable 文件都会对应一个 Bloom Filter。当需要查询某个 key 时，可以先在 Bloom Filter 中查找该 key 是否可能存在于 SSTable 文件中。如果 Bloom Filter 返回不存在，则可以直接返回查询结果；否则继续查找下一层缓存。
- Block Cache 是指将磁盘上最近访问过的数据块保存在内存中，以提高读取效率。当需要查询某个 key 时，在经过前两层缓存后，会从磁盘上读取相应的数据块，并将其保存到 Block Cache 中。如果下次再需要访问该数据块，则可以直接从 Block Cache 中读取，而无需再次访问磁盘。
通过这三层缓存的组合使用，现代 LSM-Tree 可以实现较高的查询效率和较低的延迟。
修改流程
- 将写入的数据先保存到内存缓存中。这样可以避免频繁地写入磁盘，提高写入效率。
- 当内存缓存达到一定大小时，将其转化为一个新的 SSTable 文件，并将该文件写入磁盘。同时，将该 SSTable 文件添加到 LSM-Tree 的层次结构中。
- 由于新的 SSTable 文件可能会包含与已有 SSTable 文件相同的 key，因此需要进行 Compaction 操作来合并和清理过期的 SSTable 文件。在 Compaction 过程中，会将多个 SSTable 文件按照顺序读取，并将其中相同 key 的记录进行合并和去重。最终生成一个新的 SSTable 文件，并更新索引信息。
- 在 Compaction 完成后，旧的 SSTable 文件可以被删除或标记为过期。同时，内存缓存也可以被清空，以便接受下一批写入操作。
删除流程
- 当需要删除某个 key 时，先将该 key 对应的记录标记为删除状态。这样可以避免直接删除记录，从而保证数据一致性和可靠性。
- 标记为删除状态的记录会在后续的 Compaction 过程中被清理掉。在 Compaction 过程中，会将多个 SSTable 文件按照顺序读取，并将其中相同 key 的记录进行合并和去重。如果某个 key 对应的记录被标记为删除状态，则会将其从新生成的 SSTable 文件中移除。
- 在 Compaction 完成后，旧的 SSTable 文件可以被删除或标记为过期。同时，内存缓存也可以被清空，以便接受下一批写入操作。
总结
- LSM-Tree（Log-Structured Merge Tree）是一种磁盘上的数据结构，用于高效地处理大量写入操作。
- 它将写入操作缓存在内存中，并定期将其刷入磁盘。
- LSM-Tree 使用 Sorted Strings Table（SSTable）来持久化键值对，其中键按顺序排序。
- 为了保证数据一致性和可靠性，LSM-Tree 采用 Compaction 操作来合并和清理过期的 SSTable 文件。
- 现代 LSM-Tree 通常包括多个层次结构，每个层次结构包含多个 SSTable 文件，并且每个层次结构的 SSTable 文件大小逐渐增加。通过这种方式，现代 LSM-Tree 可以实现高效地处理大量写入和删除操作，并且保证数据一致性和可靠性。