第三章：存储与检索

导读

存储引擎是数据库系统的核心组件，它决定了数据如何存储在磁盘上，以及如何高效地检索数据。不同的存储引擎针对不同的工作负载进行了优化，理解存储引擎的原理对于选择合适的数据库至关重要。

本章将深入探讨两种主要的工作负载：事务处理（OLTP）和分析处理（OLAP），以及针对这两种工作负载优化的存储引擎。我们将学习索引的基本原理，包括B树、LSM树、列式存储等，理解它们的优势和局限。

通过本章的学习，你将理解：

• OLTP和OLAP工作负载的区别
• 行式存储和列式存储的原理
• B树和LSM树索引的工作机制
• 如何根据工作负载选择合适的存储引擎
• 存储引擎对性能的影响

核心概念详解

3.1 工作负载类型

数据库系统面临两种截然不同的工作负载：

3.1.1 联机事务处理（OLTP）

OLTP工作负载的特点是：

• 高并发：每秒数千到数百万次请求
• 低延迟：响应时间通常在毫秒级
• 小事务：每次读写的数据量很小（几KB到几十KB）
• 读写混合：读操作和写操作交替进行
• 数据局部性：通常只访问少量相关数据

典型应用场景：

• Web应用的后台数据库
• 电商系统的订单处理
• 银行的账户交易
• 社交网络的用户动态

3.1.2 联机分析处理（OLAP）

OLAP工作负载的特点是：

• 低并发：每秒几次到几十次查询
• 高延迟可接受：响应时间可以从几秒到几分钟
• 大查询：每次查询涉及大量数据（GB到TB级别）
• 读密集：主要是读操作，写操作较少
• 扫描大量数据：通常需要扫描整个表或大部分数据

典型应用场景：

• 数据仓库
• 商业智能（BI）系统
• 数据分析和报表
• 机器学习特征工程

3.1.3 OLTP vs OLAP

3.2 行式存储 vs 列式存储

3.2.1 行式存储（Row-oriented Storage）

行式存储将一行的所有列连续存储在磁盘上。

存储格式：

Row 1: [col1, col2, col3, ...]
Row 2: [col1, col2, col3, ...]
...

优势：

• 写入效率高：一次写入整行数据，减少磁盘IO次数
• 读取整行效率高：如果查询需要访问整行数据，行式存储只需一次磁盘IO
• 事务处理友好：OLTP工作负载通常需要访问整行数据

局限：

• 列扫描效率低：如果查询只需要访问少数几列，行式存储需要读取整行数据，浪费IO带宽
• 压缩率低：同一列的数据类型不同，压缩效果差

适用场景：

• OLTP工作负载
• 需要频繁写入的场景
• 查询通常需要访问整行数据

3.2.2 列式存储（Column-oriented Storage）

列式存储将同一列的数据连续存储在磁盘上。

存储格式：

Column 1: [row1, row2, row3, ...]
Column 2: [row1, row2, row3, ...]
...

优势：

• 列扫描效率高：如果查询只需要访问少数几列，列式存储只需读取相关列，大幅减少IO
• 压缩率高：同一列的数据类型相同，压缩效果非常好（可达10:1甚至更高）
• 向量化执行：可以批量处理同一列的数据，利用CPU SIMD指令加速

局限：

• 写入效率低：写入一行数据需要更新多个列文件，增加IO次数
• 读取整行效率低：如果查询需要访问整行数据，列式存储需要多次IO

适用场景：

• OLAP工作负载
• 数据仓库
• 查询通常只访问少数几列
• 数据压缩重要的场景

3.2.3 混合存储

现代数据库系统通常采用混合存储策略，结合行式和列式的优势：

列族存储（Column Family）：如Cassandra、HBase，将相关列组织成列族，每个列族内部按列存储。

行列混合：如Apache Kudu，同时支持行式和列式存储，根据查询类型自动选择。

内存列存储：如SAP HANA，将数据存储在内存中，同时支持行式和列式访问。

3.3 索引结构

索引是提高数据检索效率的关键技术。不同的索引结构适用于不同的工作负载。

3.3.1 B树索引（B-Tree）

B树是最经典的索引结构，广泛用于关系数据库。

结构特点：

• 平衡树：所有叶子节点在同一层，保证查询时间复杂度为O(log n)
• 多叉树：每个节点可以有多个子节点（通常几百到几千个），减少树的高度
• 有序存储：节点内的键值有序排列，支持范围查询

工作原理：

[50]
        /    \
    [20,35]  [65,80]
    /  |  \   /  |  \
  [10][25][40][60][70][90]

查询键值30：

从根节点开始，30 < 50，进入左子树

在节点[20,35]中，20 < 30 < 35，进入中间子树

在叶子节点中找到30

优势：

• 查询效率高：时间复杂度O(log n)，通常3-4次磁盘IO即可定位数据
• 支持范围查询：可以高效查询某个范围内的数据
• 支持排序：数据有序存储，可以直接返回排序结果
• 更新效率高：插入、删除、更新操作的时间复杂度也是O(log n)

局限：

• 写入放大：每次写入可能需要更新多个节点
• 空间利用率：节点通常只填充50%-70%，浪费空间
• 不适合写密集场景：频繁的节点分裂和合并会降低写入性能

适用场景：

• OLTP工作负载
• 读多写少的场景
• 需要范围查询和排序的场景

3.3.2 LSM树索引（Log-Structured Merge-Tree）

LSM树是专门为写密集场景设计的索引结构。

结构特点：

• 分层结构：分为内存层（MemTable）和磁盘层（SSTable）
• 顺序写入：所有写入先追加到内存，然后批量刷盘，避免随机写入
• 合并优化：后台异步合并多个SSTable，减少读放大

工作原理：

写入流程：
1. 写入内存表（MemTable）
2. 内存表满后，冻结为不可变内存表（Immutable MemTable）
3. 后台线程将不可变内存表写入磁盘，生成SSTable
4. 后台线程定期合并多个SSTable

读取流程：
1. 先查内存表
2. 再查不可变内存表
3. 最后查磁盘上的SSTable（从新到旧）

优势：

• 写入效率高：顺序写入磁盘，避免随机IO
• 压缩率高：SSTable可以高效压缩
• 适合写密集场景：写入性能稳定，不受数据量影响

局限：

• 读取效率低：可能需要查询多个SSTable
• 读放大：为了找到数据，可能需要读取多个文件
• 空间放大：同一数据可能存在多个SSTable中
• 写放大：后台合并操作会重复写入数据

适用场景：

• 写密集的工作负载
• 日志存储
• 时间序列数据
• 大数据量的场景

3.3.3 B树 vs LSM树

3.4 其他存储技术

3.4.1 布隆过滤器（Bloom Filter）

布隆过滤器是一种空间效率极高的概率数据结构，用于判断元素是否存在于集合中。

工作原理：

• 使用多个哈希函数将元素映射到位数组
• 查询时，如果所有对应位都为1，则元素可能存在
• 如果任一对应位为0，则元素一定不存在

优势：

• 空间效率高：存储100万元素只需几MB空间
• 查询速度快：时间复杂度O(k)，k为哈希函数个数

局限：

• 存在假阳性：可能误判元素存在
• 不支持删除：标准布隆过滤器不支持删除操作
• 不存储元素本身：只能判断存在性，不能获取元素值

应用场景：

• 缓存穿透防护
• 数据库索引优化
• 网络路由器

3.4.2 压缩技术

数据压缩可以减少存储空间，提高IO效率。

通用压缩算法：

• Snappy：压缩速度快，压缩率中等
• LZ4：压缩速度极快，压缩率较低
• Zstd：压缩速度和压缩率平衡
• Gzip：压缩率高，压缩速度慢

列式存储专用压缩：

• 字典编码（Dictionary Encoding）：将重复值替换为索引
• 游程编码（Run-Length Encoding）：将连续相同值替换为值和计数
• 位压缩（Bit Packing）：将小值压缩到更少的位数

3.4.3 物化视图（Materialized View）

物化视图是预先计算并存储的查询结果，用于加速复杂查询。

工作原理：

• 定义物化视图时，指定查询语句
• 数据库预先执行查询，将结果存储到磁盘
• 查询时，如果查询语句匹配物化视图，直接返回结果

优势：

• 查询速度快：避免重复计算
• 适合复杂查询：聚合、连接等操作可以预先计算

局限：

• 存储成本高：需要额外存储空间
• 维护成本高：基表数据变化时，需要更新物化视图
• 一致性延迟：物化视图可能不是最新的

应用场景：

• 数据仓库
• 报表系统
• 复杂查询加速

重要知识点

知识点1：没有万能的存储引擎

不同的存储引擎针对不同的工作负载进行了优化。OLTP工作负载适合行式存储和B树索引，OLAP工作负载适合列式存储。选择存储引擎时，应该根据实际工作负载进行选择。

知识点2：写入性能和读取性能通常是对立的

B树索引读取性能高，但写入性能较低；LSM树写入性能高，但读取性能较低。这是存储引擎设计中的基本权衡。

知识点3：压缩是存储引擎的关键技术

数据压缩可以减少存储空间，提高IO效率。不同的压缩算法在压缩速度和压缩率之间权衡。列式存储由于数据同质性高，压缩率通常远高于行式存储。

知识点4：索引不是越多越好

索引可以加速查询，但也会增加写入成本和存储空间。应该根据查询模式，只创建必要的索引。过多的索引会降低写入性能，浪费存储空间。

知识点5：理解存储引擎有助于性能调优

当系统性能不达标时，理解存储引擎的工作原理可以帮助定位瓶颈。例如，如果写入性能低，可能是B树索引的随机写入导致的，可以考虑切换到LSM树索引。

常见误区

误区1：认为列式存储总是优于行式存储

列式存储在OLAP场景下确实有优势，但在OLTP场景下可能不如行式存储。行式存储写入效率高，读取整行数据效率高，适合事务处理场景。选择存储格式时，应该根据工作负载进行选择。

误区2：认为索引越多查询越快

索引可以加速特定查询，但过多的索引会降低写入性能，浪费存储空间。应该根据查询模式，只创建必要的索引。定期审查索引使用情况，删除不常用的索引。

误区3：忽视压缩的重要性

数据压缩可以减少存储空间，提高IO效率。很多数据库系统默认启用压缩，但压缩算法的选择会影响性能。应该根据工作负载选择合适的压缩算法。

误区4：认为B树索引适合所有场景

B树索引读取性能高，但写入性能较低。对于写密集的场景，LSM树索引可能更合适。选择索引结构时，应该根据读写比例进行选择。

误区5：认为物化视图可以解决所有性能问题

物化视图可以加速复杂查询，但也会增加存储成本和维护成本。物化视图需要定期更新，可能引入一致性延迟。应该谨慎使用物化视图，只用于真正需要的场景。

实践应用

案例1：电商系统的存储引擎选择

一个电商系统需要处理多种工作负载：

订单处理（OLTP）：使用MySQL或PostgreSQL，行式存储，B树索引。高并发、低延迟、强一致性。

商品搜索：使用Elasticsearch，倒排索引。全文搜索、模糊匹配、聚合分析。

数据分析（OLAP）：使用ClickHouse或BigQuery，列式存储。大规模数据分析、报表生成。

关键经验：

• 根据工作负载选择合适的存储引擎
• 混合使用多种存储引擎是常见做法
• 不要试图用一种存储引擎解决所有问题

案例2：日志系统的存储优化

一个日志系统需要处理海量日志数据：

日志写入：使用LSM树索引（如RocksDB），顺序写入，高吞吐。

日志查询：使用倒排索引（如Elasticsearch），支持全文搜索。

日志归档：使用列式存储（如Parquet），高压缩率，节省存储空间。

关键经验：

• 写密集场景适合LSM树索引
• 全文搜索需要倒排索引
• 归档数据适合列式存储

案例3：社交网络的数据存储

一个社交网络需要处理用户数据、动态数据、消息数据：

用户数据：使用MySQL，行式存储，B树索引。强一致性，支持事务。

动态数据：使用Cassandra，LSM树索引，列族存储。高写入吞吐，水平扩展。

消息数据：使用HBase，LSM树索引。海量数据存储，高写入性能。

关键经验：

• 根据数据特点选择合适的存储引擎
• 考虑系统的可扩展性
• 权衡一致性和性能

本章小结

本章深入探讨了存储与检索的核心概念。

工作负载类型：OLTP工作负载特点是高并发、低延迟、小事务；OLAP工作负载特点是低并发、高延迟可接受、大查询。

存储格式：行式存储适合OLTP工作负载，写入效率高，读取整行数据效率高；列式存储适合OLAP工作负载，列扫描效率高，压缩率高。

索引结构：B树索引读取性能高，支持范围查询，适合读多写少场景；LSM树索引写入性能高，顺序写入，适合写多读少场景。

其他技术：布隆过滤器用于快速判断元素存在性；压缩技术可以减少存储空间，提高IO效率；物化视图可以加速复杂查询。

选择存储引擎时，应该根据工作负载、数据特点、查询模式等因素综合考虑。没有万能的存储引擎，混合使用多种存储引擎是常见做法。

下一章，我们将探讨编码与演化，这是数据系统长期运行中必须面对的问题。数据格式和Schema会随时间变化，如何在不中断服务的情况下进行系统演化，是一个重要的工程挑战。