1 追加式数据库
1.1 基本数据操作
1）set：在文件末尾追加一个 KV 对。
2）get：匹配所有 Key，返回最后（也即最新）一条 KV 对中的 Value。时间复杂度o（n）。
1.2 优缺点
优势：顺序写磁盘，性能不错。
缺点：查找性能差。
适合频繁写，读少的数据。
1.3 建立哈希索引，加快读速度
1.3.1 哈希索引
把value写到磁盘，把key和value在磁盘偏移记录到内存。
（这里如何确定磁盘value间的数据边界呢？采用分隔符或者先记录长度再记录数据的形式）
1.3.2 优缺点
优点：仍然是顺序写磁盘，性能好。
读数据，只需要根据磁盘偏移进行一次IO，性能不错。
缺点：磁盘资源耗尽。
适合频繁读写的场景。
1.3.3 磁盘压缩
1）当写入数据达到一定规模后，进行数据分割即写入到新的文件中。我们把每个文件叫做一个段。
2）段内数据可以进行压缩（只保留最新的key数据）。段之间也可以进行合并。
3）每个段都有自己的内存哈希表。读请求一定从最新的段开始查找KEY ，最新的段没有指定KEY，查找次新的段。
1.4 一些其他问题
- 文件格式。对于日志来说，CSV 不是一种紧凑的数据格式，有很多空间浪费。比如，可以用 length + record bytes 。
- 记录删除。一般是写一个特殊标记（比如墓碑记录，tombstone）以表示该记录已删除。之后 compact 时真正删除即可。
- 宕机恢复。在机器重启时，内存中的哈希索引将会丢失。当然，可以全盘扫描以重建，但通常一个小优化是，对于每个 segment file， 将其索引条目和数据文件一块持久化，重启时只需加载索引条目即可。
- 记录写坏、少写。系统任何时候都有可能宕机，由此会造成记录写坏、少写。为了识别错误记录，我们需要增加一些校验字段，以识别并跳过这种数据。为了跳过写了部分的数据，还要用一些特殊字符来标识记录间的边界。
- 并发控制。由于只有一个活动（追加）文件，因此写只有一个天然并发度。但其他的文件都是不可变的（compact 时会读取然后生成新的），因此读取和紧缩可以并发执行。
顺序写入和原地更行相比，优势有：
- 以顺序写代替随机写。对于磁盘和 SSD，顺序写都要比随机写快几个数量级。
- 简易的并发控制。由于大部分的文件都是不可变（immutable）的，因此更容易做并发读取和紧缩。也不用担心原地更新会造成新老数据交替。
- 更少的内部碎片。每次紧缩会将垃圾完全挤出。但是原地更新就会在 page 中留下一些不可用空间。
当然，基于内存的哈希索引也有其局限：
- 所有 Key 必须放内存。一旦 Key 的数据量超过内存大小，这种方案便不再 work。当然你可以设计基于磁盘的哈希表，但那又会带来大量的随机写。
- 不支持范围查询。由于 key 是无序的，要进行范围查询必须全表扫描。
2 按KEY排序的kv存储表（SSTable，LSM-Tree）
上一节的存储结构，key如果比较多会把内存耗尽。需要一种更加紧密的key存储方式，来容纳更多的key。
2.1 基本操作
在段文件中，按照key排序存储，每个键在一个段文件中只出现一次。（这就不是顺序写入了，每个段文件不应该太大，因为写入是o（n）的时间复杂度了）
key在内存中是顺序表存储而不是存在hash表中。
2.2 优点
2.2.1 段合并更高效
每个段都是按照key排序的，合并段本质就是多路归并排序。
2.2.2 稀疏索引，节省能存空间
把段文件分成多个数据块，给数据块的头部建立顺序表索引。
2.2.3 数据压缩
相邻 Key 共享前缀，既然每次都要批量取，那正好一组 key batch 到一块，称为 block，且只记录 block 的索引。
如图，压缩hand前缀
2.3 提高写入性能
每个写请求都写入段文件，时间复杂度为o（n）。这很慢，比较直观的想法是，攒够一批数据，写入段文件。
2.3.1 写入
内存中维护平衡树（插入，删除，查找，时间复杂度logn），这个树叫做内存表。当内存表达到某个阈值大小，写入磁盘，遍历平衡树实现顺序写入磁盘，高效👍。
2.3.2 读
先看键是否在内存表，再按从新到旧的顺序查找段文件索引。
2.3.3 周期性段合并和压缩数据
2.3.4 crash-safe
为了避免断电造成内存表数据丢失。引入一个写操作追加日志，实现crash-safe（变随机写为顺序写， mysql和redis都有类似的设计）。
