B Tree 与 LSM-Tree 存储引擎深度工程实战：从 InnoDB 到 RocksDB 的完整存储结构链路

前言

存储引擎是数据库系统的核心组件，它决定了数据如何组织、存储和检索。在关系型数据库领域，B+Tree 是 MySQL InnoDB、PostgreSQL 等引擎的根基；而在 NoSQL 和新型数据库中，LSM-Tree 则是 RocksDB、LevelDB、HBase、Cassandra 的标配。本文将深入两种结构的每个实现细节，分析其工程权衡，并展望混合存储引擎的未来趋势。

1. B+Tree 结构本质

B+Tree 的所有数据都存储在叶子节点，叶子节点通过链表串联：

// InnoDB B+Tree 节点最小单元 = 1个Page = 16KB
struct Page {
    PageHeader  header;     // 38字节，含 page_id/prev/next/level
    Infimum     infimum;    // 最小记录（虚拟）
    UserRecords records;    // 所有用户记录，按主键有序排列
    Supremum    supremum;   // 最大记录（虚拟）
    PageDir     directory;  // page directory，每4-8条记录一个槽
};

// 典型参数：页大小16KB，单向指针8字节
// 假设主键8字节 + 行数据1KB
// 叶子节点存储约 16KB / (8B + 1KB) ≈ 15条记录
// 非叶节点存储约 16KB / (8B主键 + 8B page_id) = 1024条指针
// 3层 B+Tree 支持 1024² × 15 ≈ 1500万条记录
// 4层 B+Tree 支持 1024³ × 15 ≈ 150亿条记录

2. InnoDB 聚簇索引与二级索引

InnoDB 的索引组织方式：

• 主键索引（聚簇索引）：叶子节点存储完整的行数据。通过主键检索直接获取行。
• 二级索引（辅助索引）：叶子节点存储索引列 + 主键值。查询需回表（Bookmark Lookup）。
• 覆盖索引：当查询需要的列全在二级索引中时，无需回表，极大提升性能。

-- 无 Back Buffering 的二级索引查询（需回表）
EXPLAIN SELECT * FROM t WHERE name = 'Alice';
-- type: ref（使用二级索引），Extra: NULL（需要回表）

-- 覆盖索引查询
EXPLAIN SELECT id, name FROM t WHERE name = 'Alice';
-- type: ref，Extra: Using index（无需回表）

3. InnoDB Buffer Pool 管理

InnoDB 用 Buffer Pool 缓存磁盘数据页，避免每次访问磁盘：

• LRU 链表变体：分为 young（热数据）和 sub-old（冷数据）两段。新读取的页先进入 old 区头部，第二次访问且停留超过 innodb_old_blocks_time（默认 1000ms）才升 young 区。避免全表扫描污染 cache。
• Change Buffer（Insert Buffer 进化版）：二级索引的非唯一变更先写入 Change Buffer（内存中的 B+Tree），后续由 background merge 线程合并到磁盘页。将随机写转换为批量写。
• Double Write Buffer：写磁盘 page 前先在连续区域写入副本，防止 partial page write。

4. InnoDB WAL 与崩溃恢复

WAL（Write-Ahead Logging）保证崩溃可恢复：

1. 修改 Buffer Pool 中的页，生成 redo log（物理日志："page 123 offset 40 修改为新值"）
2. redo log 写入 log buffer → 刷盘 innodb_flush_log_at_trx_commit
3. 修改过的页成为脏页，由 page cleaner 线程异步刷盘
4. 崩溃后根据 redo log 前滚（redo 已提交事务）和 undo log 回滚（未提交事务）

两个关键 LSN：

• Log sequence number（LSN）：当前 redo log 写入位置
• Flushed_up_to_lsn：已刷盘的 redo log 位置
• Checkpoint_lsn：已刷脏页对应的 redo 位置

5. LSM-Tree 结构原理

LSM-Tree（Log-Structured Merge-Tree）将随机写转为顺序写：

// LSM-Tree 核心组件（RocksDB 实现）
struct LSMTable {
    MemTable *active;         // 活跃内存表（Writable，接收写入）
    MemTable *immu;           // 不可变内存表（正在 flush）
    SSTable l0[kMaxL0File];   // Level 0：无序，SST 文件间 key 可能重叠
    SSTable li[kMaxLiFile];   // Level i（i>0）：每个 Level 内有序，文件间不重叠
    WAL *wal;                 // 写前日志
    Manifest *manifest;       // MANIFEST 文件记录各 Level 文件清单
};

// MemTable 实现：SkipList（默认）
// 支持并发无锁写，range query 友好
struct SkipListMemTable {
    Node *head;
    int max_level;
    Comparator cmp;
    Arena *arena;             // 内存池
};

6. SSTable 文件格式

RocksDB SSTable 结构：

┌─────────────────────────────────┐
│ Data Block 1   (压缩后的 KV 数据) │
│ Data Block 2                     │
│ ...                              │
│ Meta Index Block (meta 索引信息) │
│ Index Block   (data block 索引)  │
│ Filter Block  (布隆过滤器)       │
│ Footer        (48字节元信息)     │
└─────────────────────────────────┘

// 读取路径：Bloom Filter → Index Block 定位 → Data Block 二分查找
// Bloom Filter 误判率：bits_per_key=10 时约 1%

7. Compaction 策略

Compaction 是 LSM-Tree 最耗资源的操作，主要有三种策略：

• Size-Tiered（RocksDB 默认策略之一）：当同一 Level 的 SST 文件总大小达到阈值，触发 Compaction。写到下一 Level 时合并为有序段。写放大较低，但读放大较高。适合写多读少。
• Leveled（LevelDB 默认）：每个 Level 内 SST 文件不重叠，只维护一个 sorted run。当 Level i 文件数超阈值，将其中与 Level i+1 重叠的文件 Compaction 到 i+1。读放大最低（均匀场景），但写放大较高。
• Universal 策略：Size-Tiered 的变体，根据大小比值触发。Level 0 永远无序，其他按大小比值合并。
• FIFO Compaction：不 Compaction，按 TTL 直接删除最老文件。适合纯缓存场景。

8. 读写放大计算

写入放大（Write Amplification）和读取放大（Read Amplification）是 LSM-Tree 的核心指标：

// 假设每层大小放大因子 T=10（Leveled 策略）
// 写放大 = 1 + 1/T + 1/T + ... ≈ T = 10x
// 读放大 = Level 数 = log_T(N/data_block_size)
// 空间放大 = 1 + 1/T = 1.1x（Size-Tiered 可达 1.5x+）

// RocksDB 调优
options.compaction_style = kCompactionStyleLevel;
options.write_buffer_size = 64 * 1024 * 1024;  // MemTable 大小
options.max_write_buffer_number = 3;            // 最多 3 个 MemTable
options.level0_file_num_compaction_trigger = 4; // L0 达到 4 个 SST 触发 Compaction
options.target_file_size_base = 64 * 1024 * 1024; // L1 SST 目标大小
options.bytes_per_sync = 1048576;               // 每 1MB 同步 FLUSH

9. B+Tree vs LSM-Tree 对比

10. 混合引擎与未来趋势

现代存储引擎越来越多地融合两种结构的优势：

• InnoDB 的 Change Buffer：本质是将二级索引的随机写先转为有序合并再刷盘，类似微型 LSM-Tree。
• Bw-Tree（微软 Hekaton）：B+Tree 变体，用 Delta 更新 + CAS 替换写时复制（COW），减少锁竞争。
• TerarkDB / FASTER：混合索引，热路径用 B+Tree/Fingerprint Tree，冷数据用 LSM-Tree。
• 元数据 B+Tree + 日志数据 LSM-Tree：PostgreSQL 15+ 讨论的混合方案。

选择引擎时，关键看工作负载特征：读密集型适合 B+Tree，写密集型适合 LSM-Tree，混合场景需要细致调优。

11. 总结

B+Tree 和 LSM-Tree 看似是两个对立的存储范式，实则各有优劣且正在互相借鉴。理解其内部结构——InnoDB 的 Pool 管理和 Change Buffer、RocksDB 的 Compaction 策略和 Bloom Filter——是构建高性能存储系统的必备基础。在实际工程中，往往不是二选一，而是将两者优势结合，适应不同的查询和写入模式。