有两种主要的数据存储及索引结构：LSM-Tree 和 B-Tree。由于索引结构总是针对数据存储结构而设计和优化的，因此两者是紧密关联的，很难分开来讨论。
LSM-Tree
LSM：Log-Structured Merge-Tree。从 AOF 和 SSTable 演变而来。
AOF
- Append-Only File
- 只添加新记录，不修改或删除已有记录；
- 当前写入文件超出一定大小时，创建新的文件再写入；这些文件称为 Segment Files ；
- 需要压缩和合并 Segment Files，让最终的 AOF 文件体积更小；
- 合并完成后，删除旧的 Segment Files，读请求会转发给最新的 AOF 文件；
- Bitcask 模型： 多个不可变 Segment Files + 一个活跃的可写 Segment File；
- 适合 key 比较少，但 value 更新频繁的场景；适合日志文件场景。
索引结构：
- 需要内存中的 HashMap 来索引指定 key 在磁盘文件上的记录；
- HashMap 索引：key 是记录的 key, value 是记录在磁盘文件上的 offset。
实现细节：
- 文件格式：文本文件更可读，二进制文件会更快。通常格式是“checksums + 数据长度+数据内容”；
- 删除记录：丢弃对应 key 的之前记录，能加快合并过程；
- 故障恢复：在磁盘上保持 AOF 的 HashMap 的快照， Bitcask 可以加速恢复速度；
- 部分写入：Bitcask 包含 checksums, 确保部分写入的脏数据被检测到和忽略掉；
- 并发控制：已有文件是不可变的，支持并发读。
优点：
- 顺序写，写磁盘效率更高；
- 并发控制和恢复更简单，无需考虑已有记录被更新成新值。
缺点：
- 不支持范围查找；
- 有大量 keys 时，内存占用过大，而磁盘实现的 HashMap 的性能会很低（随机 IO 太多）。
SSTable
- Sorted String Table
- keys 是有序的；
- 合并时可以采用归并排序；
- 可以将 keys 分组成一个个有序块，压缩后存放在磁盘文件里，支持范围查找。
SSTable 内存索引：
- 依然是 HashMap 结构；
- 只需包含更少 keys , 比如这些 keys 是一组记录 keys 的前缀集合；
- 一个 Segment File 可以只需要一个 key;
- 可以使用红黑树或 B 树；
- 当内存索引过大时，可以写入磁盘文件 SSTable File；
- 查询记录时，先查询内存索引，找到记录所在的文件位置，再取记录；如果在内存索引里找不到，则依次从最近的 SSTable File 里去查找记录的磁盘索引位置。
优化：
- 如果数据写入了内存索引但还没写入磁盘文件 SSTable File，突然发生故障了，就可能导致索引不完整。可以加一个额外日志，每当写内存索引时，也写一条记录在这个日志里。
优点：
- 支持范围查找；
- 由于是顺序写，写吞吐量很高。
LSM-Tree
- LSM-Tree 基于 SSTable 构建并进行了优化；
- 压缩和合并可以采用 size-tiered 或 leveled；
- 使用 BloomFilter 来定位不存在的 keys ，避免在找不到 key 时在磁盘中搜索过多次数；
B-Tree
- 将记录集分割成固定块或页，一次读写一个块或页； LSM-tree 的记录集分割是可变大小的；
- 多重有序表的链接；
优化：
- WAL：Write-ahead Log ，保证 B 树可靠性。避免在 B 树节点分裂发生故障时，B 树会 corrupted ；
- Copy-on-write:
- B+ 树：内节点只存 key ，不存数据，让树的内节点能存储更多的 keys ，减小树的高度，减少磁盘读写次数；
- 叶子页使用链表连接起来，保持有序。
对比
- LSM 写性能更好，而 B-Tree 读性能更好；
- LSM 压缩文件比 B-Tree 体积更小；
- 对于一个 key 来说， LSM 存在多份拷贝，而 B-Tree 只有一份； B-Tree 能更好地支持事务。
参考资料
- 《设计数据密集型应用（影印版）》：第 3 章