问题背景描述

要解决的问题：如何在不同的硬件限制（内存 vs 磁盘）和业务需求（多读 vs 多写 vs 范围查询）下，最快地找到数据？

可以把这个问题拆解为两个维度来理解：

1. 存储介质维度：
   • 内存（RAM）： 访问极快，但空间有限。重点在于算法的CPU计算复杂度（如红黑树、跳表）。
   • 磁盘（Disk/SSD）： 访问慢，IO成本高。重点在于减少磁盘IO次数和利用顺序读写（如B+树、LSM树）。
2. 读写倾向维度：
   • 读多写少： 需要极致的查找速度（B+树）。
   • 写多读少： 需要极致的写入速度（LSM树）。

从存储介质维度来看，可以归类：

底层机制

B+ 树

1. 为什么是 4KB 或 16KB？（物理与系统的契合）

这是为了减少 IO 浪费和利用物理对齐。

• 硬件层： 磁盘驱动器读取数据的最小物理单位是扇区（Sector），传统为 512 字节，现代磁盘（Advanced Format）多为 4KB。
• 系统层： 操作系统管理内存和文件系统的基本单位是页（Page），通常也是 4KB。
• 数据库层（以 InnoDB 为例）： 如果 B+ 树的节点大小（Page Size）不是 4KB 的整数倍，会导致“跨页读取”。例如，如果你定义 Page 为 5KB，为了读这一个 Page，操作系统必须从磁盘读取 2 个 4KB 的物理块，这产生了一次不必要的磁盘 IO。
• 16KB 的选型： 默认选 16KB 而非 4KB，是为了在一次 IO 中加载更多的索引项。虽然 IO 耗时略微增加，但它能显著提升扇出率，让树变得更矮。

2. 树的高度通常是多少？（极致的矮胖设计）

在生产环境中，即使是千万级甚至亿级的数据量，B+ 树的高度通常也只有 3 到 4 层。

• 根节点缓存： 数据库启动后，根节点通常常驻内存。
• 中间节点加载： 第二层节点也极大概率被缓存。
• IO 结果： 实际上定位一行数据，通常只需要 1~3 次磁盘 IO（很多时候甚至只需要 1 次，因为非叶子节点都在内存里）。

3. 能存多少数据？（千万级容量的推算）

我们以 MySQL 默认的 16KB 节点进行推算：

• 非叶子节点： 假设主键为 BigInt（8 字节），加上指针（6 字节），每个节点可存储约 $16KB / 14B \approx 1170$ 个索引项（即分叉数）。
• 叶子节点： 假设每行记录大小为 1KB，一个节点可存 $16KB / 1KB = 16$ 条数据。

存储能力推演：

• 2 层树： $1170 \times 16 \approx 1.8$ 万条数据。
• 3 层树： $1170 \times 1170 \times 16 \approx$ 2190 万条数据。
• 4 层树： $1170 \times 1170 \times 1170 \times 16 \approx$ 250 亿条数据。

直击要害的总结

1. 节点大小设为 4KB/16KB 是为了与操作系统和磁盘扇区对齐，消除 IO 碎片和跨页读写。
2. 3 层高度 就能容纳约 2200 万行 数据，这使得查找任意一条记录的磁盘访问次数被严格控制在 3 次以内。
3. 结论： 这种设计让 B+ 树在海量数据下依然保持了极其稳定的 $O(\log N)$ 查询性能，且底数（分叉数）非常大，极大地减少了磁盘寻道时间。

这个问题直击数据库优化的核心。在 B+ 树的物理结构下，主键的选择直接决定了数据的写入成本和存储碎片。

1. 核心差异：有序 vs 无序

B+ 树本质上是一个有序的平衡索引结构。

• 自增 ID： 是单调递增的，新数据总是按顺序排列。
• UUID： 是随机生成的，新数据在逻辑位置上是乱序的。

2. 对写入性能的影响：顺序写 vs 随机写

自增 ID（顺序写入）

• 操作： 每次新记录插入，都会追加在当前 B+ 树最后一个叶子节点的末尾。
• 结果： 磁盘是顺序写。当一个页（Page）写满后，系统自动开辟一个新页继续写。
• 效率： 写入效率极高，几乎不涉及已满页面的变动。

UUID（随机写入）

• 操作： 每条新记录可能被插入到 B+ 树中间的任何位置。
• 结果： 磁盘是随机写。为了把数据塞进已经排好序的中间位置，数据库必须先查找到对应的 Page，并将其加载进内存。
• 效率： 极其低下，随着数据量增大，磁盘 IO 会成为巨大瓶颈。

3. 致命杀手：页分裂 (Page Split)

这是 UUID 导致性能崩溃的根源。

• 页分裂过程： 当 UUID 指向的那个 Page 已经存满（16KB）时，为了插入新数据，数据库必须把这个 Page 拆分成两个页。
• 连锁反应：
  1. 数据迁移： 移动约一半的数据到新页。
  2. 上层变动： 必须修改父节点（索引页）的指针。
  3. 磁盘碎片： 频繁的分裂会导致页面的填充率极低（通常只有 50%），浪费大量空间。
  4. 大量 IO： 一次简单的插入可能触发多次磁盘 IO 来调整树结构。

4. 存储与查询效率：索引空间与缓存命中率

• 空间占用： UUID 通常是 36 字节的字符串或 16 字节的二进制，而自增 ID（BigInt）仅需 8 字节。UUID 会让索引体积膨胀数倍，导致内存缓存（Buffer Pool）能存下的索引项变少，增加磁盘读取频率。
• 缓存失效： 自增 ID 的局部性非常好（新写的数据都在一起），而 UUID 导致内存中的 Page 被频繁换入换出，缓存命中率大幅下降。

直击要害的总结

1. 自增 ID 保持了 B+ 树的单调递增性，实现了磁盘的顺序追加，最大程度避免了页分裂，保证了最高的写入吞吐量。
2. UUID 导致了频繁的随机 IO 和 页分裂，不仅写入慢，还会产生大量内存碎片，使树变得“虚胖”，严重拖慢读写性能。
3. 工程建议： 永远优先使用自增 ID 或类雪花算法（Snowflake，趋势递增【时钟回拨问题】）作为主键。如果必须存储 UUID，建议将其作为普通唯一索引，而非聚簇索引主键。

LSM Tree

这两个问题直击 LSM Tree 的灵魂。LSM Tree 之所以能拥有极高的写入吞吐量，正是因为它在对待“修改”和“删除”这件事上采取了极其极端的“只读不改”策略。

以下是针对这两个高价值问题的深度解析：

问题一：LSM Tree 是如何处理数据的修改（Update）和删除（Delete）的？

标准答案：

LSM Tree 是一种 Append-only（只追加） 结构。它在物理层面上严禁随机原地修改已写入磁盘的文件。

1. 修改（Update）的本质是“新增版本”：

   当你要把 ID=1 的用户年龄从 20 改为 21 时，LSM 不会去硬盘找旧数据。它直接在当前的内存（MemTable）里写入一条最新的 ID=1, Age=21。在合并（Compaction）之前，磁盘上可能同时存在多个版本的 ID=1，但系统只认可时间戳最新的那一个。

2. 删除（Delete）的本质是“墓碑标记（Tombstone）”：

   删除也不是真的抹掉数据，而是写入一条特殊的记录，标记为“已删除”。这条记录被称为墓碑（Tombstone）。

3. 最终处理（Merge）：

   只有当后台进行 Compaction（合并） 时，系统才会把不同层级的同名 Key 拿出来对比。此时，旧版本的数据会被丢弃，带有墓碑标记的数据连同旧数据会被彻底物理抹除。

价值点深度关联：

这解释了为什么 ClickHouse 的 ReplacingMergeTree 引擎在查询时可能还会看到“重复”或“未删除”的数据。因为 Merge（合并）是在后台异步发生的，在合并完成前，你需要通过 FINAL 关键字或特定的查询逻辑来手动过滤掉旧版本。

问题二：为什么 LSM Tree 读数据经常需要 Bloom Filter（布隆过滤器）配合？

标准答案：

这是为了解决 LSM Tree 的致命缺陷——读放大（Read Amplification）。

1. 读放大的痛苦：

   由于 LSM Tree 的数据散落在内存（MemTable）和磁盘上多个不同层级（Level 0, Level 1…）的文件中。当你查找一个 Key 时，如果它不在内存里，你可能需要依次打开 L0 层的多个文件、L1 层的文件……甚至翻遍所有文件才能确定这个 Key 到底存不存在。

2. 布隆过滤器（Bloom Filter）的作用：

   布隆过滤器是一个极其节省空间的“保镖”，它存在于每个磁盘文件（SSTable）的头部。当你询问“ID=99 在这个文件里吗？”时：

   • 如果它回答 “不在”：那么这个 Key 绝对不在这个文件里。数据库直接跳过，省下了一次昂贵的磁盘读取。
   • 如果它回答 “可能在”：数据库才会真正去读这个文件的内容。

3. 结论：

   布隆过滤器极大地过滤掉了那些无效的随机 IO。如果没有它，LSM Tree 在面对“查询一个不存在的 Key”时，性能会因为扫描大量文件而彻底崩溃。

价值点深度关联：

在 RocksDB 或 HBase 的调优中，调整布隆过滤器的位数（FPR，假阳性率）是优化读性能的最重要手段。如果你发现 ClickHouse 点查（Point Lookup）很慢，通常就是因为命中了太多的文件索引。

直击要害的总结

• 关于增删改： LSM Tree 靠“撒谎”（用新增代替修改）赢得了速度，最后靠“后台勤快”（Compaction）来圆谎。
• 关于读性能： LSM Tree 靠“预判”（布隆过滤器）规避了无效劳动，否则它的读取成本将是 B+ 树的几十倍。

这两个机制完美解释了 LSM 系数据库（如 ClickHouse）为什么“写起来像疯子，读起来像刷子（扫全表快，点查慢）”的物理特性。

跳表

这是一个非常经典的设计决策问题。Redis 的作者 Antirez 曾明确表示，选择**跳表（Skip List）**实现有序集合（ZSet）主要不是因为性能有压倒性优势，而是基于**工程实现、内存开销和查询需求**的综合权衡。

以下是直击要害的标准答案：

1. 范围查询的极致便捷（最核心原因）

Redis 的 ZSet 经常需要执行 ZRANGE 或 ZREVRANGE 这样的命令（比如：获取排行榜前 10 名）。

• 跳表： 底层是一个有序链表。一旦通过索引跳到起点，接下来的操作就是顺序遍历链表。这种操作在逻辑上非常自然，效率极高。
• 平衡树（如红黑树）： 虽然也能做范围查询，但需要进行中序遍历。在树结构中寻找“下一个节点”可能需要回溯到父节点再向下寻找，逻辑实现上比简单的链表遍历要复杂得多。

2. 实现简单，维护成本低

这是工程实践中的重要考量。

• 红黑树： 插入或删除节点时，为了保持平衡，可能需要触发复杂的左旋、右旋和变色操作。代码逻辑晦涩，极易出错。
• 跳表： 节点层级由随机概率（掷硬币）决定。插入数据时，只需要修改前后节点的指针即可。它的逻辑极其直观，代码量仅为红黑树的三分之一，非常便于调试和优化。

3. 并发环境下锁的粒度更小

虽然 Redis 目前的核心执行模型是单线程的，但从数据结构设计角度看：

• 平衡树： 一个插入操作可能引发从叶子到根的全树平衡调整，这意味着可能需要锁定整棵树。
• 跳表： 插入操作只影响局部指针。在多线程环境下（如 Java 的 ConcurrentSkipListMap），跳表可以实现更细粒度的锁，并发性能更强。

4. 内存开销的灵活性

很多人认为跳表比红黑树费内存（因为有冗余指针），但实际上：

• 跳表： 每个节点包含多少个指针是由概率常数 $p$ 决定的（Redis 中 $p=1/4$）。平均每个节点只需 $1 / (1-p)$ 个指针。
• 可控性： Redis 可以通过调整概率参数，在查询速度和内存消耗之间找到一个完美的平衡点。

5. 为什么不选 B+ 树？

• 环境不同： B+ 树的设计初衷是减少磁盘 IO（让树变矮）。
• 结论： 在内存环境下，磁盘 IO 不再是问题。B+ 树复杂的节点管理（Page 维护、分裂合并）在内存里反而变成了负担。跳表这种更轻量、对缓存友好的结构明显更合适。

直击要害的总结

1. 范围查询是 ZSet 的高频操作，跳表的有序链表特性天然契合。
2. 实现简单意味着系统更稳定，也更容易被其他开发者理解和优化。
3. 随机化平衡策略避免了复杂的旋转逻辑，同时在内存使用上非常灵活。

Redis 的选型哲学是：在满足性能需求的前提下，优先选择实现更简单、更易于扩展的结构。

终极知识回顾：你的数据结构地图

既然你已经从 B+ 树聊到了跳表，你的脑子里应该已经有了这张全景图：

1. 查磁盘上的单条记录 $\rightarrow$ B+ 树（MySQL）。
2. 海量数据拼命写入磁盘 $\rightarrow$ LSM 树（ClickHouse）。
3. 内存里做排行榜和范围查 $\rightarrow$ 跳表（Redis）。
4. 编程语言内部简单的映射查找 $\rightarrow$ 红黑树（Java/C++ 内部容器）。

恭喜你！你已经系统性地梳理了现代互联网架构中最核心的存储基石。

既然你是 Python/Go 后端开发，想了解一下 Go 语言的 Map 底层为什么要用 哈希表 而不是红黑树吗？或者你想聊聊你在 ClickHouse 工作中遇到的具体性能困惑？

问题 Q&A

是否能回答出那些触及底层原理和工程权衡的问题。

第一层级：原理与机制（面试必问，工作必备）

1. 关于 B+ 树（MySQL/常规数据库核心）

• 高价值问题： “为什么 B+ 树的节点大小（Page Size）通常设计为 4KB 或 16KB？树的高度通常是多少？能存多少数据？”
  • 价值点： 理解磁盘页（Page）与操作系统文件系统的对应关系。
  • 答案线索： 3层高的 B+ 树通常就能存 2000万行左右的数据。这解释了为什么 MySQL 查询通常只需要 1-3 次磁盘 IO。
• 高价值问题： “在 B+ 树场景下，使用 UUID 和自增 ID 作为主键，性能差异在哪里？”
  • 价值点： 理解顺序写 vs 随机写以及页分裂（Page Split）带来的性能损耗。这是数据库设计中最常见的坑。

2. 关于 LSM Tree（ClickHouse/StarRocks/RocksDB 核心）

• 高价值问题： “LSM Tree 是如何处理数据的修改（Update）和删除（Delete）的？”
  • 价值点： 理解 LSM 的 Append-only（只追加） 特性。LSM 里没有真正的“修改”，只有“写入新版本”；没有真正的“删除”，只有“写入墓碑标记（Tombstone）”。这直接关系到你如何理解 ClickHouse 的 ReplacingMergeTree。
• 高价值问题： “为什么 LSM Tree 读数据经常需要 Bloom Filter（布隆过滤器）配合？”
  • 价值点： 理解 LSM 读放大的痛点。不加布隆过滤器，读一个 Key 可能要查所有 Level 的文件，IO 会爆炸。

3. 关于跳表（Redis 核心）

• 高价值问题： “Redis 的 ZSet 在数据量少的时候用什么结构？数据量大时什么时候转为跳表？”
  • 价值点： 理解内存压缩（Ziplist/Listpack）。Redis 为了省内存，小数据量是用紧凑列表存的，只有大了才会用跳表。这涉及到“时间换空间”的工程权衡。

第二层级：性能权衡与调优（架构师视角）

这部分问题涉及到系统设计中的 Trade-off（权衡），没有标准答案，只有最适合场景的答案。

1. 著名的 RUM 猜想

• 高价值问题： “在存储系统设计中，Read（读）、Update（写/更新）、Memory（内存/空间）这三者通常只能满足两个，如何针对不同场景做取舍？”
  • B+ 树： 牺牲了写性能（随机写），换取了极致的读性能和较低的内存占用。
  • LSM 树： 牺牲了读性能（可能读多层），换取了极致的写性能。
  • Hash 索引： 牺牲了范围查询能力和内存（可能），换取了 O(1) 的点查。

2. 写放大 vs 读放大 vs 空间放大

• 高价值问题： “LSM Tree 的 Compaction（合并/压缩）机制会带来严重的写放大，这会如何影响线上业务？怎么缓解？”
  • 场景映射： 你在使用 ClickHouse 或 StarRocks 时，如果后台合并太频繁，CPU 会飙升，导致查询变慢。理解这一点，你才懂得为什么要调整 Compaction 策略，或者在业务低峰期做 OPTIMIZE TABLE。

3. 为什么 MongoDB 以前用 B 树，后来默认存储引擎 WiredTiger 也趋向于 B+ 树变种？

• 价值点： 纯 B 树虽然离根近的数据查得快，但范围查询（Range Scan）对磁盘极其不友好（需要中序遍历，是随机 IO）。而在大数据分析场景下，全表扫描或范围扫描是常态，B+ 树的叶子链表优势巨大。

第三层级：结合你的技术栈（Go/Python & DB）

这些问题能帮你把理论落地到你手写的代码中。

1. Go 语言与红黑树/B 树：
   • Go 的 map 底层是 Hash 表，但 Go 的运行时定时器（Timer）以前用的是 最小堆（Min Heap），这和跳表、红黑树有什么异同？（都是为了快速找到最小/最近的时间点）。
   • 如果有海量数据在 Go 内存里要做排序和范围查，你会选 B-Tree 库（如 Google 的 btree 包）还是自己写个红黑树？（答案通常是 B-Tree，因为 Go 的 GC 对指针过多的结构（如红黑树/链表）压力很大，而 B-Tree 节点大，指针少，对 GC 更友好）。
2. StarRocks/ClickHouse 调优：
   • 你知道 StarRocks 的主键模型（Primary Key Model）为了加速去重，其实引入了内存索引，这是否打破了 LSM 纯磁盘的限制？
   • 为什么 ClickHouse 不建议高频单条插入，而建议批次插入？（直接对应 LSM Tree 频繁 Flush 会导致生成大量小文件，后续 Merge 压力巨大的原理）。

总结：在这个阶段，你最该搞懂的一个问题

如果只选一个最有价值的问题来深入，结合你现在的“后端开发 + 数据分析（ClickHouse/StarRocks）”背景，我建议你彻底搞懂：

“LSM Tree 的 Compaction（合并）策略具体是怎么工作的？Leveled Compaction 和 Size-Tiered Compaction 有什么区别？”

• 理由：
  • Size-Tiered（写极快，读慢，空间放大严重）：适合像 ClickHouse 这种写日志、写指标的场景。
  • Leveled（写稍慢，读稳，空间控制好）：适合 RocksDB 这种做 KV 存储的场景。
  • 价值： 弄懂这个，你就能解释为什么有时候你的 StarRocks 写入很快但查询抖动，或者磁盘空间突然报警。

你想先针对 “LSM Tree 的写放大与合并策略” 这一点展开吗？这和你工作中的 ClickHouse 息息相关。

MySQL & mongo

为什么mongo要使用B树作为存储结构，而mysql是使用B+树呢?

这是一个非常经典的数据库底层原理问题，核心区别在于 应用场景（Data Model & Access Pattern）的不同。

简单来说：MySQL（关系型）重在“范围查询”和“排序”，而 MongoDB（文档型）重在“单条记录的快速读写”。

为了更直观地理解，我们需要对比 B-Tree 和 B+Tree 的结构差异：

1. 核心区别：数据存在哪里？

• MySQL (InnoDB) 使用 B+Tree：
  • 非叶子节点只存索引（Key），不存数据。
  • 叶子节点存储所有的数据（Value），并且叶子节点之间通过双向链表连接。
• MongoDB (早期/经典模型) 使用 B-Tree：
  • 每个节点（包括非叶子节点） 都存储数据（Key + Value）。
  • 数据分布在树的各个层级中，叶子节点之间没有指针连接。

2. 为什么要这样设计？（场景决定结构）

MySQL 为什么选 B+Tree？（为“关系”服务）

SQL 数据库最常见的操作不仅仅是 WHERE id = 1，更多的是：

1. 范围查询：SELECT * FROM users WHERE age > 18。
2. 全表/全索引扫描：COUNT(*) 或不带索引的查询。
3. 排序：ORDER BY create_time。

• 优势：在 B+Tree 中，只要找到范围的起点，顺着叶子节点的链表往后遍历即可，效率极高。
• 稳定性：查询任何数据都需要走到叶子节点，IO 次数是固定的（通常 2-3 次），性能非常稳定。
• 页利用率：因为非叶子节点不存数据，能存更多的索引键值。这意味着树的层高（Height）更低，减少磁盘 IO。

MongoDB 为什么选 B-Tree？（为“文档”服务）

MongoDB 是非关系型数据库，它的核心理念是 Document（文档）。

1. 单条获取：Mongo 最典型的用法是通过 _id 获取整个 JSON 文档。数据往往是聚合好的（比如用户信息里直接包含地址列表），不需要像 SQL 那样 Join。
2. 局部性原理：如果你经常访问某些“热数据”，在 B-Tree 中，这些热数据可能直接存在于根节点或靠近根节点的层级。

• 优势：
  • 查询可能更快：如果运气好，数据在根节点或第二层，只需要 1 次 IO 就能拿到数据，不需要像 B+Tree 那样必须走到最底层的叶子节点。
  • 写入优势：对于写入操作，B-Tree 不需要像 B+Tree 那样频繁地维护叶子节点的链表平衡，对于某些高频写入场景有一定优势。

3. 这里的“误区”与现代真相 (WiredTiger 引擎)

虽然面试中大家常说“Mongo 用 B-Tree，MySQL 用 B+Tree”，但这个说法在现代 MongoDB 中并不完全准确。

MongoDB 早期的存储引擎 MMAPv1 确实使用了类似 B-Tree 的结构。但是，从 MongoDB 3.2 开始，默认引擎变成了 WiredTiger。

WiredTiger 的实现其实更接近 B+Tree：

1. 磁盘上的数据：WiredTiger 在磁盘上存储数据时，采用的结构类似于 B+Tree，数据主要集中在叶子页面（Leaf Pages），内部页面（Internal Pages）主要用于导航。
2. 内存中的表现：WiredTiger 加载到内存后，会使用一种特殊的 B-Tree 变体，甚至结合了跳表（Skip List）的思想来处理并发修改。

所以，为什么现在大家还认为 Mongo 是 B-Tree？

• 历史原因：早期架构的惯性认知。
• 非关系型特性：Mongo 依然不支持像 SQL 那样高效的 Join 和复杂的范围分析，它的设计初衷依然是“Key-Value”式的文档存取，这符合 B-Tree 的原始设计哲学（尽快找到 Key 对应的 Value）。

总结

简单一句话：MySQL 假设你会经常遍历数据，所以把数据铺平在底部连起来；MongoDB 假设你只关心特定的某一个文档，所以把数据散落在树的各个节点，让你尽快遇到它。

MongoDB 存储引擎

为什么mongo的存储结构向B+树演进？WiredTiger 在磁盘上存储数据时，采用的结构类似于 B+Tree，那么到底和B+树有何不同？

这是一个非常深刻的问题，触及了数据库存储引擎设计的核心取舍。

简单来说，MongoDB 从早期的 B-Tree 理念转向 WiredTiger 的 B+Tree 变体，是因为现代硬件特性（磁盘 I/O 和 CPU 缓存）以及业务场景（范围查询和压缩需求）的变化。

WiredTiger 虽然在磁盘上使用 B+Tree 结构，但它引入了“写时复制（Copy on Write）”、“变长页面”和“前缀压缩”，这使得它与传统的（如 InnoDB 的）B+Tree 也就是所谓的“定长原地更新 B+Tree”有很大不同。

一、 为什么 Mongo 的存储结构向 B+Tree 演进？

早期 MongoDB 使用 B-Tree 是为了“单点查询极快”，但在大规模生产环境中，B+Tree 的优势逐渐压倒了 B-Tree：

1. 缓存命中率与树高（Cache Friendliness）

• B-Tree 问题：非叶子节点也存 Data（文档）。MongoDB 的文档是 JSON，通常很大（几 KB 到几 MB）。这意味着一个 16KB 的内存页，如果用来存非叶子节点，可能只能存几个 Key + Data。结果就是分叉率（Fan-out）低，树很高。
• B+Tree 优势：非叶子节点只存 Key（索引）。Key 通常很小（几十字节）。一个 16KB 的页可以存上千个 Key。这意味着树非常矮（通常 3 层就能存几十亿数据），大大减少了磁盘 I/O。

2. 范围查询（Range Scan）的碾压

• B-Tree 问题：要做范围查询（例如 age > 20），B-Tree 需要进行“中序遍历”，在树的各层之间跳跃，产生大量的随机 I/O。
• B+Tree 优势：叶子节点存了所有数据且物理（或逻辑）相邻。范围查询只需要找到起点，然后顺序读取磁盘块（Sequential I/O），这对机械硬盘和 SSD 都极其友好。

3. 磁盘块的利用率

• 操作系统和磁盘是按“Block（块/页）”读写的。B+Tree 将索引和数据分离，使得索引页极其紧凑，数据页也可以集中存储，极大提升了缓冲池（Buffer Pool）的利用效率。

二、 WiredTiger 的 B+Tree 与传统 B+Tree (InnoDB) 有何不同？

虽然大家都是 B+Tree，但 InnoDB 是为传统 OLTP 设计的，而 WiredTiger 是为现代高并发 + 高压缩 设计的。

1. 页面大小：定长 vs. 变长

• **InnoDB (传统)**：
  • 严格的 16KB（默认）定长页面。
  • 如果数据更新导致页面溢出，需要复杂的页分裂（Page Split）和碎片整理。
• **WiredTiger (现代)**：
  • 磁盘上的页面是变长的。虽然默认配置可能是 32KB，但它会根据数据压缩后的实际大小动态调整写入磁盘的块大小。
  • 这使得 WiredTiger 能够极其高效地利用压缩算法（如 Snappy, Zstd）。在 InnoDB 中，压缩往往会导致“半满”的页，产生空洞；而 WiredTiger 直接把压缩后的数据紧凑地写盘。

2. 更新机制：原地更新 vs. 写时复制 (Copy on Write / Checkpoint)

这是最本质的区别：

• **InnoDB (Update-in-place)**：
  • 修改数据时，直接在 Buffer Pool 的页中修改。
  • 刷盘时，把原来的页覆盖掉（或者写入 Double Write Buffer 防止崩溃）。
  • 缺点：并发控制依赖复杂的行锁和锁存器（Latch）。
• **WiredTiger (No-overwrite / Reconciliation)**：
  • WiredTiger 采用一种 Shadow Paging（影子分页） 的变体。
  • 当一个页被修改时，WiredTiger 往往不会直接覆盖磁盘上的旧页，而是找一个新的位置写入新页，并更新父节点的指针指向新位置。
  • 优势：这天然支持了 Snapshot（快照）隔离级别。只要旧的页还没被回收，旧的事务就可以读取旧页，完全不需要像 InnoDB 那样去回滚段（Undo Log）里翻旧版本数据。

3. 内存中的数据结构 (Reconciliation 机制)

WiredTiger 最“黑科技”的地方在于：磁盘上是 B+Tree，但内存里不是 B+Tree。

• 磁盘态：标准的 B+Tree 页（Extent）。
• 内存态：
  • 当一个磁盘页被加载到内存时，WiredTiger 会把它解析成一个 基准值（Base Data） 加上一个 修改链表（Update List / Skip List）。
  • 读操作：合并基准值 + 修改链表。
  • 写操作：不修改原始页面，而是向“修改链表”中追加（Append）一条记录。
  • 刷盘（Reconciliation）：只有在 Checkpoint 或内存不够时，WiredTiger 才会把“基准值 + 修改链表”合并，重新生成一个新的 B+Tree 磁盘页并写入磁盘。

形象比喻：

• InnoDB 像是在黑板上写字，改错了直接擦掉重写（需要锁住黑板不让别人看）。
• WiredTiger 像是在书上贴便利贴。读的时候连着书和便利贴一起看。等到便利贴贴满了，再把整页书重新排版打印一张新的纸插进去。

4. 前缀压缩 (Prefix Compression)

WiredTiger 在磁盘 B+Tree 的叶子节点中，默认开启Key 前缀压缩。

• 如果有两个 Key：user_001, user_002。
• InnoDB 可能存两份完整的。
• WiredTiger 存 user_001, (match=7, suffix='2')。
• 这对于像 MongoDB _id 这种通常由时间戳构成、具有高度相似性的 Key，能极大节省空间。

总结

MongoDB 转向 B+Tree 是为了利用现代 I/O 模式处理海量数据。

而 WiredTiger 的 B+Tree 与 InnoDB 的区别在于：

1. 变长页 + 块压缩：极致的磁盘空间利用率。
2. **内存追加写 (Update List)**：写操作在内存中是追加而非覆盖，实现无锁并发。
3. **写时复制 (CoW)**：落盘时写新块，天然支持快照，减少了对 Undo Log 的依赖。

WiredTiger 其实更像是一个 Log-Structured Merge Tree (LSM) 的思想注入到了 B+Tree 的骨架中。

拓展阅读

1. DDIA：GitHub - Vonng/ddia: 《Designing Data-Intensive Application》DDIA 第一版 / 第二版 中文翻译
2. 各类数据结构可视化：Data Structure Visualization
3. 算法入门：Hello 算法
4. 红黑树：红黑树 | JavaGuide
5. Redis跳表：Redis为什么用跳表实现有序集合 | JavaGuide
6. 面试题汇总：红黑树（图解+秒懂+史上最全） - 技术自由圈 - 博客园