😄 Joker's Digital Garden

B 树和 LSM 树的原理对比

6 min read

Recent

See 244 more →

这是一份关于 B 树（B-Tree）与 LSM 树（Log-Structured Merge-Tree）基本原理的 Markdown 文档，包含了 Mermaid 流程图对比。

数据库存储引擎核心：B 树 vs LSM 树

在现代数据库中，存储引擎通常分为两大流派：以 B 树为代表的“原地更新”流派（如 MySQL InnoDB）和以 LSM 树为代表的“追加写入”流派（如 LevelDB, RocksDB, HBase）。

1. B 树 (B-Tree) - 读优化

B 树是一种多路平衡搜索树，旨在保持数据有序并允许在对数时间内进行查找、顺序访问、插入和删除。

基本原理

  • 结构：由根节点、内部节点和叶子节点组成。每个节点包含多个 Key 和指向子节点的指针。
  • 原地更新 (Update-in-place)：当数据修改时，直接定位到对应的磁盘页（Page）并覆盖原数据。
  • 磁盘友好：节点大小通常与磁盘页（如 4KB 或 16KB）对齐，减少 I/O 次数。

Mermaid 原理图

graph TD
    Root["根节点: [100 | 200]"]
    Root --> Node1["内部节点: [20 | 50]"]
    Root --> Node2["内部节点: [120 | 150]"]
    Root --> Node3["内部节点: [220 | 280]"]

    Node1 --> Leaf1["叶子节点(Page): 10, 15"]
    Node1 --> Leaf2["叶子节点(Page): 25, 30"]
    Node1 --> Leaf3["叶子节点(Page): 60, 70"]

    style Root fill:#f9f,stroke:#333
    style Leaf1 fill:#bbf,stroke:#333
    style Leaf2 fill:#bbf,stroke:#333
    style Leaf3 fill:#bbf,stroke:#333

2. LSM 树 (LSM-Tree) - 写优化

LSM 树不是一棵严格的树，而是一种利用顺序写性能远高于随机写的存储架构。

基本原理

  • MemTable：在内存中维护一个有序结构（如跳表或红黑树）。
  • WAL (预写日志)：数据先写日志，防止宕机丢失。
  • SSTable (Sorted String Table)：内存写满后，将其作为有序文件“冲刷”（Flush）到磁盘。
  • 分层合并 (Compaction)：由于数据是追加写的，旧数据不会被覆盖，后台会定期将多个小文件合并成一个大的有序文件，并清理旧版本。

Mermaid 原理图

graph TD
    Write((写入请求)) --> WAL

    subgraph Disk_Area ["持久化存储 (Disk)"]
        WAL[("WAL 预写日志<br/>(顺序追加文件)")]
        
        subgraph SST_Layers ["SSTable 分层存储"]
            L0["Level 0: [SST 1] [SST 2]"]
            L1["Level 1: [Merged Sorted SST]"]
            L2["Level 2: [Larger Sorted SST]"]
        end
    end

    subgraph Memory_Area ["易失性存储 (Memory)"]
        MemTable["MemTable<br/>(有序跳表/树)"]
    end

     刷盘流向
    MemTable -- "Flush (溢写)" --> L0
    L0 -- "Compaction (合并)" --> L1
    L1 -- "Compaction (合并)" --> L2

    %% 恢复流向
    WAL -- "崩溃恢复时重放" --> MemTable

    style Memory_Area fill:#e1f5fe,stroke:#01579b
    style Disk_Area fill:#fff3e0,stroke:#e65100
    style WAL fill:#ffccbc,stroke:#bf360c

3. 核心对比

特性B 树 (B-Tree)LSM 树 (LSM-Tree)
数据更新方式原地更新 (In-place Update)追加写入 (Append-only / Log-structured)
主要存储介质磁盘页 (Pages)内存表 + 分层有序文件 (SSTables)
写性能较慢（随机写、涉及页分裂和磁盘寻道）极快（顺序写内存 + 顺序异步刷盘）
读性能极快（点查询路径短，无需多文件合并）较慢（可能需要检索多个文件，配合布隆过滤器使用）
空间碎片存在（页内填充不满）存在（过期数据需等待合并时清理）
典型应用关系型数据库 (MySQL, PostgreSQL)NoSQL/大数据 (Cassandra, RocksDB, TiDB)

4. 总结与联系

  • B 树 就像一本厚字典：为了找一个词，你翻到对应的那一页直接看。如果词义变了，你拿橡皮擦掉在原位改写。
  • LSM 树 就像一堆日记本：新的记录永远写在当天的最后。为了找某个记录，你得先看今天的日记，没找到再翻昨天的。为了不让日记本太多，你会定期把几天的日记整理（Merge）成一本索引完美的书。

为什么布隆过滤器常用于 LSM 树？ 正如文档之前提到的，LSM 树由于数据散落在不同的 SSTable 文件中，查询一个不存在的 Key 时可能需要扫描所有文件。布隆过滤器可以在访问磁盘前告诉你“这个 Key 绝对不在这些文件里”，从而极大地弥补了 LSM 树读性能的短板。

Graph View