参考《DDIA》
如果你把东西整理的井井有条，下次就不用找了。
为什么要关注数据库内部的存储和索引？我们往往需要从众多的存储引擎中选择一个对自己应用来说适合的，针对特定的工作负载而对数据库调优，这需要对存储引擎的底层机制有一个大概的了解。
1. 哈希索引
K-V类型随处可见，是其他复杂索引的基础构造模块，通常使用hash map来实现。
假设数据存储使用append追加模式，那么最简单的策略是：
- 保存内存中的hash map，把每个键一一映射到数据文件中特定的字符偏移量，这样就可以找到每个值的位置。（这就是Bitcask所采用的核心做法）
但，只追加到一个文件中，免不了存储空间极大浪费，最终磁盘耗尽。那么如何避免？
-
一个好的解决方案是，将日志分解成一定大小的段，当文件达到一定的大小时就关闭它，将后续写到新的段文件中。然后在这些段上执行压缩，丢弃重复的旧的键，保留最新的键。
细节之处：
- 文件格式：应采用二进制格式，以字节为单位来记录字符串的长度，以后跟上原始字符串（不需要转义）
- 删除记录：删除键和他关联的值，必须在数据文件中最佳一个特殊的删除记录（墓碑），当合并日志段时，一旦发现墓碑标记，则会丢弃这个已经删除键的所有值。
- 崩溃恢复：数据库重启后，内存中的hash map会丢失。从头到尾读取所有段文件代价过大。Bitcask将每个段的hash map快照存储在磁盘上，方便更快的加载到内存中。
- 部分写入的记录：数据库随时可能崩溃，Bitcask包含校验值功能，这样可以发现损坏部分并丢弃。
- 并发控制：由于写入必须以严格的先后顺序追加到日志中，通常的实现选择是只有一个写线程。数据文件段是追加的，并且是不变的，所以可以被多个线程读。
哈希表索引的局限性：
- 出现了大量的键，磁盘需要大量的随机访问I/O，当哈希变满后，继续增长代价昂贵，并且哈希冲突时需要复杂的处理逻辑。
- 区间查询效率不高，比如查询kitty00000到kitty99999区间内的所有键，只能采用逐个查找的方式。
2. SSTable和LSM-Tree
SSTable即排序字符串表，它要求K-V对的顺序按键排序，每个键在每个合并的段文件中只能出现一次。
相比于哈希索引的日志段，具有以下优点：
- 合并段更加简单高效，即使文件大于可用内存。合并方式类似于归并排序。
- 在文件中查找特定的键时，不再需要在内存中保存所有键的索引。
如何保证数据按键排序？在磁盘上维护排序结构是可行的（B-trees），不过将其保存在内存中更容易。内存排序使用一些树状数据结构，例如红黑树、AVL树。使用这些数据结构，可以按任意顺序插入键并以排序后的顺序读取它们。
基本工作流程：
- 当写入时，将其添加到内存中的平衡树数据结构（内存表）中。
- 当内存大于某个阈值（几兆），将其作为SSTable文件写入磁盘。同时有新数据到来，便写入到一个新的内存表中。
- 为了处理读请求，先在内存表中查找键，然后是最新的磁盘段文件，之后是次新的磁盘段文件，知道找到目标（或为空）。
- 后台进程周期性地执行段合并与压缩过程，以合并多个段文件，并求其那些已被覆盖或删除地键。
- 同时，在磁盘上保留单独地日志，每个写入立即追加到该日志中，该日志不需要排序。方便在数据库崩溃重启后恢复未写入磁盘的数据。
