最近在做Mini-LSM，在实现过程中，遇到了些小问题
问题背景
在 LSM 树中，数据被组织成多个层级的存储结构，通常包括内存中的 MemTable 和磁盘上的多个层级的文件（如 LevelDB 中的 SSTable）。当 MemTable 达到一定大小时，它会被冻结并写入磁盘，形成一个新的层级文件。在 MemTable 被冻结并写入磁盘之后，如果其中的键（key）在后续的层级文件中被删除且不做合适的处理，那么在扫描（scan）数据时，这些已经被删除的键仍然有可能被读取到。这是因为删除操作可能没有被正确地传播到所有的层级文件中，导致旧版本的数据仍然可见。
解决方案
- 在下层的两个 iterator（迭代器）进行扫描时，必须将被删除的键也包含在迭代过程中。
- 在合并（merge）的过程中，由于会优先访问最新的层级文件，因此可以检查键是否在最新的层级文件中被删除。
- 在合并 iterator 的过程中，去掉所有被删除的键。
原理解释
- 删除操作的处理：在 LSM 树中，删除操作通常不是直接从磁盘上移除数据，而是标记数据为已删除。这通常通过在新的层级文件中记录一个删除标记（tombstone）来实现。
- Iterator 的作用：iterator 用于遍历 LSM 树中的数据。在合并多个层级文件时，需要确保所有层级文件中的数据都被正确地合并，并且删除标记被正确处理。
- Merge Iterator：在合并多个层级文件时，merge iterator 会按照键的顺序合并数据。由于 LSM 树会优先访问最新的层级文件，因此在合并过程中可以检查键是否在最新的层级文件中被删除。
- Fuse Iterator：在 fuse iterator 的过程中，需要去掉所有被删除的键，以确保最终返回的数据是正确的。
实现细节
- 不进行过滤处理：在下层的两个 iterator 中，不对数据进行过滤处理，确保所有键（包括被删除的键）都被读取出来。
- 合并数据：在 merge iterator 这一层，按照新旧顺序合并数据。如果一个键在最新的层级文件中被标记为删除，则在合并过程中将其过滤掉。
- 删除操作的处理：删除操作本质上是将值置空，因此不需要进行特殊处理，只需要在合并过程中按照规则过滤掉被删除的键。