DDIA

DDIA 笔记：第四章 - 存储与检索

核心问题： 数据库如何在内部存储数据，并在需要时高效地检索数据？

引言：

  • 数据库两大基本功能：存储数据、检索数据。
  • 本章关注数据库内部的存储与检索机制，即 存储引擎 的工作原理。
  • 理解存储引擎有助于选择合适的引擎并进行性能优化。
  • 重点区分 事务处理 (OLTP) 和 分析处理 (OLAP) 优化的引擎。

一、 驱动数据库的数据结构

1. 最简单的数据库 (Bash 示例)

  • db_set key value: 将键值对追加到日志文件末尾。
  • db_get key: 扫描整个文件，找到键最后一次出现的位置并返回其值。
  • 优点： db_set 追加写入非常快。
  • 缺点： db_get 查找性能差，开销为 O(n)。
  • 核心概念：
    • 日志 (Log): 一个仅追加 (append-only) 的记录序列。是许多数据库的基础。
    • 索引 (Index): 为了加速查找而从主数据衍生的 额外 结构。
    • 权衡： 索引加速读取，但会减慢写入（因为写入时需要更新索引）。需要根据查询模式选择合适的索引。

2. 散列索引 (Hash Index)

  • 思路： 使用内存中的散列表（Hash Map）存储键到数据文件中 字节偏移量 (byte offset) 的映射。
  • 工作流程：
    • 写入 (db_set): 将键值对追加到数据文件（段文件）末尾，并更新内存散列表中的键->偏移量映射。
    • 读取 (db_get): 通过键在内存散列表中查找偏移量，然后 seek 到文件中的该位置读取值。
  • 代表： Bitcask (Riak 默认引擎)。
  • 特点：
    • 优点： 写入快（顺序追加），读取快（如果键在内存中）。适合值频繁更新、键数量能放入内存的场景。
    • 缺点：
      1. 内存限制： 所有键必须能放入内存。硬盘散列表性能不佳（随机 I/O, 哈希冲突）。
      2. 范围查询效率低： 无法高效扫描一个范围内的键。
  • 优化与实现细节：
    • 分段 (Segmentation): 日志文件达到一定大小时，关闭当前段，开始写入新段。
    • 压缩 (Compaction): 在后台合并段文件，丢弃重复的键（只保留最新版本），回收空间。
    • 合并 (Merging): 可以在压缩时将多个段合并成一个更大的段。
    • 查找： 从最新的段开始，逐个检查段的内存散列表。
    • 文件格式： 二进制格式优于 CSV（记录长度前缀 + 原始字节）。
    • 删除记录： 追加特殊删除标记（墓碑, tombstone）。压缩时丢弃被标记删除的键的所有值。
    • 崩溃恢复：
      • 方法1: 重启时扫描所有段文件重建内存散列表（慢）。
      • 方法2 (Bitcask): 将每个段的散列表快照存储在硬盘上，加速恢复。
    • 部分写入： 使用校验和检测并忽略损坏记录。
    • 并发控制： 通常单写入线程（因为是顺序追加），多读取线程。
  • 追加日志的优势：
    • 顺序写入性能优于随机写入（尤其在 HDD，SSD 也有利）。
    • 并发和崩溃恢复更简单（文件不可变）。
    • 合并旧段避免了数据文件碎片化问题。

3. SSTables 和 LSM 树 (Log-Structured Merge-Tree)

  • SSTable (Sorted String Table): 对段文件格式的改进。
    • 核心要求 1： 段文件内的键值对 按键排序。
    • 核心要求 2： 每个键在 合并后的 段文件中只出现一次。
  • SSTable 的优势：
    1. 高效合并： 即使文件大于内存，也能像归并排序一样高效合并多个已排序的段文件。合并时，保留最新段中的值，丢弃旧段中的重复键。
    2. 稀疏内存索引： 无需在内存中存储所有键。只需存储部分键及其偏移量。查找时，在内存索引中定位范围，然后扫描硬盘上的相关段。
    3. 块压缩： 可以将排序后的键值对分组为块（Block），在写入硬盘前压缩块。内存索引指向块的起始位置。节省空间，减少 I/O 带宽。
  • 构建和维护 SSTables (LSM 树架构):
    1. 写入: 新写入添加到内存中的 平衡树 结构（如红黑树、AVL树），称为 内存表 (memtable)。
    2. 刷盘: 当 Memtable 大于阈值时，将其作为 SSTable 文件 写入硬盘（此时 Memtable 已排序，写入高效）。新 SSTable 成为最新的段。
    3. 读取: 先查 Memtable -> 最新 SSTable 段 -> 次新 SSTable 段 -> …
    4. 合并/压缩: 后台线程定期合并 SSTable 段，并丢弃被覆盖或删除的值。
    5. 崩溃恢复: 使用 预写日志 (WAL) 记录写入操作。当 Memtable 刷盘成功后，对应的 WAL 可丢弃。
  • 代表: LevelDB, RocksDB, Cassandra, HBase (受 Google Bigtable 启发)。Lucene 词典存储也类似。
  • LSM 树 (Log-Structured Merge-Tree): 指这种基于 合并和压缩排序文件 (SSTable) 原理的存储引擎。
  • 性能优化:
    • 布隆过滤器 (Bloom Filter): 快速判断一个键 是否可能存在，用于优化对不存在键的查找，避免不必要的硬盘读取。
    • 压缩策略:
      • Size-Tiered Compaction: 将较小、较新的 SSTables 合并到较大、较旧的 SSTables 中 (HBase, Cassandra)。
      • Leveled Compaction: 将键范围分割到更小的 SSTables，并将数据分层移动，压缩更增量，空间占用更少 (LevelDB, RocksDB, Cassandra)。
  • LSM 树特点： 高写入吞吐量（顺序写），适合范围查询，即使数据远超内存也能工作。
### LSM树的追加写（Append-Only）与合并机制

  1. 基本原理 LSM树（Log-Structured Merge Tree）采用只追加不修改的策略。数据首先写入内存（MemTable），达到阈值后以顺序写方式刷入磁盘形成不可变的SSTable文件。旧数据通过后台的Compaction过程合并并清理过期记录，最终形成新的有序文件，而非直接修改原有文件。

  2. 实现细节

    • MemTable与SSTable：内存中的MemTable使用跳表或红黑树结构保证有序；磁盘上的SSTable按层级组织，低层文件合并后生成高层大文件 。
    • Compaction策略：分为Minor（内存到磁盘）和Major（磁盘文件合并），通过顺序I/O批量处理数据，减少随机写。

  3. 性能影响

    • 优点：顺序写大幅提升写入吞吐，适合高并发写入场景（如HBase、LevelDB）；数据不可变性简化并发控制。
    • 缺点：读操作需多级查询（内存+各层SSTable），需布隆过滤器优化；Compaction可能引发空间放大（临时存储冗余数据）和读放大（多次I/O）。

LSM概念形象举例

核心思想：解决写入效率问题

想象一下，你有一个巨大的、按字母顺序排列的文件柜（代表硬盘上的数据）。

  1. 直接插入的问题（类似 B 树原地更新）： 每次来一份新文件（新数据），你都要找到它在柜子里的确切位置，挪开现有文件，把它塞进去。如果文件很多，这个过程会非常慢，因为你一直在“随机”地打开不同的抽屉和文件夹。硬盘的随机写入性能很差。
  2. 简单追加的问题（类似前面 Bash 脚本）： 你可以把所有新文件都扔到柜子顶上的一个大箱子里（追加到日志文件末尾）。这样放文件很快（顺序写入）。但找文件时，你得翻遍整个箱子才能找到最新的那份（读取性能差）。而且箱子会无限增大。
  3. 带内存索引的追加（类似 Bitcask）： 在旁边放个小本子（内存散列表），记下每个文件在大箱子里的位置。放文件还是很快，找文件也快了（查本子就知道去哪找）。但问题是，如果文件种类特别多（键多），你的小本子可能不够大（内存限制），而且还是没法高效地按顺序查找文件（比如找“合同A”到“合同F”的所有文件）。

LSM 树的解决方案：结合内存、顺序写和后台合并

LSM 树就是为了结合写入速度、处理大数据量和较好的读取性能而设计的。它引入了 SSTable (Sorted String Table) 这个关键组件。

我们再用文件柜的类比：

  1. 内存缓冲区 (Memtable): 不直接往大柜子或大箱子放。新来的文件先放在你办公桌上的一个文件架 (Memtable) 里。这个文件架不大（内存有限），但你随时保持里面的文件按字母顺序排好（用的是平衡树，如红黑树，插入和排序都很快）。

    • 对应步骤 1: 新写入添加到内存中的平衡树 (Memtable)。

  2. 批量刷盘 (Flush to SSTable): 当你桌上的文件架满了（Memtable 达到阈值），你把整个架子上的文件（它们已经是排好序的！）一次性、按顺序地整理成一个新的、只读的文件夹 (SSTable)，然后把它放到那个大文件柜的最顶层。这个过程很快，因为你是把一批文件顺序地写入一个新文件夹，而不是随机插入旧文件夹。

    • 对应步骤 2: Memtable > 阈值 -> 作为 SSTable 文件写入硬盘。新 SSTable 是最新的段。

  3. 写入日志 (WAL): 在你把文件放到桌上文件架 (Memtable) 的同时，为了防止突然断电导致桌上的文件丢失，你立刻在旁边的一个流水账本 (WAL) 上记一笔：“收到了某文件”。这个账本是写在不容易丢失的地方（硬盘）。只有当你把桌上那个满了的文件架成功整理成文件夹 (SSTable) 并放入大柜子后，你才能擦掉流水账本上对应的记录。

    • 对应步骤 5: 使用 WAL 记录写入操作。Memtable 刷盘成功后，WAL 可丢弃。

  4. 查找文件 (Read):

    • 先看你桌上的文件架 (Memtable) 有没有。（最快）
    • 如果没有，就去大文件柜最顶层的那个最新文件夹 (最新的 SSTable) 里找。
    • 还没有？那就找次新的那个文件夹 (下一个 SSTable)… 以此类推，一层层往下找。
    • 对应步骤 3: 先查 Memtable -> 最新 SSTable -> 次新 SSTable -> …

  5. 后台整理 (Compaction / 合并压缩): 文件柜里的文件夹 (SSTables) 会越来越多。查找时可能要翻很多文件夹。所以，需要有个档案管理员（后台线程） 不断地工作：

    • 他会定期从柜子里拿出几个相邻的、比较旧的文件夹 (旧的 SSTables)。
    • 把这些文件夹里的所有文件倒出来，合并到一起，重新按字母排序。
    • 如果发现同一个文件有好几份（来自不同旧文件夹），只保留最新的那一份（基于写入时间或版本）。
    • 如果有些文件被标记为“已删除”(墓碑 tombstone)，就把它们彻底扔掉。
    • 最后，把这些整理好的文件装进一个新的、更大的文件夹 (新的 SSTable)，放回柜子，同时把那些被合并的旧文件夹扔掉。
    • 这个过程不断进行，控制了文件夹的数量，回收了空间，也让查找更高效（因为层数减少，或者每层的文件更少）。
    • 对应步骤 4: 后台定期合并 SSTable 段，丢弃覆盖/删除的值。

性能优化解释：

  • 布隆过滤器 (Bloom Filter): 在查找文件时，为了避免白跑一趟去翻一个肯定没有目标文件的文件夹 (SSTable)，可以在每个文件夹外面贴个“内容摘要”(布隆过滤器)。查找前先看摘要，如果摘要说“这个文件肯定不在里面”，你就不用打开这个文件夹了，直接跳到下一个。这能大大加快查找不存在的文件时的速度。（注意：摘要有时会误报“可能在里面”，但从不会漏报“肯定在里面”）。
  • 压缩策略 (Compaction Strategies): 这就是上面“档案管理员”整理文件柜的不同方法论：
    • Size-Tiered: 管理员倾向于把差不多大小的旧文件夹合并成一个大文件夹。优点是逻辑简单，合并时可能写入次数相对少。缺点是合并大文件夹时可能临时占用很多额外空间，而且可能导致一个很大的旧文件夹长期不被合并。
    • Leveled: 管理员把文件柜分成好几层（Level 0, Level 1, Level 2…）。新出炉的小文件夹放在 Level 0。整理时，他会拿一个 Level N 层的文件夹，跟 Level N+1 层中内容范围有重叠的文件夹合并，生成新的 Level N+1 层文件夹。优点是每次合并的规模通常更可控，总空间占用更稳定，读取时可能需要检查的文件更少。缺点是可能整体的写入放大（数据被反复读写合并的总量）会高一些。

LSM 树特点总结：

  • 写入快: 把随机写变成了内存操作 + 磁盘顺序写。
  • 范围查询友好: 因为 SSTable 内部是有序的。
  • 适合大数据: 数据可以远超内存大小。
  • 缺点: 读取可能需要检查多个地方 (Memtable + 多个 SSTable)，后台 Compaction 会消耗资源并可能影响性能（尽管实现时会尽量减少影响）。

LevelDB, RocksDB, Cassandra, HBase, Lucene 是什么？

它们都是使用了 LSM 树（或类似思想）作为其底层存储机制的软件：

  1. LevelDB & RocksDB:

    • 类型: 它们是 存储引擎库 (Library)，不是一个完整的、可以直接运行的数据库服务器。
    • 用途: 开发者可以在自己的应用程序中嵌入它们，来获得高性能的键值存储功能。就像你可以在你的代码里 import 一个数学库一样，你可以 import LevelDB/RocksDB 来处理数据的持久化存储。
    • 关系: LevelDB 是 Google 开发的。RocksDB 是 Facebook 基于 LevelDB 分叉出来并做了大量优化的，特别是在多核、SSD 和大规模服务器场景下表现更好。很多现代数据库（如 TiDB 的 TiKV 组件）都使用 RocksDB 作为其底层的存储引擎。
    • 它们实现了: Memtable, SSTable (按 Level 组织，默认 Leveled Compaction), WAL, Bloom Filter 等 LSM 核心组件。

  2. Cassandra:

    • 类型: 一个 分布式 NoSQL 数据库。它是一个完整的数据库系统，你可以安装、运行并连接使用。
    • 特点: 高可用、可扩展性强、面向列族（Wide Column Store）的数据模型。
    • 存储: 在每个 Cassandra 节点内部，它使用 LSM 树结构来存储数据。它需要处理数据如何在多个节点间分布、复制等分布式问题，但单个节点的数据持久化依赖的就是 LSM 树。它提供了 Size-Tiered 和 Leveled 两种 Compaction 策略供选择。

  3. HBase:

    • 类型: 另一个分布式 NoSQL 数据库，通常运行在 Hadoop 生态系统之上（使用 HDFS 作为底层文件系统）。
    • 特点: 面向列族，设计用来存储海量稀疏数据，灵感来自 Google 的 Bigtable 论文。
    • 存储: 同样，HBase 在其 RegionServer（处理数据的节点）内部使用 LSM 树架构。它的 Memtable 叫 MemStore，SSTable 叫 HFile。它也依赖 Compaction 来管理 HFile。

  4. Lucene:

    • 类型: 一个 全文搜索引擎库 (Library)，也不是一个完整的数据库。像 Elasticsearch 和 Solr 这些流行的搜索引擎，它们的核心都是基于 Lucene 构建的。
    • 用途: 专门用于创建和查询倒排索引 (Inverted Index)，这是搜索引擎能快速找到包含特定单词的文档的关键。
    • 存储: Lucene 在存储它的词典 (Term Dictionary) 和倒排列表 (Postings List) 时，也采用了类似 LSM 树的思想。新的索引数据先写入内存中的段 (segments)，然后刷到磁盘上成为不可变的段文件。后台会进行段合并 (segment merging)，这其实就是 Compaction 的另一种说法。

它们要么是 LSM 树的具体实现库 (LevelDB, RocksDB)，要么是 在其内部使用 LSM 树作为核心存储机制的完整数据库系统 (Cassandra, HBase)，要么是 在特定领域（如搜索）使用类似 LSM 思想的库 (Lucene)。它们都看中了 LSM 树在高写入吞吐量和处理大数据方面的优势。

4. B 树 (B-Tree)

  • 背景: 最广泛使用的索引结构，历史悠久且稳定 (1970s 至今)。几乎所有关系型数据库和许多 NoSQL 数据库都在使用。
  • 核心思想: 与日志结构不同，B 树将数据库分解为 固定大小 的 块 (Block) 或 页 (Page) (通常 4KB)，一次读/写一个页面。更接近底层硬件（硬盘按块组织）。
  • 结构:
    • 页面引用: 页面通过地址/位置相互引用，形成树状结构。
    • 根 (Root): 查找的起点。
    • 内部节点 (Internal Page): 包含若干键（作为边界）和指向子页面的引用。每个子页面负责一段连续的键范围。
    • 叶节点 (Leaf Page): 包含键的值，或指向值所在位置的引用。
    • 分支因子 (Branching Factor): 一个页面中子页面引用的数量 (通常几百)。
    • 平衡树: 深度保持 $O(\log n)$，通常 3-4 层即可支持非常大的数据量 (如 256TB)。
  • 操作:
    • 查找: 从根开始，根据键比较，逐层向下导航到叶子页。
    • 更新: 找到包含键的叶子页，修改值，将该页写回硬盘。
    • 插入: 找到合适的叶子页，添加键。若页面已满，则 分裂 (split) 成两个半满的页面，并更新父页面以反映新的分区。
  • 可靠性:
    • 原地更新 (Update-in-place): 基本写操作是 覆写 硬盘上的页面。
    • 风险: 如果在覆写多个页面（如分裂操作）的中途崩溃，可能导致索引损坏。
    • 解决方案: 预写式日志 (WAL / Redo Log)。所有 B 树修改必须先写入 WAL (仅追加文件)，再应用到树页面。崩溃恢复时，使用 WAL 使 B 树恢复一致状态。
    • 并发控制: 需要使用 锁存器 (Latches) (轻量级锁) 保护树结构，防止多线程访问时出现不一致。
  • 优化:
    • 写时复制 (Copy-on-Write): 修改时不覆写原页面，而是写入新位置，并更新父节点指向新位置（如 LMDB）。有助于并发控制。
    • 键缩短: 在内部节点只存储足够区分范围的前缀，节省空间，提高分支因子。
    • 页面布局: 尝试将叶子页面在硬盘上按序排列，以优化范围扫描（但难以维持）。
    • 叶子节点指针: 添加指向左右兄弟页面的指针，方便顺序扫描。
    • 分形树 (Fractal Tree): 借鉴日志结构思想减少硬盘查找。
  • B+ 树: B 树的一种常见变体（如键缩短、叶子节点链表），常与 B 树混用。
B树的原地更新（In-Place Update）机制

  1. 基本原理 B树的写操作通过直接覆写磁盘上的现有页面实现。例如，当插入或更新数据时，B树会定位到目标数据所在的磁盘页，修改该页的内容（如调整键值、分裂或合并节点），然后将修改后的页覆写回原位置。这种操作不改变页面的物理地址，所有指向该页的引用（如父节点的指针）仍保持有效。

  2. 实现细节

    • 页面分裂与合并：插入可能导致节点超过容量上限，此时需分裂节点并调整父节点的指针；删除可能导致节点过空，需合并相邻节点。这些操作涉及多个页面的覆写 。

    • 写放大（Write Amplification）：即使修改少量数据，也可能需要重写整个页面（如16KB的页）。若数据跨页分布，会导致更多随机I/O操作 。

  3. 性能影响

    • 优点：数据始终有序，查询效率稳定（时间复杂度O(logN)），适合高频查询和事务型场景（如MySQL） 。
    • 缺点：频繁的随机写导致磁盘I/O压力大，尤其在数据量激增时，节点分裂可能引发级联更新，加剧写放大 。

5. B 树 与 LSM 树 对比

  • 经验法则:
    • LSM 树: 写入更快。
    • B 树: 读取更快，且延迟更可预测。
  • LSM 树优点:
    • 写入吞吐量高: 将随机写转换为顺序写。写放大 (Write Amplification) 可能更低（取决于配置和负载）。
    • 压缩效果好: 定期重写 SSTables 去除碎片，存储开销低（尤其 Leveled Compaction）。文件通常比 B 树小。
    • SSD 友好: 低写放大和低碎片化对 SSD 寿命和性能有利。
  • LSM 树缺点:
    • 压缩干扰: 后台压缩可能影响读写性能，导致高百分位延迟较长。
    • 压缩速率: 高写入速率下，压缩可能跟不上，导致未合并段增多，磁盘耗尽，读取变慢。需要监控。
    • 读取可能较慢: 需要检查 Memtable 和多个 SSTable 段。
    • 键冗余: 同一个键可能存在于多个段中（直到压缩）。
  • B 树优点:
    • 读取快且稳定: 查找路径短，延迟可预测。
    • 键唯一性: 每个键只存在于索引的一个位置。利于实现事务锁（如范围锁）。
    • 成熟: 技术非常成熟，性能稳定。
  • 结论: 没有绝对优劣，需要根据具体工作负载进行基准测试。
特性B树LSM树
写入方式原地覆写（随机I/O为主）追加写（顺序I/O为主）
写入性能低吞吐，适合低频更新高吞吐，适合海量写入
读取性能稳定高效（单次路径）可能延迟高（需多级查询）
空间效率无冗余数据存在临时冗余（Compaction前）
适用场景OLTP、强事务需求（如MySQL）OLAP、日志系统（如HBase、RocksDB）

6. 其他索引结构

  • 次级索引 (Secondary Index): 对非主键列建立的索引。
    • 目的： 加速特定查询（如 WHERE 子句中的条件），对 JOIN 操作至关重要。
    • 实现：
      • 方法1: 索引值为匹配行标识符（Row ID 或主键）的列表。
      • 方法2: 通过在索引键后附加行标识符使键唯一。
    • B 树和 LSM 树都可用于次级索引。
  • 索引中存储值 (Value Storage):
    • 堆文件 (Heap File): 索引只存储指向数据行的 引用 (指针)，实际行数据存储在无特定顺序的堆文件中。
      • 优点： 避免多个次级索引造成的数据冗余。更新值（不改变大小）时效率高。
      • 缺点： 读取需要额外一次跳转（索引 -> 堆文件）。值变大会导致行移动和索引更新/转发指针。
    • 聚集索引 (Clustered Index): 行数据直接存储在索引的叶子节点中（通常是主键索引）。
      • 优点： 读取快（数据和索引在一起）。
      • 缺点： 每个表通常只能有一个聚集索引。次级索引可能更大（若引用聚集索引键）。
      • 例子: MySQL InnoDB (主键是聚集索引)，SQL Server (可指定)。
    • 覆盖索引 (Covering Index / Index with Included Columns): 在索引中存储 部分 列的值（除了索引键列）。
      • 优点： 如果查询所需的所有列都在索引中，则可以直接从索引获取结果，无需访问表数据（称为 索引覆盖查询）。
      • 权衡: 加速读取 vs. 增加存储和写入开销。
  • 多列索引 (Multi-Column Index):
    • 连接索引 (Concatenated Index): 将多个列按指定顺序 拼接 成一个索引键。
      • 类比: 电话簿按（姓，名）排序。
      • 优点： 对查询条件匹配索引键 前缀 的情况有效。
      • 缺点： 对不匹配前缀的查询（如只查“名”）无效。
    • 多维索引 (Multi-Dimensional Index): 用于查询多个维度/列的范围，尤其适用于 地理空间数据。
      • 例子: 查询地图矩形区域内的餐馆 (需要 latitude 和 longitude 范围)。
      • 挑战: 标准 B 树/LSM 树不擅长处理多维范围查询。
      • 解决方案:
        • 空间填充曲线 (Space-Filling Curve): 将 2D/多维坐标转换为 1D 值，再用 B 树索引。
        • 专用空间索引: R 树 (如 PostGIS 使用 GiST 实现)。
      • 应用: 不限于地理数据，如（颜色 R,G,B）搜索，（日期, 温度）范围查询。
  • 全文搜索和模糊索引:
    • 需求: 搜索 相似 的键（拼写错误、同义词、语法变体等），而非精确匹配或排序范围。
    • 代表: 全文搜索引擎 (如 Elasticsearch, Solr 底层的 Lucene)。
    • Lucene 词典实现:
      • 类似 SSTable 的结构存储 词 (term) -> 文档 ID 列表 (postings list) 的映射。
      • 内存索引使用 有限状态自动机 (Finite State Automaton) (类似 Trie)，而非稀疏键列表。
      • 模糊搜索: 自动机可转换为 Levenshtein 自动机，支持高效的 编辑距离 (edit distance) 查询。
    • 其他技术涉及信息检索、机器学习。
  • 内存数据库 (In-Memory Database):
    • 动机: RAM 成本下降，许多数据集可完全放入内存。
    • 类型：
      • 易失性 (缓存): 如 Memcached，重启后数据丢失。
      • 持久性: 通过 WAL、快照、复制或特殊硬件 (电池供电 RAM) 实现持久化。
    • 特点：
      • 性能优势: 主要来自 消除了内存与硬盘数据结构之间的编码/解码开销，而不仅仅是避免了硬盘读取（OS 缓存本身也能减少硬盘读）。
      • 数据模型: 更易实现复杂内存数据结构（如 Redis 的 Set, Sorted Set, List）。
    • 扩展:
      • 反缓存 (Anti-Caching): 当内存不足时，将最近最少使用的数据换出到硬盘，需要时再加载回来（数据库比 OS 更精细地管理）。索引仍需常驻内存。
      • 未来: 非易失性存储器 (NVM) 可能带来新设计。

二、 事务处理 (OLTP) 还是 分析 (OLAP)?

1. 定义与区别:

  • 事务 (Transaction): 一组读写操作构成的逻辑单元（不一定保证 ACID）。
  • OLTP (Online Transaction Processing):
    • 用户: 终端用户，通过应用程序交互。
    • 访问模式: 大量并发请求，每次查询通常访问少量记录（通过键/索引）。低延迟是关键。
    • 数据: 主要关注数据的最新状态。
    • 例子: 网站交互、订单处理、银行交易。
  • OLAP (Online Analytical Processing):
    • 用户: 内部业务分析师，用于决策支持（商业智能）。
    • 访问模式: 查询量少，但每个查询通常 扫描大量记录，读取部分列，进行 聚合 (COUNT, SUM, AVG)。高吞吐量是关键。
    • 数据: 关注历史数据和趋势。
    • 例子: 销售报表、用户行为分析。

表 3-1 OLTP vs OLAP 特点对比

属性事务处理系统 (OLTP)分析系统 (OLAP)
主要读取模式查询少量记录，按键读取在大批量记录上聚合
主要写入模式随机访问，写入要求低延时批量导入（ETL）或事件流
主要用户终端用户，通过 Web 应用内部数据分析师，决策支持
处理的数据数据的最新状态（当前时间点）随时间推移的历史事件
数据集尺寸GB ~ TBTB ~ PB

2. 数据仓库 (Data Warehouse)

  • 背景: 为避免 OLAP 查询影响 OLTP 系统性能，企业倾向于建立独立的数据仓库。
  • 定义: 一个独立的数据库，包含来自各种 OLTP 系统的 只读数据副本，专门用于分析查询。
  • ETL (Extract-Transform-Load): 从 OLTP 系统 抽取 数据 -> 转换 为适合分析的模式 -> 清理 -> 加载 到数据仓库的过程。
  • 优势:
    • 不影响 OLTP 性能。
    • 可以针对分析访问模式进行 深度优化。
  • 技术栈:
    • 传统商业产品: Teradata, Vertica, SAP HANA, Oracle Exadata, Amazon Redshift (基于 ParAccel)。
    • 开源 SQL-on-Hadoop: Hive, Spark SQL, Impala, Presto, Drill (部分受 Google Dremel 启发)。
    • 混合型: Microsoft SQL Server, SAP HANA (内部有不同引擎支持 OLTP 和 OLAP)。
  • 数据模型: 通常是关系型 (SQL 适合分析)。

3. 星型模式与雪花模式 (Star and Snowflake Schemas)

  • 背景: 数据仓库中常见的数据建模方式（维度建模）。
  • 星型模式 (Star Schema):
    • 中心: 事实表 (Fact Table)，每行代表一个事件（如一次销售、一次点击）。通常非常大且宽（列多）。包含 度量值 (measures) 和指向维度表的外键。
    • 周围: 维度表 (Dimension Tables)，描述事件的背景（Who, What, Where, When, Why），如 dim_product, dim_time, dim_customer, dim_store。包含描述性属性。
    • 可视化: 事实表在中心，维度表像星星一样分布四周。
  • 雪花模式 (Snowflake Schema):
    • 维度表进一步 规范化 为子维度（如 dim_product 引用 dim_brand 和 dim_category）。
    • 比较: 雪花模式更规范化，但星型模式更简单，通常更受分析师青睐。

三、 列式存储 (Column Stores / Column-Oriented Storage)

1. 核心思想:

  • 动机: OLAP 查询通常只访问表中少数几列，但涉及大量行。行式存储 (Row Store) 需要加载整行数据，效率低下。
  • 解决方案: 按 列 (Column) 存储数据，而不是按行。将每一列的所有值连续存储在一起。
  • 优点: 查询只需读取和解析所需的列，大大减少 I/O。

2. 列压缩 (Column Compression)

  • 原理: 同一列的数据类型相同，且通常重复度较高（尤其是维度列或排序后的列），非常适合压缩。
  • 技术:
    • 位图编码 (Bitmap Encoding):
      • 适用于 低基数 (distinct values 少) 的列。
      • 为每个 不同值 创建一个位图，每行对应一个 bit (1 表示该行是此值，0 则否)。
      • 优点： 对于 WHERE col IN (...) 或 WHERE col1 = ... AND col2 = ... 这类查询，可以通过高效的位运算 (OR, AND) 实现。
      • 优化： 对于稀疏位图（很多 0），可以使用 游程编码 (Run-Length Encoding, RLE) 进一步压缩。
    • 其他压缩算法也可用。
  • 代表: Parquet (支持嵌套数据的列式格式)。

注意: Cassandra/HBase 的 “列族 (Column Family)” 并非真正的列式存储。它们在列族内仍然是按行存储的。

3. 内存带宽和矢量化处理 (Vectorized Processing)

  • 瓶颈: OLAP 查询的瓶颈不仅是磁盘 I/O 带宽，还有内存到 CPU 缓存的带宽以及 CPU 计算效率。
  • 列存优势:
    • 缓存友好: 压缩后的列数据块更容易放入 CPU 缓存。
    • 矢量化处理: CPU 可以在一个紧凑循环中对一批（向量）来自同一列的值执行操作（使用 SIMD 指令），而不是对每行数据进行分支和函数调用。极大提升 CPU 利用率。

4. 列式存储中的排序顺序 (Sort Order)

  • 重要性: 虽然行的物理存储顺序不影响逻辑结果，但 按特定列排序 (Sort Key) 对 OLAP 非常有利。
  • 操作: 整个 行 被排序（基于一个或多个排序列的值），即使数据是按列存储的。
  • 好处:
    1. 查询优化: 对于按排序列过滤的查询（如按日期范围），只需扫描相关范围的行数据。
    2. 压缩优化: 排序后，列中相同的值会聚集在一起，形成长串的重复值，大大提高压缩率（尤其是 RLE）。第一个排序列压缩效果最好。
  • 多个排序顺序: (如 Vertica / C-Store)
    • 思路: 将相同数据存储多次，每次按不同的列组合排序。
    • 优点: 可以根据查询模式选择最优排序版本的数据进行查询。
    • 类比: 类似行存储的多个次级索引，但这里存储的是完整的、不同排序的数据副本。

5. 写入列式存储

  • 挑战: 原地更新（Update-in-place）对于压缩和排序的列数据非常困难或不可能。插入一行可能需要重写所有列文件。
  • 解决方案: 采用 LSM 树 的思想。
    • 写入: 先写入内存中的存储结构 (Memtable，可以是行式或列式)。
    • 刷盘: 积累足够写入后，批量写入新的、排序好的 列块 文件到硬盘。
    • 合并: 后台进行列文件的合并和压缩。
    • 读取: 查询需要合并来自硬盘列文件和内存中最近写入的数据。

6. 聚合：数据立方体和物化视图

  • 动机: OLAP 查询经常使用聚合函数 (SUM, AVG, COUNT等)。重复计算相同聚合可能效率低下。
  • 物化视图 (Materialized View):
    • 定义: 查询结果的 物理副本，存储在硬盘上。区别于普通视图（只是查询别名）。
    • 优点: 对于频繁使用的聚合查询，可以直接读取预计算结果，速度快。
    • 缺点: 当底层数据变化时需要更新视图（增加写入开销）。在读多写少的数据仓库中更常用。
  • 数据立方体 (Data Cube / OLAP Cube):
    • 定义: 物化视图的一种常见特例。按不同 维度 (Dimensions) 预先计算好的聚合网格。
    • 例子: 按 (日期, 产品, 商店) 聚合销售额。可以快速查询按任一维度或维度组合的总计。
    • 优点: 对符合立方体结构的查询极快。
    • 缺点: 灵活性差。无法回答未包含在立方体维度或聚合中的查询（如按价格区间过滤）。通常与原始数据并存，作为性能优化手段。

四、 本章小结

  • 存储引擎两大类：OLTP 优化 (低延迟，高并发随机访问) vs OLAP 优化 (高吞吐量，批量扫描聚合)。
  • OLTP 引擎主要流派：
    • 日志结构 (Log-Structured): 仅追加，后台合并 (SSTables, LSM 树)。代表: Bitcask, LevelDB, RocksDB, Cassandra, HBase。优点: 高写入吞吐量。
    • 原地更新 (Update-in-Place): 基于页面的覆写 (B 树)。代表: 几乎所有关系型数据库。优点: 读取快且稳定，事务支持好。
  • 索引结构: 散列索引、SSTables、LSM 树、B 树、次级索引、聚集索引、覆盖索引、多列索引 (连接、多维)、全文/模糊索引。
  • 内存数据库: 利用 RAM 消除编码开销，提供高性能和特殊数据模型。
  • OLAP 优化:
    • 数据仓库: 分离 OLTP 和 OLAP 负载。
    • 星型/雪花模式: 常用数据模型。
    • 列式存储: 核心优化。按列存储，极大减少 I/O。
    • 列压缩: 利用列数据特性 (位图编码, RLE)。
    • 矢量化处理: 提升 CPU 效率。
    • 排序: 优化查询和压缩。
    • 物化视图/数据立方体: 预计算聚合。
  • 核心权衡: 读性能 vs 写性能、空间 vs 时间、灵活性 vs 性能。
  • 理解存储引擎内部机制有助于选择合适的工具、进行性能调优和理解系统行为。