【读书笔记】设计数据密集型应用 DDIA 第三章：存储与检索

1. 章节介绍

本章聚焦数据库的核心功能：存储与检索数据。从数据库内部视角，探讨了不同存储引擎的工作原理、索引结构及适用场景，帮助读者理解如何为特定应用场景选择合适的存储引擎。同时，本章还区分了事务处理（OLTP）与分析处理（OLAP）的差异，介绍了数据仓库的概念及列存储等专为分析优化的存储方式。

核心知识点	面试频率
索引的概念与作用	高
哈希索引	中
SSTables与LSM树	高
B树索引	高
B树与LSM树的比较	高
OLTP与OLAP的区别	中
列存储	中
数据仓库与星型模式	低

2. 知识点详解

2.1 索引的概念与作用

• 索引是从主数据衍生的附加结构，用于加快数据查询速度
• 索引通过保存额外的元数据作为"路标"，帮助快速定位所需数据
• 索引是一把双刃剑：
  • 加速读查询
  • 减慢写操作（每次写入需更新索引）
• 数据库默认不会索引所有内容，需要根据查询模式手动选择索引

2.2 哈希索引

• 基于哈希表实现的索引结构
• 工作原理：
  • 内存中维护哈希映射，键映射到数据文件中的字节偏移量
  • 写入时追加到日志文件并更新哈希映射
  • 读取时通过哈希映射找到偏移量，直接读取数据
• 代表实现：Bitcask（Riak的默认存储引擎）
• 优点：
  • 读写性能高
  • 适合键经常更新的场景
• 缺点：
  • 所有键必须能放入内存
  • 不适合范围查询（O(n)复杂度）
• 解决磁盘空间问题：
  • 将日志分为固定大小的段
  • 后台进行段压缩，只保留每个键的最新值
  • 合并多个段以减少数量

2.3 SSTables与LSM树

2.3.1 SSTables（排序字符串表）

• 特点：段文件中的键值对按键排序，每个键在合并后的段中只出现一次
• 优势：
  • 合并段简单高效（类似归并排序）
  • 内存索引可以更稀疏，节省内存
  • 可将记录分组压缩，减少IO
• 构建与维护：
  • 写入时先添加到内存中的平衡树（如红黑树），称为memtable
  • 当memtable达到阈值，将其作为SSTable写入磁盘
  • 读取时先检查memtable，再检查磁盘上的SSTable段

2.3.2 LSM树（日志结构合并树）

• 基于合并和压缩排序文件原理的存储引擎
• 核心思想：维护一系列SSTable，后台定期合并
• 代表实现：LevelDB、RocksDB、Cassandra、HBase
• 优化技术：
  • Bloom过滤器：减少不存在键的查询开销
  • 压缩策略：
    • 大小分层压缩：新的小SSTable合并到旧的大SSTable
    • 水平压缩：将键范围拆分为更小的SSTable

2.4 B树索引

• 最广泛使用的索引结构，几乎所有关系数据库的标准索引实现
• 结构特点：
  • 将数据库分解为固定大小的块（页面），通常4KB
  • 页面之间通过地址引用，形成树状结构
  • 根页面包含键和对子页面的引用，每个子页面负责一段连续范围的键
• 操作特性：
  • 查找复杂度为O(log n)
  • 更新时只需修改相关页面
  • 页面分裂机制保证树的平衡性
• 保证可靠性的机制：
  • 预写式日志（WAL）：记录所有修改，崩溃后用于恢复
  • 并发控制：使用锁保护树结构

2.5 B树与LSM树的比较

2.5.1 LSM树的优点

• 写入性能通常更高
  • 顺序写入紧凑的SSTable文件
  • 写放大可能更低
• 压缩更好，磁盘空间利用率更高
• 适合写入密集型应用

2.5.2 B树的优点

• 读取性能通常更稳定
• 每个键只存在于索引中的一个位置
• 事务支持更好，适合实现锁机制
• 查询响应时间更可预测

2.5.3 实际考虑因素

• 工作负载特性决定选择
• LSM树在写入密集型应用中表现更好
• B树在读取密集型应用中更有优势
• 压缩对SSD寿命很重要，LSM树通常更有优势

2.6 其他索引结构

2.6.1 二级索引

• 基于键值索引构建，但键不唯一
• 实现方式：
  • 索引值为匹配行标识符的列表
  • 向每个索引项添加行标识符使键唯一
• 可使用B树或日志结构索引作为二级索引

2.6.2 聚簇索引与非聚簇索引

• 聚簇索引：索引中存储实际行数据
• 非聚簇索引：索引中存储指向实际数据的引用
• 覆盖索引：索引中存储查询所需的部分或全部数据，可直接回答查询

2.6.3 多列索引

• 连接索引：将多列值组合成一个键
• 多维索引：适合同时查询多个列，如地理空间数据
• 全文搜索索引：支持模糊查询和文本分析

2.7 OLTP与OLAP的区别

2.7.1 OLTP（在线事务处理）

• 主要特点：
  • 处理用户交互产生的事务
  • 查询少量记录，按键读取
  • 随机访问，写入要求低延迟
  • 关注数据的最新状态
  • 数据集规模通常为GB到TB级

2.7.2 OLAP（在线分析处理）

• 主要特点：
  • 支持业务分析和决策支持
  • 在大批量记录上进行聚合操作
  • 批量导入，事件流写入
  • 处理历史数据
  • 数据集规模通常为TB到PB级

2.8 列存储

• 与行存储的区别：将来自每一列的所有值存储在一起，而非一行的所有值
• 优势：
  • 只读取查询所需的列，减少IO
  • 列数据通常重复度高，压缩效率高
  • 适合分析查询（通常只访问少数列）
• 压缩技术：
  • 位图编码：适合不同值数量少的列
  • 游程编码：适合连续重复值
• 排序顺序：
  • 整行排序，而非单列排序
  • 可根据常见查询模式选择排序键
  • 可维护多个排序版本以优化不同查询

2.9 数据仓库与星型模式

• 数据仓库：独立的分析数据库，不影响OLTP系统性能
• ETL过程：从OLTP系统提取数据，转换为适合分析的模式，加载到数据仓库
• 星型模式：
  • 中心是事实表，存储事件数据
  • 周围是维度表，描述事件的上下文（时间、地点、产品等）
  • 事实表通常很大，维度表相对较小
• 雪花模式：星型模式的变体，维度被进一步分解为子维度

3. 章节总结

本章深入探讨了数据库存储与检索的核心原理，重点介绍了两类主流存储引擎：基于B树的存储引擎和基于LSM树的日志结构存储引擎。通过对比分析，阐述了它们在读写性能、适用场景等方面的差异。

索引是提高查询性能的关键，本章介绍了哈希索引、B树索引、LSM树等多种索引结构及其适用场景。同时，本章还区分了OLTP和OLAP两种数据处理模式的差异，介绍了列存储等专为分析优化的存储方式。

理解这些底层原理有助于开发者为特定应用场景选择合适的数据库和存储引擎，优化查询性能，并在面对数据库设计决策时做出更明智的选择。

4. 知识点补充

4.1 补充知识点

1. 索引选择性：指索引中不同值的数量与表中记录数的比值。选择性越高，索引效果越好。例如，性别列选择性低（只有2个值），不适合建索引；而用户ID列选择性高，适合建索引。

2. 索引覆盖查询：如果查询所需的所有列都包含在索引中，则不需要访问主表数据，这种查询称为索引覆盖查询，性能极高。

3. 索引合并：当查询条件涉及多个索引时，数据库可能会合并多个索引的结果，而不是仅使用一个索引。

4. 数据库分区：将大表分成 smaller 部分，每个部分可以独立管理和查询。常见的分区策略有范围分区、列表分区和哈希分区。

5. MVCC（多版本并发控制）：许多数据库使用的并发控制方法，通过维护数据的多个版本，实现读写不冲突，提高并发性能。

4.2 最佳实践：如何为应用选择合适的存储引擎

选择合适的存储引擎需要综合考虑应用的访问模式、性能需求和数据特性。以下是一些实用指南：

1. 分析应用的读写比例：如果是写入密集型应用（如日志收集、实时数据处理），LSM树为基础的存储引擎（如Cassandra、RocksDB）通常表现更好，因为它们的写入性能更高，并且能更好地处理顺序写入。

2. 考虑查询模式：如果应用主要进行点查询（通过主键查找），哈希索引或B树都能胜任；如果需要频繁进行范围查询，B树或LSM树更合适；如果需要复杂的多条件查询，B树索引通常更有优势。

3. 评估数据规模和增长趋势：对于小规模数据，几乎任何存储引擎都能胜任；对于大规模数据，需要考虑存储引擎的水平扩展能力和压缩效率。LSM树通常在压缩效率上更有优势，适合大规模数据存储。

4. 考虑硬件环境：在传统机械硬盘上，顺序写入性能远高于随机写入，LSM树的优势更明显；在SSD上，随机写入性能提升，B树和LSM树的差距缩小，但LSM树通常仍有写入放大优势。

5. 评估事务需求：如果应用需要强事务支持和ACID特性，基于B树的传统关系型数据库通常是更好的选择；如果可以接受最终一致性，某些基于LSM树的数据库（如Cassandra）提供更好的扩展性。

6. 原型验证：在做出最终决定前，使用实际数据和查询模式进行原型测试，测量不同存储引擎的性能表现。例如，对于电商平台的商品详情页，可能需要测试MySQL（B树）和RocksDB在相同查询模式下的响应时间和吞吐量。

4.3 编程思想指导：数据库设计中的权衡思维

在数据库设计和存储引擎选择中，权衡思维至关重要。以下是一些关键的权衡点及思考方式：

1. 读写权衡：几乎所有的数据库优化都涉及读写性能的权衡。索引提高读性能但降低写性能；缓存改善读性能但增加内存使用。作为开发者，需要根据应用的具体读写比例做出决策。例如，对于社交媒体的消息系统，写入频繁且读取更频繁，适当增加索引和缓存是合理的；而对于日志系统，写入远多于读取，应尽量减少索引开销。

2. 空间与时间权衡：数据库中的许多优化通过消耗更多存储空间来换取更快的查询速度。例如，物化视图预先计算并存储聚合结果，加速查询但占用更多空间。在做这种决策时，需要考虑存储成本与查询延迟的相对重要性。对于需要毫秒级响应的交易系统，额外的存储空间通常是值得的；而对于批处理分析系统，可能更愿意牺牲一些时间来节省存储空间。

3. 一致性与可用性权衡：在分布式数据库中，CAP定理表明不可能同时实现一致性、可用性和分区容错性。根据应用需求选择合适的平衡点：金融交易系统通常需要强一致性；社交网络应用可能更看重可用性，接受最终一致性。

4. 简单性与功能性权衡：选择数据库时，不应盲目追求功能丰富性而牺牲简单性。许多场景下，简单的键值存储比复杂的关系型数据库更合适，能提供更好的性能和可维护性。例如，用户会话存储使用Redis比MySQL更简单高效。

5. 短期需求与长期演进：数据库选择不仅要满足当前需求，还要考虑未来的演进。一个为小规模数据设计的系统可能在数据量增长100倍后变得难以维护。在设计初期就应考虑水平扩展能力、数据归档策略等长期因素。

培养这种权衡思维需要经验积累和持续学习。建议通过实际项目实践，观察不同设计决策的长期影响，并深入理解数据库内部原理，这样才能在面对复杂需求时做出合理的技术选择。

5. 程序员面试题

5.1 简单题：什么是索引？索引有什么优缺点？

答案：
索引是数据库中用于加快数据查询速度的附加数据结构，它通过保存额外的元数据作为"路标"，帮助快速定位所需数据。

优点：

• 显著提高查询速度，尤其是在大型数据表上
• 加速表连接操作
• 可以加速排序和分组操作

缺点：

• 增加存储空间开销
• 减慢写入操作（INSERT、UPDATE、DELETE），因为每次写入都需要更新索引
• 索引需要维护，增加了数据库管理的复杂性

5.2 中等难度题：B树和LSM树各有什么特点？分别适用于什么场景？

答案：
B树特点：

• 采用树状结构，将数据组织在固定大小的页面中
• 每个节点包含键和子节点引用，保证查找复杂度为O(log n)
• 支持原地更新，每次修改只需更新相关页面
• 读取性能稳定，每次查询的IO次数可预测

LSM树特点：

• 基于日志结构，数据首先写入内存，然后批量写入磁盘
• 由多个排序的段文件组成，后台进行合并和压缩
• 写入性能高，尤其是顺序写入
• 读取可能需要检查多个段，性能变化较大

适用场景：

• B树适用于：

  • 读取密集型应用
  • 需要强事务支持的场景
  • 对查询响应时间有严格要求的应用
  • 例如：银行交易系统、电子商务订单管理

• LSM树适用于：

  • 写入密集型应用
  • 可以接受一定读取延迟的场景
  • 需要高压缩率的大规模数据存储
  • 例如：日志收集系统、实时分析平台、物联网数据存储

5.3 中等难度题：什么是OLTP和OLAP？它们在数据存储和访问模式上有什么区别？

答案：
OLTP（在线事务处理）是指支持日常业务交易的数据库系统，如电商网站的订单处理、银行的转账操作等。

OLAP（在线分析处理）是指支持业务分析和决策支持的数据库系统，如销售报表生成、市场趋势分析等。

数据存储和访问模式的区别：

1. 数据存储：

   • OLTP：存储最新的、详细的业务数据，通常采用规范化设计减少冗余
   • OLAP：存储历史数据和汇总数据，通常采用星型或雪花型模式，允许一定的数据冗余

2. 访问模式：

   • OLTP：

     • 主要进行点查询和小范围查询
     • 读写比例相对均衡，写入操作频繁
     • 每次操作涉及的数据量小
     • 响应时间要求高（通常毫秒级）

   • OLAP：

     • 主要进行大范围查询和聚合分析
     • 以读取操作为主，写入通常是批量导入
     • 每次操作可能涉及数百万甚至数十亿条记录
     • 响应时间要求相对宽松（通常秒级或分钟级）

3. 数据规模：

   • OLTP：通常为GB到TB级
   • OLAP：通常为TB到PB级

5.4 高难度题：请详细比较B树和LSM树在写入过程中的性能差异及原因

答案：
B树和LSM树在写入性能上有显著差异，主要体现在以下方面：

1. 写入路径：

   • B树：每次写入需要找到对应的叶子节点，可能需要多次磁盘寻道；如果页面已满，需要分裂页面并更新父节点，这可能引发连锁反应，导致多次磁盘写入。
   • LSM树：写入首先追加到内存中的memtable，这是一个内存操作，速度极快；当memtable达到阈值，以顺序方式写入磁盘形成新的SSTable段，避免了随机写入。

2. 写放大：

   • B树：写放大较高，原因包括：

     • 即使只修改一个键，也可能需要写入整个页面
     • 页面分裂可能导致多个页面被重写
     • 预写日志(WAL)增加了额外写入

   • LSM树：写放大通常较低，原因是：

     • 写入主要是顺序操作
     • 合并过程批量处理多个更新
     • 可以配置压缩策略以平衡写入放大和读取性能

3. 并发写入：

   • B树：需要复杂的锁机制来保证一致性，可能导致写入竞争
   • LSM树：由于写入首先进入内存，且段文件是不可变的，并发控制更简单，通常支持更高的写入并发

4. 性能表现：

   • 对于随机写入：LSM树通常比B树快10倍以上，因为避免了磁盘寻道
   • 对于顺序写入：两者性能差距缩小，但LSM树仍有优势
   • 对于小批量写入：LSM树优势明显，因为内存写入成本低
   • 对于大批量写入：LSM树的批量合并机制更高效

这些差异使得LSM树在写入密集型应用中表现更出色，而B树在需要稳定读取性能和强事务支持的场景中更有优势。

5.5 高难度题：列存储相比行存储有什么优势？为什么列存储更适合数据仓库和分析场景？

答案：
列存储是一种将表中同一列的数据存储在一起的存储方式，相比传统的行存储有以下优势：

1. 减少IO开销：分析查询通常只需要访问表中的少数几列，列存储可以只读取所需列，大大减少了IO操作。例如，一个包含100列的表，查询只需要其中5列，列存储只需读取5%的数据，而行存储需要读取100%的数据。

2. 更高的压缩率：同一列的数据通常具有相似性，压缩效率更高。例如，性别列只有"男"和"女"两个值，可以高效压缩；而行存储中每行数据差异大，压缩率低。

3. 更好的缓存利用率：由于同一列的数据连续存储，缓存可以加载更多相关数据，提高缓存命中率。

4. 高效的聚合操作：分析查询经常需要对列进行聚合（如求和、平均值），列存储可以直接在压缩数据上进行操作，减少解压和内存占用。

列存储更适合数据仓库和分析场景的原因：

1. 分析查询模式匹配：数据仓库查询通常只访问少数列但需要扫描大量行，列存储的IO优势能得到充分发挥。

2. 数据特性匹配：数据仓库中的数据通常是历史数据，更新少，适合列存储的优化方式；同时，分析场景对写入性能要求低，可接受批量写入。

3. 计算效率：列存储可以更好地利用现代CPU的向量处理能力，对列数据进行批量处理，提高聚合计算效率。

4. 存储效率：数据仓库数据量大（通常为TB到PB级），列存储的高压缩率可以显著降低存储成本。

例如，在电商数据分析中，计算不同地区的销售额只需访问"地区"和"销售额"两列，列存储可以高效完成这一查询，而行存储需要读取包含所有列的大量记录，效率低得多。