Log Structure Unordered 数据库文件中纪录无序 Ordered 数据库文件中纪录有序 Ordered 数据库文件中纪录有序 Index In-Memory Hash Map 纪录 每个 key 对应其在数据库 文件中的纪录的位置 <= 同左 Log-Structured Merge-Tree 使用平衡树或者红黑树实现的， 查询快，索引 key 有序 Query 通过索引找到数据所在文件位置 <= 同左 假如索引 miss，因为数据有 序， 从数据文件中查找更快了 ， 可以二分查找，不用遍历。 <= 同左 由于索引中的 key 有序，且数 据库文件中纪录有序，因此 不需 要把全部 key 落索引中 。 Write 更新索引、 追加写最后一个文件分片 <= 同左 虽然数据库文件中纪录有序，但 是不需要保证它一直是有序的。 在数据写入时去实时重新排序数 据文件中的纪录会很耗 I/O。 顺 序写一个新纪录的文件，再定期 做压缩合并是更合理的做法。 更新索引、 写 WAL 防 crash Compaction 追加写导致一个 key 可能出现在 多个文件分片。需要做压缩。背 景线程对现有数据进行压缩合 并，合并完后使用新的分片文件 及索引，旧文件和索引丢弃。 除了未压缩过的文件，其他文件 都是有序的，因此压缩合并时可 以使用类似合并排序的做法。 性 能更高、内存消耗更少。 压缩合并时， 新增的数据不再存 在文件中，而是直接在索引中 取。 而且索引中已经排好序，这 会使合并性能更好。 Pros and Cons + 实现简单 - Hash map 不适合存磁盘。如 果 key 太多，内存可能不够用 - 无法做范围查询 对比左边方案： + 压缩性能更好 + 可以做范围查询 - Hash map key 过多时内存可 能不够用 对比左边方案： + 压缩性能更好 + 不需要全量数据进索引