存储引擎与索引演进

• LSM 顺序写+合并 vs B-Tree 原地更新+页分裂
• 写放大、读放大、空间放大三种放大效应的定义与权衡
• RocksDB 与 InnoDB 在各自场景下的取舍

B-Tree 采用原地更新，数据按 key 有序存放于页，点查定位快、读放大低，但随机写入会触发页的分裂/合并和写盘，写放大较高；由于 B-Tree 页可能需要多次读（根到叶），随机点查读放大一般为 1（索引深度）到几倍。LSM-Tree 把写入先追加到内存中的 MemTable，再以有序的 SSTable 批量落盘，通过后台 Compaction 合并，因此写入是顺序写、写放大低，但读需要从多层 SSTable 中查找、可能多次读，读放大较高；多次 Compaction 还会带来空间放大（暂时存在多份数据）。因此在写密集、追加型负载下 LSM 更优，在读密集/点查负载下 B-Tree 更优。工程取舍常体现在 RocksDB（LSM，适合存储引擎底座、写多读少）与 InnoDB（B+Tree，作为 OLTP 关系库的核心，读一致性好、支持事务）的对比上。

三种放大的本质是"用哪种资源换性能"：LSM 用读放大和空间放大换低写放大，B-Tree 用写放大换低读放大；二选一取决于负载是写密集还是读密集。

• Tiered 按层内多个文件、只合并满的一层，写放大低、空间放大高
• Leveled 按全局有序 level 合并，读放大低、空间放大低但写放大高
• 延迟稳定性（写放大突增 vs 后台合并的抖动）

Tiered Compaction（如 RocksDB 的 Universal、HBase 的多数配置）把同一层内积累多个 SSTable，只有某层文件数达到阈值才整体合并，合并时顺序写、写放大低、后台合并少，但同一 key 可能存在于多个文件，读放大高、空间放大高；且合并整层时可能产生写放大高峰。Leveled Compaction（如 RocksDB 的 Leveled、LevelDB 默认）把数据按全局有序的 level 组织，每层保持不重叠，读时最多检查每层一个文件，读放大低、空间放大低，但层间合并会反复重写有序数据，写放大高，且 merge 可能产生周期性抖动。Leveled 通常更利于读取和点查，Tiered 更利于大批量写入。工程上通过控制层数、合并触发阈值来在两者间权衡。

Tiered 用"读放大+空间放大"换"低写放大+低合并开销"，Leveled 用"高写放大"换"低读放大+低空间放大"，二者是读与写性能的典型权衡。

• Buffer Pool 缓存页、LRU/Clock 淘汰策略
• 脏页刷盘（异步/后台）与写放大
• checkpoint 与 WAL 重放、崩溃恢复的关系

Buffer Pool 是内存中的页缓存，采用 LRU 或 Clock 等淘汰算法决定哪些页被换出，命中率影响读放大（未命中则需读盘）。写入的页先被标记为脏页，其后由后台进程异步刷盘，而不是每次写都刷盘，从而减少写放大；但脏页过多会积累，需在 checkpoint 时把脏页刷盘并推进日志的回收点。checkpoint 与 WAL 配合：崩溃恢复时从 checkpoint 记录的 LSN 开始重放 redo log，因此 checkpoint 决定恢复起点、控制恢复时间；脏页刷盘不及时，崩溃时需重放更多日志，但刷盘过勤又会增加写放大。因此 LRU 淘汰、脏页刷盘和 checkpoint 共同在"内存命中率、写放大、崩溃恢复时间"之间权衡。

Buffer Pool 用缓存换读放大，脏页异步刷盘与 checkpoint 用日志换写放大与恢复时间；三者协同决定存储引擎的性能与可恢复性边界。

• B+Tree 树高与点查读放大（读路径页数）
• 随机写导致的页分裂/重写与写放大
• 与 LSM 写放大/读放大的定量对比

B+Tree 点查只需从根到叶读约 3-4 层页（大量 key 只需 3-4 页），读放大低；但随机写（插入/更新）会使目标页发生分裂或合并，需要多次读盘写盘，且页可能被反复改写，写放大高（通常 10-100 取决于页大小与随机性）。LSM 写入是顺序追加到 MemTable 再批量落盘，写放大较低（通常 1-10 区间，取决于层数与合并策略），但读需要从多层 SSTable 查找，读放大高（点查需检查多层 + Bloom filter）。定量上，B+Tree 点查读放大约等于树高（几页），写放大随随机更新显著增长；LSM 点查读放大与层数成正比（可能十几页），但写放大受 compaction 控制较低。二者在一个维度的优势恰是另一维度的劣势，工程取舍取决于负载。

读放大是"读路径上访问的页数"，写放大是"写入一个 key 实际写入盘的数据量倍数"；B+Tree 用有序结构换低读放大，LSM 用合并换低写放大。

• 写入先进入 MemTable 并追加 WAL
• WAL 组提交（group commit）合并多个写请求的 fsync
• 批量写（batch write）减少 fsync 次数

RocksDB 的写入路径是：写请求先追加到 WAL（Write-Ahead Log，确保持久性），同时把数据写入内存中的 MemTable（WriteBuffer）；当 MemTable 写满后转为不可变的 Immutable MemTable 并刷成一个 SSTable 落盘。WAL 是写路径上的瓶颈，因为每次写都需 fsync 到磁盘。为了提升吞吐，RocksDB 采用组提交（group commit）：多个并发写请求在 leader 上合并成一批，一次 fsync 同时落盘全部，从而分摊 fsync 的系统调用开销；同时支持批量写（batch write），把多个 key 的写入合并进一个 WriteBatch 再一次性提交。组提交与批量写共同把"每写一次 fsync"变成"多写一次 fsync"，显著提升高并发写吞吐。

写路径的核心是"WAL 的 fsync 是瓶颈"，组提交与批量写均通过减少 fsync 次数来放大写吞吐，是 RocksDB 高写吞吐的关键机制。

• latch 保护内部数据结构短期临界区，lock 保护事务数据的逻辑一致性
• latch 级别为页/记录、无死锁检测、短持有；lock 有死锁检测、可回滚
• B+Tree 并发访问需要 latch 保护页结构，LSM 通过不可变文件与版本化规避

latch（闩锁）是保护内存数据结构（如 B+Tree 页、缓冲池页）的短期互斥机制，持有时间极短、无死锁检测、不参与事务回滚，只保证内部结构的一致；lock（锁）是事务层用来串行化对数据的逻辑访问、保证 ACID 一致性的机制，有锁兼容矩阵、死锁检测、可被事务回滚释放。B+Tree 页会被多个线程并发读写，页内的指针、slot 结构必须保持物理一致，因此访问页时需要 latch；而 LSM 写路径主要操作 MemTable 和追加不可变 SSTable，通过"写入时加锁 MemTable、SSTable 一旦落盘即不可变（immutable）"避免了对可变页结构的长期锁，配合版本迭代（每次操作读取某个版本）实现无锁或轻锁并发，后续由 Compaction 在后台合并。

latch 是"物理结构"的短期保护，lock 是"逻辑数据"的长期串行化；LSM 用不可变文件+版本化规避了 B+Tree 那样的可变页结构并发问题。

• SSTable 分层组织（Data Block、Index Block、Filter Block）
• Block Cache 缓存数据块，Filter Block 用 Bloom Filter 快速判断 key 是否存在
• 协同减少 IO 与读放大

SSTable 是 LSM 的持久化文件，内部按块组织：Data Block 存实际 key-value 数据，Index Block 记录 Data Block 的 key 范围用于定位，Filter Block 存放 Bloom Filter 位图用于判断某个 key 是否可能存在于该文件。查询时先查 Filter Block 的 Bloom Filter，如果 key 不存在则直接跳过该 SSTable，避免不必要的读盘；若可能存在，再经 Index Block 定位到 Data Block 并读入。Block Cache 是内存中的块缓存，把最近读过的 Data/Index 块缓存起来，避免重复读盘。三者协同：Bloom Filter 减少无谓的块读取，Index 加速定位，Block Cache 降低重复读盘，共同显著降低 LSM 的读放大与 IO 开销。

协同的核心是"层层减少不必要的 IO"：Bloom Filter 跳过不存在的文件、Index 精确定位、Block Cache 复用已读块，配合起来缓和 LSM 读放大高的劣势。

• 列存按列连续存储，同列数据相似度高利于压缩
• RLE/字典/Delta 编码的特点与适用数据
• 压缩后数据可直接在编码域向量化计算

列式存储把同一列的数据连续存放，同列数据往往值域小、重复多、相关性高，非常适合压缩。Run-Length（游程编码）压缩连续重复值，适合低基数/重复多的列；Dictionary（字典编码）把值映射为较短的整数 ID，适合低基数枚举；Delta（增量编码）存相邻值的差值，适合有序/时间序列。与向量化契合的原因是：压缩后数据仍是连续的同质数组，很多运算可以在编码域直接进行（如对字典 ID 做比较、对 RLE 做跳跃式聚合），无需先解压成行式；而且列存天然提供连续列指针，向量化核可直接批量处理。因此列存 + 高效压缩 + 向量化执行互相增益，是 OLAP 引擎性能的基础。

契合点在于列存提供"连续同质数据"，压缩进一步降低数据量并保持连续性，向量化在编码域直接批量运算，三者叠加降低 IO 与内存带宽、提升吞吐。

• Redo 保证已提交事务的持久性（WAL），Undo 用于回滚与 MVCC 版本链
• MVCC 版本链依赖 Undo，崩溃恢复依赖 Redo
• Redo 物理（记录页/偏移的变更，可重放）、Undo 逻辑（记录逆向操作，需结合上下文）

Redo Log 记录已提交事务对数据库页所做的物理修改（如"在某页某偏移写入什么数据"），用于崩溃恢复：崩溃后重放 redo 把已提交事务的修改恢复到磁盘，保证持久性（WAL 原则）。Undo Log 记录撤销操作（如"删除某记录"或"把某字段改回旧值"），用于事务回滚和 MVCC 的版本链：MVCC 通过 Undo 保存旧版本，让读事务能读到一致性快照；回滚时按 Undo 撤销改动。为什么 Redo 是物理、Undo 是逻辑：Redo 必须能在崩溃后精确重放页的最终状态，物理记录（页+偏移）可重复、幂等，不依赖其他数据；Undo 需要结合当前版本链和上下文才能正确恢复到旧版本，逻辑上描述"如何撤销"，且可能涉及多版本判断，因此是逻辑的。

Redo 解决"已提交的不能丢"（物理、可重放），Undo 解决"未提交的要能回滚、并发读要一致"（逻辑、结合上下文），二者分工互补，共同支撑崩溃恢复与 MVCC。

• AHI 是 InnoDB 对高频访问页构建的哈希索引，加速点查
• Bloom Filter 用于 LSM 判断 key 是否存在，避免无效读盘
• AHI 的内存占用、维护成本、命中率依赖访问模式

自适应哈希索引（AHI）是 InnoDB 在 Buffer Pool 中根据频繁访问的索引页自动构建的哈希索引，让点查通过哈希直接定位而非逐层走 B+Tree，从而加速点查；其边界的代价是：只对"访问模式稳定且集中"的 key 构建，构建和更新需要维护开销，且占用内存（Buffer Pool 的一部分），当访问模式变化（如负载变为全表扫描、随机大范围访问）时命中率会骤降，甚至可能因维护成本高于收益，InnoDB 默认据此自适应开关。Bloom Filter 是 LSM 中用于判断一个 key 是否可能存在，避免对不存在 key 的无效块读取；其边界是存在误判（false positive），且需要随 SSTable 重建/维护。二者都用于加速点查，但 AHI 依赖稳定的热点访问模式，Bloom Filter 依赖"过滤不存在的 key"来减少读盘。

AHI 的边界是"用内存换热点命中、但命中率随访问模式波动且维护有成本"；Bloom Filter 的边界是"用少量误判换大量无效 IO 的规避"。

• Page 级压缩、前缀压缩、字典编码的适用场景与成本
• 列存利于压缩、行存压缩受限
• 随机更新与压缩的矛盾及解决（页内重解压、日志式更新、批处理）

Page 级压缩对整个数据页做压缩（如 LZ4、ZSTD），通用但压缩/解压有 CPU 成本，适合不常更新的数据；前缀压缩利用相邻 key 共享前缀省空间，适合有序索引；字典编码把重复值映射为短 ID，适合低基数列，列存下尤其有效。行存数据分散、列间差异大，压缩率相对低；列存同列连续、相似度高，压缩率高。压缩与随机更新的矛盾在于：压缩后数据无法原地定位修改，更新需先解压页、改完再重新压缩，代价高。解决办法包括：压缩时保留页级索引/偏移，只在页内解压那一块再重压缩；对更新密集的数据采用日志式/追加式更新（如 LSM 的追加）避免原地修改；或对热点数据不压缩、对冷数据压缩，做冷热分层。

压缩的本质是"用 CPU 换空间与 IO"，随机更新与压缩的矛盾在于"原地修改与编码后的非随机访问"冲突，用分层、日志式更新或按需解压来缓解。

• 聚簇索引（主键索引）叶子存整行数据
• 二级索引叶子存主键值，查询需回表
• 覆盖索引避免回表

InnoDB 是索引组织表（IOT），数据按主键聚簇存储：主键对应的聚簇索引（Clustered Index）的叶子节点直接存整行数据，因此按主键查询一次索引就能取到整行。二级索引（Secondary Index）的叶子节点存的是索引列的值 + 主键值，而不存整行；当查询通过二级索引定位到主键后，需要再根据主键回到聚簇索引去取整行数据，这一步称为"回表"（secondary lookup / table lookup）。回表会多一次索引访问，增加 IO。若查询所需的列全部包含在二级索引中，则无需回表，称为覆盖索引（covering index），可显著提升查询性能。

聚簇索引决定了数据物理组织，二级索引+回表是"用索引列定位主键再取行"的流程，覆盖索引通过让所需列都在索引中避免回表。

• 页大小与磁盘 IO 块/文件系统块的对齐
• 页大小对顺序扫描、随机点查、缓存率的影响
• 页大小与压缩、索引、行大小的关系

数据库以页为单位读写磁盘，页大小（如 4K/8K/16K）必须与磁盘扇区、文件系统块对齐（未对齐会导致一次 IO 跨越多个物理块，产生额外 IO）。较大的页（如 16K）单次能读更多数据，顺序扫描吞吐高、缓存命中率高（每页覆盖更多行），但随机点查时每次读入更多数据、浪费 IO 且缓存更易被大页挤占；较小的页（如 4K）随机点查更精确、缓存更细粒度，但顺序扫描吞吐低、页头开销占比高。页大小还应与行大小、索引扇出匹配（页越大索引扇出越多、树越矮）。因此页大小是"顺序吞吐/缓存率 vs 随机点查精度/缓存粒度"的权衡，需结合存储介质与负载设置。

页大小影响一次 IO 覆盖的数据量、缓存粒度与索引扇出，其与 IO 块对齐则避免物理 IO 的碎片化；工程上需按负载与介质权衡。

• checkpoint 记录已刷盘的最新 LSN，作为 redo 重放起点
• redo 从 checkpoint 的 LSN 开始重放已提交修改
• undo 依据 undo log 回滚崩溃时未提交的事务

崩溃恢复时，先找到最近一次 checkpoint 记录的位置，checkpoint 记录了已刷盘到磁盘的最新日志 LSN（RedoLSN），因此 redo 只需要从该 checkpoint 的 LSN 开始向后重放，而不必从头重放所有日志，从而缩短恢复时间。重放过程中，对属于已提交事务的修改应用（redo 到磁盘）；同时，崩溃时可能还有未提交的事务，这些事务的修改虽然被 redo 重放到了内存/磁盘，但逻辑上无效，需要依据这些事务的 undo log 进行回滚，把它们的修改撤销，恢复到事务开始前的状态。因此：checkpoint 确定 redo 起点，redo 保证已提交持久性，undo 回滚未提交事务，三者共同完成崩溃恢复。

checkpoint 本质是"已持久化的进度标记"，redo 从它开始减少重放量，undo 负责清理未提交事务的残留，恢复过程遵循"先重放 redo 再回滚 undo"。

• Bw-Tree 用无锁/日志式 + 增量更新解决并发与缓存问题
• HOT 针对写放大/缓存友好
• 新型索引工程落地受限的原因（复杂度、兼容性、成熟度）

Bw-Tree（微软 Hekaton/内存数据库）针对 B+Tree 的并发瓶颈，采用无锁的 CAS（比较并交换）和 delta 更新（delta chain）机制，避免加锁和页内原地修改，从而提升多核并发，并改善缓存友好性；HOT（Highly Optimized Tree, 慕尼黑研究）针对 B+Tree 的写放大和缓存不友好问题，通过节点内紧凑布局和减少分裂来降低写放大、提升缓存局部性。这些新型索引针对 B+Tree 的并发、缓存、写放大问题做了改进，但工程落地有限，原因包括：实现复杂度高（无锁算法、故障恢复、持久化困难）、与现有数据库的事务/恢复机制集成复杂、兼容性和生态成熟度不足、以及现代硬件（更大缓存、更快的锁）使 B+Tree 的简单性与成熟度仍占优。因此多数生产数据库仍以 B+Tree 为主。

新型索引都针对 B+Tree 的某类缺陷，但"正确性 + 可维护性 + 与现有恢复/事务体系集成"的工程成本远高于其性能收益，导致落地受限。

• 用机器学习模型拟合 key 到位置映射，替代 B+Tree 查找
• 关键点：模型误差需要边界保证（如最后一段线性扫描）
• 适用范围与工程落地现状

学习型索引（Learned Index）由 Kraska 等人在《The Case for Learned Index Structures》中提出，核心思想是用机器学习模型（如分段线性/神经网络）学习 key 与数据位置（页偏移）的映射关系，替代传统 B+Tree 的逐层二分查找，从而减少查找开销、提升缓存友好性。关键工程点是：模型预测必须保证误差有界，即预测位置与实际位置之差有上限，通常用最后一段较小的线性扫描或二次索引来覆盖误差，保证正确性。其适用范围主要是只读、key 分布可学习、静态或低更新率的数据（如只读查找、日志、CDN 缓存）；对高频更新、key 分布剧烈变化、需要事务与恢复的场景并不适合。工程进展上，目前仍以研究为主，生产数据库采用有限，因为正确性边界、更新维护、与现有存储/并发集成成本高。

学习型索引的收益来自"用模型替代二分查找"，但正确性依赖误差上界，且更新与维护抵消了部分优势，因此适合静态只读数据。

• NVMe 极低延迟、高 IOPS 使随机 IO 与顺序 IO 差距缩小
• PMEM 可字节寻址、持久，改变 WAL/fsync 与页缓存假设
• 对缓冲池、WAL、checkpoint 设计的影响

传统存储引擎假设磁盘随机 IO 远慢于顺序 IO，因此用页缓存、WAL、顺序写策略来规避随机 IO。NVMe SSD 的延迟和 IOPS 大幅提升，随机与顺序 IO 差距显著缩小，使随机读、更小的 IO 粒度、更频繁的刷盘变得可行，页缓存与缓冲策略的收益下降、WAL 的组提交/顺序写优化边际收益变小。持久内存（PMEM）可直接字节寻址且持久，理论上可让数据直接持久化、减少 WAL 与 fsync 的必要性（崩溃后无需重放），也改变页缓存假设（数据无需先写内存再刷盘）。但 PMEM 的写入带宽、持久化屏障（如 clflush/pfence）仍有开销，且与现有缓冲池、WAL 结构集成复杂，工程上多采用"混合"方案（PMEM 作为持久缓存或 WAL 介质）。总体上新硬件让"顺序 vs 随机"和"WAL/fsync"的旧假设被重新审视。

新硬件压缩了传统分层（内存缓存 + 磁盘 + WAL）的优化空间，但不同硬件各有新约束（持久化屏障、带宽、寿命），工程上需重新设计而非简单沿用。

• Hash 索引适合等值点查、O(1) 平均
• 跳表支持有序遍历与范围查询、O(log n)
• 内存数据下两者无 IO 约束，关注并发与缓存

内存数据库把数据放在内存，索引无需考虑磁盘 IO，重点在并发与缓存。Hash 索引通过哈希直接定位 key，等值点查平均 O(1)，适合点查密集型负载（如 Redis 的哈希、按主键查找），但哈希无序，无法高效支持范围查询和排序。跳表（Skip List）是带随机指针的有序链表，支持 O(log n) 的查找、插入、删除和有序范围遍历，且天然支持并发（多重链表指针局部更新），适合需要有序访问和范围查询的场景（如 Redis 的 ZSET 有序集合、InnoDB 的内存辅助结构）。在内存数据库里，常将 Hash 索引用于主键/等值快速访问、跳表或有序结构用于范围查询与排序，二者按查询形态选择。

Hash 换"等值 O(1)"但失去有序性，跳表换"有序 O(log n)"支持范围，内存库按查询形态（点查 vs 范围）选择，并兼顾并发与缓存。

• 对象存储高延迟、只追加/不可变语义、按对象寻址
• 写入放大（小写需整对象重写）
• 混合存储：热数据在本地、冷数据在对象存储

对象存储（如 S3）延迟高（首次访问毫秒到百毫秒级）、按对象（而非页）寻址、对象不可变（修改需重写整个对象），因此若直接作为数据库的行级/页级存储层，会产生高延迟（每次访问都要网络往返）和写放大（小量更新也要重写整个对象）。挑战还包括缺乏细粒度随机写、一致性模型与事务支持复杂。混合存储方案缓解：把热数据放在本地 SSD/内存（低延迟、细粒度随机读），冷数据/归档数据放在对象存储（容量大、成本低），通过分层与后台迁移（如冷热自动分层、把不常访问的数据压缩打包成对象）实现；查询时对冷数据做批量扫描，把对象读入本地后处理。这样既利用对象存储的廉价与容量，又避免其高延迟与写放大对热路径的影响。

对象存储的高延迟与"按对象不可变"语义与数据库的页级随机读写冲突，混合方案用"热数据本地、冷数据对象存储 + 分层迁移"来规避。

• 页内布局：目录/插槽数组 + 数据区，记录可移动
• 更新导致的碎片（页内空洞、行迁移）
• 碎片整理与页合并对更新密集负载的影响

数据库页内通常采用"布局目录（slot / 插槽数组）+ 数据区"的结构：页头是槽数组，每条记录在数组中有一个槽指针指向记录在数据区的位置，这样记录可以在页内移动（如删除、压缩后移动），槽指针保持稳定。更新若改变行长度，可能使页内出现空洞和碎片（行变长需要新位置，旧位置成为碎片），除页净空间外还会导致行迁移（行被移到别的页，原处留转发指针）。页内碎片整理（把碎片合并、压缩剩余空间）与页合并（把相邻低占用页合并）能提高空间利用率、减少页数，但对更新密集负载可能带来额外开销：碎片整理要移动记录并更新索引指针，合并要读写多个页，频繁的整理/合并会增加 CPU 与 IO、甚至与并发访问竞争。因此需要根据负载权衡：更新密集时减少频繁整理，改为周期性/后台整理，或预留足够净空间避免碎片加剧。

槽数组+数据区让记录可移动以支持整理，但碎片整理与合并本身有成本，更新密集负载下要权衡"空间利用率"与"整理/合并的 CPU、IO 与并发开销"。