第三章 存储与检索 - 数据库内部如何工作

导读

当我们执行一条 SELECT * FROM users WHERE email = 'alice@example.com' 时，数据库内部发生了什么？数据是如何存储在磁盘上的？为什么有些查询很快，有些查询很慢？索引是如何加速查询的？

本章将深入数据库的内部实现，揭示存储引擎（Storage Engine）的工作原理。我们将探讨两种核心的存储引擎设计：面向日志的存储（Log-Structured）和面向页面的存储（Page-Oriented），以及它们各自适用的场景。

理解存储引擎的工作原理，对于选择合适的数据库、设计高效的索引策略、诊断性能问题至关重要。这些知识将帮助你从"会用数据库"进阶到"用好数据库"。

核心概念详解

3.1 数据结构基础

在深入存储引擎之前，我们需要回顾几种关键的数据结构，它们是数据库内部实现的基础。

3.1.1 哈希索引（Hash Index）

最简单的索引结构是哈希索引。其核心思想是：维护一个内存中的哈希表，键是数据的键（如 user_id），值是数据在磁盘文件中的偏移量（offset）。

当需要查找一条记录时：

在哈希表中查找键对应的偏移量。

直接跳转到磁盘文件的对应位置读取数据。

哈希索引的优势是O(1) 的查找时间，前提是哈希表完全在内存中。Bitcask（Riak 数据库的默认存储引擎）就是基于哈希索引的实现。

哈希索引的局限：

• 内存限制：哈希表必须完全在内存中，不适合键数量巨大的场景。
• 范围查询低效：哈希表不支持范围查询（如 WHERE age > 20 AND age < 30），因为哈希函数会打乱键的顺序。
• 冲突处理：哈希冲突会降低性能，虽然可以通过良好的哈希函数缓解。

3.1.2 SSTable 与 LSM-Tree

SSTable（Sorted String Table）是面向日志存储引擎的核心数据结构。它的定义很简单：一个有序的、不可变的键值对集合。

SSTable 的关键特性：

• 键有序：键按排序顺序存储，支持高效的范围查询。
• 不可变（Immutable）：一旦写入，就不能修改。新的数据写入新的文件。
• 稀疏索引：内存中只保存部分键的索引（如每隔 N 个键保存一个），因为键是有序的，可以通过二分查找定位。

基于 SSTable 的写入流程（LSM-Tree 的核心思想）：

内存表（MemTable）：新的写入先进入内存中的有序数据结构（通常是红黑树或跳表）。

刷盘（Flush）：当内存表达到一定大小（如 64MB），将其写入磁盘，生成一个新的 SSTable 文件。这个过程不需要排序（因为内存表已经有序），也不需要修改已有文件（因为是追加写入）。

合并（Compaction）：后台线程定期合并多个 SSTable 文件。由于每个 SSTable 内部都是有序的，合并过程类似于归并排序。合并时会去除重复键（保留最新版本）和删除标记。

LSM-Tree（Log-Structured Merge-Tree）就是基于上述思想的存储引擎。它的优势：

• 写入性能极高：所有写入都是顺序追加，没有随机写入。
• 支持高写入吞吐量：适合写密集型应用。
• 压缩效率高：SSTable 的有序性使得压缩算法可以高效工作。

LSM-Tree 的劣势：

• 读取性能不稳定：读取时可能需要查找多个 SSTable，且需要等待 Compaction 完成。
• Compaction 开销：后台合并会消耗 CPU 和磁盘 I/O，可能影响前台请求。
• 空间放大：多个 SSTable 中可能存在同一键的多个版本，占用额外空间。

典型的 LSM-Tree 实现包括：LevelDB、RocksDB、Cassandra、HBase、BigTable。

3.1.3 B-Tree

B-Tree（Balanced Tree）是最经典的数据库索引结构，也是关系型数据库的默认存储引擎。

B-Tree 的核心思想：

• 将数据组织成一棵平衡的多叉树。
• 每个节点包含多个键和子节点指针。
• 所有叶子节点在同一层，保证查找路径长度一致。
• 节点大小通常等于磁盘页大小（如 4KB 或 16KB），一次 I/O 操作读取一个节点。

B-Tree 的写入流程：

从根节点开始，沿着树向下查找目标键的位置。

如果目标叶子节点已满（达到节点大小上限），需要将节点分裂（Split）成两个节点，并向上层添加一个新的键。

节点分裂可能向上传播，极端情况下导致树的高度增加。

B-Tree 的优势：

• 读取性能稳定：每次查找都需要从根到叶的路径，时间复杂度 O(log N)，且路径长度可预测。
• 原地更新（In-Place Update）：可以直接覆盖旧值，不需要像 LSM-Tree 那样保留多个版本。
• 空间效率高：每个键只存储一次，没有空间放大问题。

B-Tree 的劣势：

• 写入需要随机 I/O：更新一个键值需要找到对应的节点并修改，这通常涉及随机磁盘写入。
• 写入放大：节点分裂时需要写入多个新节点。
• 并发控制复杂：多个事务同时修改同一棵树需要复杂的锁机制。

3.2 存储引擎的两种范式

3.2.1 面向日志的存储（Log-Structured）

"日志"在这里不是指应用日志（log messages），而是指追加写入（append-only）的存储策略。

核心思想：所有写入操作（插入、更新、删除）都被转化为对新数据的追加写入。旧数据不会被修改或删除，而是通过标记（tombstone）表示已删除，在后续的 Compaction 过程中清理。

这种设计的哲学是：顺序写入比随机写入快得多。

现代磁盘的顺序写入速度：

• HDD：约 100-200 MB/s
• SSD：约 500-3000 MB/s

而随机写入速度：

• HDD：约 0.1-1 MB/s（受限于磁头寻道时间）
• SSD：约 10-100 MB/s（受限于擦除和写入放大）

可以看到，顺序写入比随机写入快 10-1000 倍。面向日志的存储引擎充分利用了这一硬件特性。

面向日志存储的代表：

• LevelDB / RocksDB：Google 和 Facebook 开源的嵌入式 KV 存储引擎。
• Cassandra / HBase：分布式宽列存储，使用 LSM-Tree。
• Kafka：分布式消息队列，本质上是一个面向日志的存储系统。

3.2.2 面向页面的存储（Page-Oriented）

B-Tree 是面向页面存储的典型代表。数据被组织成固定大小的页面（Page），每个页面对应一次磁盘 I/O。

核心思想：通过树形索引结构，将随机读取转化为可预测的 I/O 模式（从根到叶的路径），同时支持高效的就地更新。

面向页面存储的代表：

• PostgreSQL：使用 8KB 的页面大小。
• MySQL (InnoDB)：使用 16KB 的页面大小。
• Oracle：使用可配置的块大小（通常 8KB）。
• SQLite：使用可配置的页面大小（默认 4KB）。

3.3 辅助索引与聚簇索引

3.3.1 辅助索引（Secondary Index）

除了主键索引之外，数据库通常支持创建辅助索引来加速非主键列的查询。

辅助索引的实现方式因存储引擎而异：

在 B-Tree 存储引擎中：

• 辅助索引也是一棵 B-Tree，键是索引列的值，值是主键。
• 查询过程：先在辅助索引中找到主键，再在主键索引中找到完整记录。这需要两次索引查找，称为回表（Bookmark Lookup / Table Access by Index Rowid）。

在 LSM-Tree 存储引擎中：

• 辅助索引通常是一个额外的有序文件，键是（索引列值，主键），值是空或附加信息。
• 查询过程：先在辅助索引中找到主键，再在主数据中查找完整记录。

3.3.2 聚簇索引（Clustered Index）

聚簇索引是一种特殊的索引，它将索引和数据存储在一起。在聚簇索引中，表的物理存储顺序与索引顺序一致。

MySQL InnoDB 的聚簇索引：

• 主键索引就是聚簇索引，数据按主键顺序物理存储。
• 辅助索引的叶子节点存储的是主键值，而不是行指针。
• 这意味着通过辅助索引查询需要两次 B-Tree 查找：一次在辅助索引中找主键，一次在聚簇索引中找数据。

聚簇索引的优势：

• 按主键范围查询时，数据物理上连续存储，减少磁盘 I/O。
• 不需要额外的回表操作（对于主键查询）。

聚簇索引的劣势：

• 插入顺序如果不是按主键顺序，会导致频繁的页面分裂和随机 I/O。
• 只能有一个聚簇索引（因为数据只能有一种物理存储顺序）。
• 辅助索引需要额外的回表操作。

3.3.3 覆盖索引（Covering Index）

如果一个索引包含了查询所需的所有列，数据库可以直接从索引返回结果，无需回表查询原始数据。这就是覆盖索引。

例如，如果有一个索引 (last_name, first_name)，查询 SELECT last_name, first_name FROM users WHERE last_name = 'Smith' 可以直接从索引返回结果，因为索引中已经包含了 last_name 和 first_name。

覆盖索引可以显著减少 I/O 操作，是性能优化的重要手段。

3.4 全文索引与倒排索引

3.4.1 倒排索引（Inverted Index）

全文搜索需要一种特殊的索引结构——倒排索引（Inverted Index）。

倒排索引的核心思想：

• 将文本拆分为词条（Term）（经过分词、小写化、去停用词等处理）。
• 为每个词条维护一个倒排列表（Posting List），记录包含该词条的所有文档 ID。

例如：

文档 1: "the quick brown fox"
文档 2: "the lazy dog"
文档 3: "the quick dog"

倒排索引:
"brown" → [1]
"dog"   → [2, 3]
"fox"   → [1]
"lazy"  → [2]
"quick" → [1, 3]
"the"   → [1, 2, 3]  (通常作为停用词被去除)

查询 "quick dog" 时，分别查找 "quick" 和 "dog" 的倒排列表，取交集得到文档 3。

3.4.2 倒排索引的优化

实际的倒排索引比上面的简单示例复杂得多，需要多种优化：

词条字典（Term Dictionary）：使用 FST（Finite State Transducer）或 Trie 树压缩存储所有词条，支持前缀匹配和模糊搜索。

倒排列表压缩：使用差分编码（Delta Encoding）和变长整数编码（VarInt）压缩文档 ID 列表。例如，[1, 5, 12, 23] 编码为 [1, 4, 7, 11]。

位置信息（Position Information）：记录词条在文档中的位置，支持短语搜索和邻近搜索。

相关性评分：使用 TF-IDF 或 BM25 算法计算文档与查询的相关性分数。

典型的全文搜索引擎：Elasticsearch、Apache Solr、Apache Lucene。

3.5 OLTP vs OLAP

3.5.1 两种工作负载

数据密集型应用通常有两种截然不同的工作负载：

OLTP（Online Transaction Processing，在线事务处理）：

• 特点：大量短小的读写操作，每次操作涉及少量数据。
• 典型场景：电商下单、银行转账、用户登录。
• 性能指标：低延迟（毫秒级）、高并发（数千 QPS）。
• 数据模型：高度规范化，避免冗余。
• 代表系统：MySQL、PostgreSQL、Oracle。

OLAP（Online Analytical Processing，在线分析处理）：

• 特点：少量复杂的查询，每次查询涉及大量数据（数百万到数十亿行）。
• 典型场景：报表生成、数据分析、趋势预测。
• 性能指标：高吞吐量（每秒处理 GB 级数据）、可接受的延迟（秒到分钟级）。
• 数据模型：反规范化（星型模型、雪花模型），允许冗余。
• 代表系统：ClickHouse、Apache Doris、Amazon Redshift、Google BigQuery。

3.5.2 列式存储（Column-Oriented Storage）

OLAP 工作负载通常使用列式存储而非行式存储。

行式存储：一行数据连续存储在磁盘上。

行 1: [id=1, name=Alice, age=30, city=Beijing]
行 2: [id=2, name=Bob, age=25, city=Shanghai]

列式存储：一列数据连续存储在磁盘上。

id 列:   [1, 2, 3, ...]
name 列: [Alice, Bob, Charlie, ...]
age 列:  [30, 25, 35, ...]
city 列: [Beijing, Shanghai, Guangzhou, ...]

列式存储的优势（对于 OLAP）：

I/O 效率高：分析查询通常只涉及少数几列，列式存储只需要读取相关列，避免读取无用的列。

压缩率高：同一列的数据类型相同，相似度高，压缩算法（如字典编码、游程编码、位图编码）可以高效压缩。

CPU 缓存友好：连续读取同一列的数据，CPU 缓存命中率高。

向量化执行：可以一次处理一批数据（SIMD 指令），充分利用现代 CPU 的并行计算能力。

列式存储的劣势（对于 OLTP）：

写入放大：插入一行数据需要写入多个列文件。

点查低效：读取一行数据需要从多个列文件中查找，I/O 次数多。

典型的列式数据库：ClickHouse、Apache Parquet（文件格式）、Apache Columnar、Google Dremel。

重要知识点

知识点 1：WAL（Write-Ahead Log）

WAL 是保证数据库崩溃恢复（Crash Recovery）的核心机制。

核心思想：在对数据文件进行任何修改之前，先将修改操作写入一个追加日志（WAL）。如果数据库在修改数据文件的过程中崩溃，重启时可以通过重放 WAL 来恢复数据。

WAL 的工作流程：

事务开始时，生成一条 WAL 记录，描述即将进行的修改。

WAL 记录先写入磁盘（顺序写入，速度快）。

然后修改内存中的数据页（Buffer Pool）。

被修改的数据页（脏页）在后台异步写入磁盘。

如果数据库崩溃，重启时重放 WAL 中未持久化的修改。

WAL 的关键约束：WAL 记录必须在数据页之前写入磁盘。这就是"Write-Ahead"的含义。

知识点 2：Buffer Pool

Buffer Pool（缓冲池）是数据库内存管理的核心组件。

核心思想：在内存中维护一个数据页的缓存。读取数据时先查 Buffer Pool，命中则直接返回；未命中则从磁盘读入 Buffer Pool。写入数据时先修改 Buffer Pool 中的页（成为脏页），后台异步将脏页刷盘。

Buffer Pool 的管理策略：

• LRU（Least Recently Used）：淘汰最近最少使用的页。简单但在扫描大量数据时可能淘汰热点页。
• LRU-K：考虑页的使用频率，避免一次性扫描淘汰热点页。
• Clock / Second-Chance：LRU 的近似实现，使用引用位代替时间戳，开销更低。

Buffer Pool 的大小直接影响数据库性能。通常建议将 Buffer Pool 设置为可用内存的 60%-80%。

知识点 3：Compaction 策略

LSM-Tree 存储引擎中，Compaction 是保证读取性能的关键机制。两种主要的 Compaction 策略：

Size-Tiered Compaction（STC）：

• 将相似大小的 SSTable 合并为一个新的、更大的 SSTable。
• 优势：写入放大低。
• 劣势：读取放大高（需要查找多个 SSTable），空间放大高。
• 适合：写密集型场景。

Leveled Compaction（LC）：

• 将 SSTable 组织成多个级别（Level），每个级别有大小上限。
• Level 0 的 SSTable 可能与 Level 1 的键范围重叠，但同一级别内的 SSTable 键范围不重叠。
• 优势：读取放大低（每层最多查找一个 SSTable），空间放大低。
• 劣势：写入放大高（需要频繁合并）。
• 适合：读密集型场景。

Tiered + Leveled 混合策略：

• 低层使用 Size-Tiered（减少写入放大），高层使用 Leveled（保证读取性能）。
• RocksDB 的 Universal Compaction 就是这种策略。

知识点 4：Bloom Filter

布隆过滤器（Bloom Filter）是一种空间效率极高的概率数据结构，用于判断一个元素是否属于某个集合。

特性：

• 可以确定"元素一定不在集合中"。
• 不能确定"元素一定在集合中"（有一定的假阳性率）。
• 不支持删除操作（标准版本）。

在存储引擎中的应用：

• LSM-Tree 中，读取时可能需要查找多个 SSTable。通过在内存中维护一个 Bloom Filter，可以快速跳过不包含目标键的 SSTable，减少磁盘 I/O。
• 一个误判率为 1% 的 Bloom Filter，每个键只需要约 10 比特的空间。

常见误区

误区 1："SSD 时代不需要关心顺序写入了"

纠正：虽然 SSD 的随机写入性能比 HDD 好很多，但顺序写入仍然比随机写入快 5-10 倍。更重要的是，SSD 的随机写入会触发写放大（Write Amplification），因为 SSD 需要以块（Block）为单位擦除，以页（Page）为单位写入。频繁的随机写入会加速 SSD 的磨损，降低寿命。因此，面向日志的存储引擎在 SSD 上仍然有显著优势。

误区 2："B-Tree 比 LSM-Tree 慢"

纠正：这种说法过于笼统。B-Tree 的读取性能更稳定（O(log N) 且路径可预测），适合读密集型场景。LSM-Tree 的写入性能更好（顺序追加），适合写密集型场景。选择哪种取决于具体的工作负载。现代数据库（如 PostgreSQL 和 MySQL）使用 B-Tree 仍然可以提供极高的性能。

误区 3："索引越多越好"

纠正：索引是空间换时间的策略。每个额外的索引都会：

• 增加写入开销（每次写入都需要更新所有相关索引）。
• 占用额外的磁盘空间。
• 增加 Compaction 的工作量（对于 LSM-Tree）。
• 增加 Buffer Pool 的压力。

应该只为频繁查询的列创建索引，并定期审查和删除不再使用的索引。

误区 4："列式存储适合所有分析场景"

纠正：列式存储适合"读取少量列、扫描大量行"的分析查询。但对于"读取所有列、涉及少量行"的点查场景（如根据 ID 查找一条记录），行式存储更高效。此外，列式存储的写入性能较差，不适合高频的 OLTP 工作负载。很多现代数据仓库使用行列混合存储来兼顾两种场景。

误区 5："数据库崩溃后会丢失数据"

纠正：现代数据库通过 WAL + 定期 Checkpoint 机制保证数据不丢失。只要 WAL 记录已经写入磁盘（fsync），即使数据库崩溃，重启后也可以通过重放 WAL 恢复所有已提交事务的数据。这就是 ACID 中持久性（Durability）的保证。

实践应用

实践 1：选择合适的存储引擎

根据工作负载选择存储引擎：

实践 2：索引优化策略

分析慢查询：使用 EXPLAIN 或 EXPLAIN ANALYZE 查看查询执行计划，识别缺少索引的查询。

选择合适的索引类型：

- 等值查询（WHERE id = 1）：Hash 索引或 B-Tree 索引。

- 范围查询（WHERE age > 20）：B-Tree 索引。

- 全文搜索：倒排索引。

- 地理空间查询：R-Tree 或 GiST 索引。

使用复合索引：对于多列查询，创建复合索引（如 (last_name, first_name)）。注意列的顺序——选择性高的列放在前面。

避免过度索引：定期审查索引使用情况，删除未使用的索引。

实践 3：调优 Buffer Pool

监控命中率：Buffer Pool 命中率应该保持在 95% 以上。如果低于 90%，考虑增加 Buffer Pool 大小。

合理配置大小：通常设置为可用内存的 60%-80%。留出内存给操作系统和其他进程。

监控脏页比例：脏页比例过高可能导致刷盘压力，影响写入性能。调整 innodb_io_capacity 等参数控制刷盘速率。

预热 Buffer Pool：数据库重启后，Buffer Pool 是空的，需要时间预热。可以配置在关闭时保存 Buffer Pool 状态，重启时恢复。

实践 4：OLTP 与 OLAP 分离

对于同时需要 OLTP 和 OLAP 的系统，推荐将两种工作负载分离：

OLTP 数据库：使用行式存储（MySQL、PostgreSQL），处理在线事务。

数据同步：通过 CDC（Change Data Capture）工具（如 Debezium、Canal）将数据实时同步到 OLAP 系统。

OLAP 数据库：使用列式存储（ClickHouse、BigQuery），处理分析查询。

应用层分离：OLTP 查询走 OLTP 数据库，OLAP 查询走 OLAP 数据库，避免互相干扰。

这种架构被称为 HTAP（Hybrid Transactional/Analytical Processing） 的分离实现，兼顾了事务处理和分析处理的性能需求。

本章小结

本章深入探讨了数据库存储引擎的内部工作原理：

两种核心存储范式：

- 面向日志的存储（LSM-Tree）：所有写入都是顺序追加，写入性能极高，适合写密集型场景。代表：LevelDB、RocksDB、Cassandra。

- 面向页面的存储（B-Tree）：数据组织成平衡树，读取性能稳定，支持高效的原地更新。代表：PostgreSQL、MySQL。

索引技术：

- 哈希索引：O(1) 查找，但不支持范围查询。

- 辅助索引：加速非主键列查询，但需要回表。

- 聚簇索引：索引和数据存储在一起，减少 I/O。

- 覆盖索引：索引包含查询所需的所有列，避免回表。

- 倒排索引：支持高效的全文搜索。

OLTP vs OLAP：

- OLTP 使用行式存储，适合短小的事务操作。

- OLAP 使用列式存储，适合大规模的分析查询。

- 现代架构通常将两者分离，通过 CDC 同步数据。

关键机制：

- WAL：保证崩溃恢复和数据持久性。

- Buffer Pool：内存缓存，减少磁盘 I/O。

- Compaction：LSM-Tree 的后台合并，保证读取性能。

- Bloom Filter：概率数据结构，加速 LSM-Tree 的读取。

理解这些底层原理，可以帮助你做出更好的架构决策：选择合适的数据库、设计高效的索引策略、诊断性能瓶颈、优化系统配置。存储引擎的选择没有绝对的好坏，关键在于匹配具体的工作负载和性能需求。