这一章节介绍了两大类存储引擎：

1、日志结构的存储引擎（log-structured）

2、面向页面的存储引擎（page-oriented），比如B树

拿最简单的append only的日志作为例子，引出存储和检索功能，为了加快查询速度，增加Hash索引，在内存中使用Hash映射来存储key-value在文件中的偏移量。

包括文件增长后的压缩和合并，以及删除旧的文件。

但是实际数据库要处理多种异常情况，如下所示：

1、文件格式

CSV不是最佳的存储合适，使用二进制格式更快

2、删除记录

在键值的后面附加一个删除标记，作为逻辑删除，在日志合并时，可以根据删除标记将无用的日志删除掉

3、崩溃恢复

如果崩溃后，需要读取所有日志文件来恢复，会导致数据库重启时间变得很长，可以在磁盘上存储Hash映射来加快重启速度

4、部分写入记录

数据库可能随时崩溃，比如把一条日志写到磁盘过程中崩溃，可以增加校验和来解决类似问题

5、并发控制

单线程写入，多线程读取

乍一看，append only很浪费，为什么不原地更新文件呢，直接用新值覆盖旧值？原因如下：

1、追加和分段合并是顺序写入，比随机写入性能更好，不论是在HDD还是SSD

2、append only对并发和崩溃恢复简单

3、合并旧数据可以避免数据文件随着时间的推移而分散的问题

Hash索引的局限性：

1、Hash表必须能放进内存

2、范围查询效率不高

在接下来的章节中提到了SSTables和LSM树

排序字符串表（Sorted String Table）简称SSTable

SSTable的优势

1、即使文件大于可用内存，合并段也是简单而高效的，每个键在每个合并段文件中只出现一次，这一点由压缩过程保证。

2、为了在文件中查找一个特定的键，不需要在内存中保存所有键的索引，比如查找键handiwork，但是内存中并没有存储handiwork的索引，只保存了handbag和handsome的索引，由于键已经是排序好的，所以可以确定handiwork在handbag和handsome之间，可以直接从handbag对应的文件偏移位置开始查找。

3、由于读请求无论如何都要扫描请求范围内的多个键值对，因此可以将这些记录分组到块中，并在写入磁盘之前进行压缩。内存中的稀疏索引指向压缩块的起始位置，除了可以节省磁盘空间，还可以减少IO带宽的使用。

 接下来介绍了构建和维护SSTables

由于传入的值可以以任意顺序发生，那如何让数据首先按键排序呢？可以在内存中使用树形结构来排序，比如红黑树或者AVL树。存储引擎工作机制如下：

1、写入时，先写到内存中的树形结构里，比如红黑树，把这个内存树形结构称为内存表（memtable）

2、当memtable大于某个阈值（通常是几MB）时，将其作为SSTable文件写入磁盘，当memtable正在被写入磁盘过程中，新进入的写请求可写到新的memtable中

3、对于读请求，先读memtable，然后再找最新的SSTabe，然后再找旧的SSTable

4、后台不定时的会有合并和压缩的任务来合并SSTable和清理已删除的值

对于上述方案，为了解决写入memtable的信息，在落盘之前数据库崩溃，导致丢失更新的问题，增加Redolog来解决。

性能优化

LSM Tree在查找数据库中不存在的记录时，性能会比较差，因为不仅要检查memtable，还要逐个检查SSTable，直到最老的SSTable，实际应用中为了优化这个问题，通常使用BloomFilter，用于判断某个值是否在数据库中。

LSM Tree可以支持很高的写入吞吐量。

 B树有很多种优化方案，如下所示：

1、一些数据库（如LMDB）使用写时复制方案，而不是覆盖页面并维护WAL进行崩溃恢复。修改的页面被写入到不同的位置，并且树中父页面的新版本被创建，指向新的位置，这种方法对并发控制很有用。

2、为了节省页面空间，可以存储key的缩写形式，在一个页面中存储更多的缩写之后的key，可以让树有更高的分支因子，这样树的高度也会更低。

3、许多B树实现尝试布局树，使得叶子页面按顺序出现在磁盘上，但是随着树的增长，维护这个顺序变得越来越困难，相比之下，由于LSM树在合并过程中一次又一次地重写存储的大部分，所以它们更容易使有序的key在磁盘上距离更近。

4、在树中存储额外的指针，比如，每个叶子页面，可以存储其左右兄弟页面的引用，这样在顺序扫描时，就不需要跳回到父节点。

5、B树的变体，如分形树，借用一些日志结构的思想来减少磁盘寻道。

 LSM树的优点

B树索引必须至少两次写入每一段数据：一次写入预先