存储引擎实现

存储引擎是数据库最核心的组件，直接决定了数据库的性能特征。本节从实现者的角度，剖析存储引擎如何解决数据存储、索引构建和并发控制这三个根本问题。

页与缓冲池

磁盘 I/O 的根本约束

理解存储引擎的设计，首先要理解磁盘 I/O 的特性。现代机械硬盘的随机访问延迟约 10ms，顺序访问约 0.1ms，差异达到 100 倍。而内存的访问延迟约 100ns，与磁盘相比又差了 5 个数量级。这意味着一次随机磁盘 I/O 的时间，足以执行数百万条 CPU 指令。

因此存储引擎设计的首要原则就是减少磁盘 I/O 次数。有两个基本策略：将数据组织成连续的块以支持顺序读取，以及在内存中缓存热点数据。

页的结构

数据库将磁盘空间划分成固定大小的块，称为页（page）或块（block）。InnoDB 的默认页大小是 16KB，PostgreSQL 默认 8KB。选择合适的页大小需要权衡：页越大，顺序读取效率越高，但单次 I/O 的数据传输量也越大；页越小，内存利用率越高，但树的高度会增加。

一个典型的数据页包含以下部分：文件头（File Header）记录页的校验和、页号、上一页下一页指针；页头（Page Header）记录页内记录数量、自由空间位置；最小记录（Infimum）和最大记录（Supremum）是虚拟记录，作为页内记录的边界；用户数据区存储实际的记录；自由空间（Free Space）是页内未使用的空间；页尾（File Trailer）存储校验和，用于检测页面是否损坏。

记录的行格式

InnoDB 支持多种行格式。COMPACT 格式下，一条记录包含变长字段长度列表、NULL 标志位、记录头信息、列数据。记录头信息包含删除标志、记录类型、下一记录指针等信息。通过记录头中的 next_record 指针，页内的所有记录串联成一个单向链表，这是实现顺序扫描的基础。

DYNAMIC 和 COMPRESSED 格式针对长字段做了优化。当列的数据长度超过 768 字节时，会将数据存储到溢出页（overflow page），原页只保留前 768 字节和指向溢出页的指针。这避免了长字段挤占页空间，使页能容纳更多记录，从而提高缓存利用率。

缓冲池管理

缓冲池（Buffer Pool）是内存中缓存数据页的区域。当需要访问某个页时，首先检查缓冲池是否已缓存该页。如果命中（cache hit），直接访问内存，省去一次磁盘 I/O。如果未命中（cache hit），需要从磁盘读取页到缓冲池，可能需要淘汰某个已有的页。

缓冲池的管理核心是页表（Page Table），它记录每个页是否在缓冲池中、在缓冲池的哪个位置、是否脏页（被修改但未刷盘）。页表本身占用可观的内存，InnoDB 使用哈希表实现，O(1) 时间定位。

页淘汰策略最经典的是 LRU（Least Recently Used），但朴素的 LRU 有两个问题：全表扫描会污染缓存，预读的页可能不会被使用。InnoDB 采用改进的 LRU：将 LRU 链表分为 young 区域和 old 区域，新页先插入 old 区域的头部，只有被第二次访问时才移入 young 区域。这样全表扫描加载的大量页只会停留在 old 区域，不会挤掉 young 区域的热点数据。

脏页刷盘策略

被修改的页称为脏页，需要刷回磁盘才能持久化。刷盘策略涉及性能和持久化的权衡。过于频繁刷盘会增加 I/O 负担，刷盘不及时则崩溃恢复耗时过长。

InnoDB 采用多种刷盘策略：redo log 满时主动刷盘，这是为了避免 redo log 循环写入覆盖未刷盘的页；缓冲池不足时淘汰脏页触发刷盘；Master Thread 定期刷盘；通过 innodb_io_capacity 控制刷盘速率，避免影响正常业务 I/O。

B+ 树索引

为什么是 B+ 树

索引的本质是用空间换时间，通过额外的数据结构加速查找。理想的索引结构应该支持高效的范围查询和点查询，同时保持较低的树高以减少 I/O 次数。

二叉查找树（BST）在最坏情况下会退化为链表，树高 O(n)。平衡二叉树（AVL）保证了 O(log n) 的高度，但每个节点只能存一个关键字，树高仍然较高。B 树通过允许一个节点存储多个关键字，大大降低了树高。B+ 树是 B 树的变体，将所有数据存储在叶子节点，非叶子节点只存储索引，这进一步增加了每个节点能容纳的关键字数量。

假设页大小 16KB，每个索引项 8 字节（关键字）+ 8 字节（指针），一个页可以存储约 1000 个索引项。一棵三层 B+ 树可以存储 10 亿条记录，而树高只有 3，意味着任何查询最多 3 次 I/O。这就是 B+ 树成为数据库索引标准结构的原因。

B+ 树的结构

B+ 树的节点是页。非叶子节点存储索引项（key, child_ptr），叶子节点存储完整记录。所有叶子节点通过双向链表连接，支持范围查询的顺序访问。每个节点维护一个关键字数组，关键字按升序排列。对于非叶子节点，key[i] 是子树 i 中所有关键字的左边界。

查找从根节点开始，通过二分查找定位到合适的子树指针，递归向下直到叶子节点。在叶子节点中继续二分查找，如果找到匹配的关键字则返回记录。

插入与分裂

插入新记录时，首先定位到目标叶子节点。如果该节点有足够空间，直接插入并保持有序。如果节点已满，需要分裂：将节点中的一半记录移动到新创建的节点，然后将新节点的最小关键字提升到父节点。如果父节点也满了，递归向上分裂，甚至可能分裂根节点，使树高增加 1。

分裂的策略会影响树的平衡性。如果总是从中间分裂，能较好地保持树的平衡，但可能产生大量半满节点。某些实现会尝试"借记录"给兄弟节点，只有兄弟节点也满了才分裂，这能提高空间利用率。

删除与合并

删除记录时，如果删除后节点的记录数低于下限（通常是容量的一半），需要从兄弟节点"借"记录或者与兄弟节点合并。借记录是将兄弟节点的一个记录移动到当前节点，同时更新父节点的索引项。合并是相反的操作，将两个节点的记录合并到一个节点，并删除父节点对应的索引项。

合并可能导致父节点记录数不足，递归触发父节点的借或合并操作，最坏情况下树高减少 1。频繁的合并和分裂会导致性能抖动，这是 B+ 树的一个缺点。

辅助索引

主键索引的叶子节点存储完整记录，辅助索引的叶子节点存储主键值。这意味着通过辅助索引查询时，需要先找到主键值，再通过主键索引回表查询完整记录。这多了一次索引查找，也就是"回表"。

为了避免回表，某些场景可以使用覆盖索引：让索引包含查询所需的所有列，这样辅助索引就能直接返回结果，无需回表。复合索引的列顺序很重要，遵循最左前缀原则：索引 (A, B, C) 可以支持查询条件 A、AB、ABC，但不能支持 B 或 BC。

LSM 树

写优化的替代方案

B+ 树是读优化的结构，随机读取和范围查询都很高效，但写入需要随机定位叶子节点并可能触发分裂，写入性能受限。LSM 树（Log-Structured Merge Tree）采用相反的设计：将随机写入转换为顺序写入，极大地提升写入性能，代价是牺牲一定的读取性能。

LSM 树的核心思想是将数据分成多层，从上到下容量递增。写入直接操作内存中的 MemTable，这是有序的内存表，通常是跳表实现。当 MemTable 达到阈值时，将其冻结为不可变的 MemTable，后台线程将其刷盘成 SSTable（Sorted String Table）。SSTable 是有序的磁盘文件，支持快速查找。后台线程定期将多层 SSTable 合并（Compaction），清理过期数据，减少层数。

MemTable 与 WAL

写入操作首先追加写入预写日志（WAL），这是顺序写，用于崩溃恢复。然后写入 MemTable，这是内存操作，延迟极低。WAL 保证即使系统崩溃，也能通过重放 WAL 恢复 MemTable 的状态。

SSTable 与 Compaction

SSTable 是不可变的磁盘文件，按 key 有序存储。查找时从最新的层开始，每层的 SSTable 通过布隆过滤器（Bloom Filter）快速判断 key 是否存在，如果可能存在则通过二分查找或稀疏索引定位记录。由于 SSTable 不可变，不需要锁，简化了并发控制。

Compaction 是 LSM 树的后台维护任务。当某层的 SSTable 数量或大小超过阈值时，触发合并。Leveled Compaction 策略将 L 层的 SSTable 与 L+1 层有重叠的 SSTable 合并，合并结果写入 L+1 层。Size-tiered Compaction 策略将相似大小的 SSTable 合并成更大的 SSTable。Compaction 清理了被删除或覆盖的数据，控制了读放大（需要检查的 SSTable 数量），代价是写放大（同一个数据可能被多次重写）。

B+ 树 vs LSM 树

B+ 树适合读多写少的场景，索引维护成本低，查询性能稳定。LSM 树适合写多读少的场景，写入性能优秀，但读取可能需要检查多个 SSTable，性能不稳定。HBase、RocksDB 等 LevelDB 衍生系统采用 LSM 树，InnoDB、PostgreSQL 采用 B+ 树。理解两者的差异，有助于针对业务特点选择合适的存储引擎。