🗄️ 本章核心：存储引擎不存在绝对最优，设计始终是在读放大、写放大、空间放大、持久性与查询模式之间取舍。
一、知识主线
追加日志 → 哈希索引 → SSTable → MemTable + WAL → LSM-Tree → B-Tree → 二级索引 → OLTP/OLAP → 行存储/列存储 → 内存数据库
二、追加日志与哈希索引
- 追加写：更新时不覆盖旧记录，而是在日志末尾写入新版本。
- 读取规则：同一个键以最新记录为准。
- 哈希索引：在内存中保存
key → 文件段、偏移量、长度，直接定位最新值。 - 日志分段：当前段接收写入，旧段冻结为只读，便于后台整理。
- 墓碑记录：删除操作写入 tombstone，防止旧值在查询或合并后复活。
- 恢复：内存索引丢失时，可以按时间顺序扫描日志重建；实际系统还会使用校验和识别末尾的不完整记录。
适用与限制
- 适合完整键的点查询。
- 不擅长范围查询，因为哈希表不维护键顺序。
- 内存索引大小取决于不同键的数量，磁盘日志大小取决于历史写入次数。
三、SSTable 与 LSM-Tree
核心组件
| 组件 | 位置与状态 | 作用 |
| WAL | 磁盘上的追加日志 | 恢复尚未进入 SSTable 的已确认写入 |
| 当前 MemTable | 内存、可修改、有序 | 接收新写入并服务近期查询 |
| 不可变 MemTable | 内存、已冻结 | 等待或正在写成 SSTable |
| SSTable | 磁盘、不可变、有序 | 长期保存数据并支持点查询和范围查询 |
| Bloom Filter | 概率型辅助结构 | 快速判断某个 SSTable 一定不包含目标键 |
| Compaction | 后台过程 | 合并 SSTable，清理旧版本与墓碑 |
写入路径
- 写入先追加到 WAL，并在需要持久性保证时可靠落盘。
- 同一次写入更新当前 MemTable。
- MemTable 达到阈值后冻结，同时创建新的 MemTable 继续接收写入。
- 不可变 MemTable 被顺序写成新的 SSTable。
- 多个 SSTable 在后台执行 Compaction。
查询路径
- 当前 MemTable。
- 尚未落盘的不可变 MemTable。
- 从新到旧查询 SSTable。
- Bloom Filter 跳过一定不包含目标键的文件。
- 遇到第一条值或墓碑，即得到最新状态。
什么时候生成新的 SSTable
- MemTable 达到大小阈值、时间阈值或内存压力阈值时。
- WAL 积累过多，系统需要推进刷盘时。
- 数据库关闭或手动执行刷新时。
- Compaction 合并旧 SSTable 时；输出过大时可能按键范围拆成多个新文件。
SSTable 写成后不再修改。更新先进入 MemTable，随后生成新 SSTable，旧版本最终由 Compaction 清理。
Compaction 策略
- Size-tiered：相近大小的 SSTable 合并，通常降低写入压力，但文件和旧版本可能更多。
- Leveled：按层级和键范围组织 SSTable，通常降低读放大和空间放大，但可能提高写放大。
四、三种放大
- 写放大：用户写入一份数据，WAL、刷盘和多轮 Compaction 导致磁盘实际写入多份。
- 读放大：一次查询需要检查多个内存结构或 SSTable。
- 空间放大：同一个键的多个历史版本暂时同时占用空间。
更频繁的 Compaction 通常降低读放大和空间放大，但提高写放大；降低 Compaction 强度则相反。
五、B-Tree
- 把数据组织成固定大小的页，通过根页、中间页和叶子页逐层缩小查询范围。
- 更新通常找到目标页并维护现有树结构。
- 插入导致页面超过容量时，会发生页分裂并更新父页。
- 与页修改对应的 WAL 必须先于修改后的数据页持久化，确保崩溃后可以重做或撤销未完整完成的修改。
B-Tree 与 LSM-Tree
| 维度 | B-Tree | LSM-Tree |
| 基本思路 | 持续维护一棵现有的树 | 产生新结构，再后台合并 |
| 磁盘结构 | 固定大小的可更新页 | 多个不可变 SSTable |
| 写入特点 | 可能涉及随机页写入 | 将大量写入转为顺序写 |
| 后台工作 | 页分裂、页合并 | Compaction |
| 读取 | 通常沿树定位一次 | 可能检查多代文件 |
六、索引
- 主键索引：根据唯一主键定位记录。
- 二级索引：根据非主键字段定位一条或多条记录。
- 堆文件：索引叶子保存数据位置，完整数据行存放在独立区域。
- 聚簇索引：数据行本身按照某个索引的顺序组织，通常只能有一种主要聚簇顺序。
- 覆盖索引：索引包含查询需要的全部字段，可以避免回表。
- 多列索引：例如
(country, city, created_at)，最适合从左侧连续使用索引列；跳过中间列时，后续列通常不能形成高效的连续范围。 - 多维索引：R-Tree 等结构适合地理空间和多个维度同时做范围查询。
- 全文索引：倒排索引适合按词语查询文档。
索引越多，读取通常越快，但写入、空间和维护成本也越高。
七、OLTP 与 OLAP
| 维度 | OLTP | OLAP |
| 访问范围 | 少量记录 | 大量历史记录 |
| 常见操作 | 点查询、插入、更新 | 扫描、分组、聚合 |
| 延迟要求 | 通常很高 | 可以接受更长执行时间 |
| 主要视角 | 当前业务状态 | 历史趋势和整体分析 |
- 为避免大规模分析影响在线业务，数据通常通过 ETL 或 ELT 从业务数据库进入数据仓库。
- 数据仓库常采用星型模型：事件及可聚合指标放在事实表，品牌、地区、时间等描述性信息放在维度表。
八、行存储与列存储
- 行存储：同一行的字段放在一起，适合根据主键读取或修改完整记录，常用于 OLTP。
- 列存储：同一列的值连续保存，分析时只读取需要的列，常用于 OLAP。
- 同列数据类型一致且重复值多，便于字典编码、游程编码等压缩。
- 合理的排序顺序能提升压缩效果，并让查询跳过无关数据范围。
- 向量化执行成批处理同类值，更好地利用 CPU 缓存与 SIMD。
- 物化视图预先保存常用聚合结果，以增加写入和维护成本换取查询速度。
九、内存数据库
- 主要数据结构常驻内存，但仍可使用 WAL、快照和复制实现恢复与高可用。
- 快照之间若没有日志，崩溃后可能丢失快照之后的写入。
- 复制主要应对机器故障，备份还要应对误删除、程序错误和数据损坏，二者不能互相替代。
十、选型速查
- 低延迟点查询、频繁更新少量完整记录：倾向 B-Tree + 行存储。
- 写入量极大、可以接受后台整理：倾向 LSM-Tree。
- 大规模扫描少数列并聚合：倾向 列存储 OLAP。
- 高写入设备事件系统：可采用 LSM-Tree，并用
(device_id, timestamp)作为有序键，支持按设备和时间范围查询。 - 数据规模可放入内存且延迟极敏感：考虑内存数据库，同时设计日志、快照、复制与备份。
十一、易错点
- 追加写不会自动解决并发冲突；并发仍需要锁、版本或事务机制。
- Bloom Filter 的“可能存在”可能是假阳性，仍需查数据；“一定不存在”则可以安全跳过。
- WAL 负责恢复尚未写成 SSTable 的近期数据；SSTable 保存已经落盘的数据。
- 新 SSTable 中没有目标键，只说明需要继续查旧文件；从新到旧查询的真正原因是新值或墓碑会覆盖旧值。
- 销售金额放入事实表，是因为它是可聚合的事件指标，而不是因为它永远不会变化。
整理日期：2026-09-10。内容基于《Designing Data-Intensive Applications》第三章的学习与问答总结。