第三章：存储与检索
1. 存储与检索的核心问题
数据库底层目标可以归结为两件事：
- 写入路径：如何高效、可靠地把数据落到持久化介质。
- 读取路径：如何在可控延迟内找到目标数据。
索引是两者之间的典型权衡：加速读，增加写放大与存储开销。
2. 基础存储结构
2.1 追加日志与哈希索引
最简单的 KV 存储是追加日志：写入顺序追加，读取反向扫描。为避免 O(n) 读取，需要内存哈希表维护 key -> offset。
该模型写入快，但有两个明显限制：
- 所有键通常要常驻内存。
- 范围查询能力弱。
2.2 SSTable 与 LSM-Tree
SSTable 要求键有序。LSM-Tree 一般由 MemTable、磁盘层级文件、后台压缩组成：
- 写入先到内存有序结构，再顺序刷盘。
- 读取按新到旧查找多个层级。
- 后台
compaction合并并清理旧版本。
关键配套：
WAL：崩溃恢复。Bloom Filter：快速判定“键不存在”，减少无效磁盘查找。
2.3 B-Tree 及其变体
B-Tree/B+Tree 以页为单位组织数据，读写路径短、范围查询稳定，是关系数据库主流索引结构。
典型特征：
- 更新常为随机写，需配合
WAL保证崩溃一致性。 - 页分裂与合并维护树平衡。
- 并发依赖锁存器与多版本机制。
2.4 LSM-Tree 与 B-Tree 对比
| 维度 | LSM-Tree | B-Tree |
|---|---|---|
| 写入吞吐 | 高，顺序写友好 | 中等，随机写较多 |
| 读取放大 | 可能查多层文件 | 路径稳定，点查快 |
| 范围查询 | 可做，但常弱于 B+Tree | 强项 |
| 空间与压缩 | 压缩效果通常更好 | 依赖页利用率 |
| 延迟稳定性 | 压缩期可能抖动 | 相对平稳 |
3. 索引设计
3.1 主键索引与二级索引
- 主键索引决定数据主存放路径。
- 二级索引用于非主键条件检索，但会引入额外写放大与一致性维护成本。
3.2 聚簇、覆盖与多列索引
- 聚簇索引：数据行与索引叶子同址，主键查找高效。
- 覆盖索引：索引包含查询所需列，减少回表。
- 多列索引：遵循最左匹配与查询模式设计，不可盲目叠加。
3.3 全文与模糊检索
全文搜索通常使用倒排索引，核心优化点是分词、倒排压缩和相关性排序。若查询以文本相关性为主，建议由专用搜索引擎承担。
4. OLTP 与 OLAP
4.1 两类负载差异
OLTP：高并发、小事务、低延迟、点查为主。OLAP：大扫描、聚合计算、吞吐优先。
同一存储结构很难同时对两类负载最优，这也是数据仓库与湖仓体系出现的根本原因。
4.2 数据仓库与建模
ETL/ELT 将业务库数据汇总到分析系统，常见模型：
- 星型模型：事实表 + 维度表，结构清晰，查询友好。
- 雪花模型：维度进一步规范化，存储节省但查询更复杂。
5. 列式存储
5.1 为分析而生
分析查询通常只访问少量列，列式存储可显著降低 I/O。列内数据同质，天然适合压缩与向量化执行。
5.2 列压缩与向量化
常见技术包括字典编码、位图、游程编码。配合 SIMD 指令，CPU 可一次处理多条数据，提高扫描效率。
5.3 列存写入策略
列存更新成本高，工程上常采用“增量写入 + 后台合并”，本质上与 LSM 思路一致。复杂聚合可通过物化视图预计算换取查询时延。
6. 实务建议
- 先根据查询模式选引擎，再做索引设计。
- 高写入日志类场景优先评估
LSM-Tree。 - 高并发事务与范围查询优先评估
B+Tree。 - 分析链路优先列存与声明式计算引擎。