存储引擎既要持久化写入，也要快速找到已经写入的数据。B-Tree 家族与 LSM-Tree 的差异，可以从一个问题理解：系统在什么时机、以什么粒度，为数据的有序组织付出代价？
B+Tree 维护页与页之间的搜索结构，更新通常落到相应页面；LSM 将新版本先组织在内存与日志中，再通过刷盘和合并维持磁盘上的有序文件。两者都需要日志、缓存和后台工作，不能简单等同于“每笔随机写”与“没有随机 I/O”。
B-Tree：通过高扇出减少层数
本文将 m 阶定义为最多 m 个孩子。非根内部节点至少有 ceil(m/2) 个孩子；叶节点没有孩子，但仍受相应关键字数量下限约束。非叶根至少有两个孩子，所有叶节点位于同一层。
查询在页内定位关键字或子树方向，再沿相应分支下降。节点容量越大，一层通常能够覆盖越多数据。插入溢出时分裂，删除低于占用下限时借位或合并，维持树的结构约束。
高扇出可以减少访问层数，但树高不等于每次查询的磁盘 I/O 次数：根和内部页可能已在缓存，叶页也可能命中。普通二叉搜索树还可能退化成链表，只有平衡等相应条件下才有对数树高。
B+Tree：将记录组织在叶层
B+Tree 的内部节点主要保存导航键与孩子引用，叶节点保存索引项或记录，并通过叶层链接支持有序扫描。是否双向链接属于实现选择，不是所有定义都必须如此。
范围查询先定位起点，再扫描相关叶页；B-Tree 同样可以进行范围查询，只是访问组织不同，并不必然遍历整棵树。
| 关注点 | B-Tree | B+Tree |
|---|---|---|
| 记录位置 | 可位于内部与叶节点 | 通常集中在叶节点 |
| 内部节点 | 兼有导航与记录信息 | 主要承担导航 |
| 范围访问 | 按有序遍历组织 | 常沿叶层链接扫描 |
| 实际成本 | 取决于页、键和值的表示 | 同样取决于表示、缓存和访问模式 |
内部节点是否更小、树是否更矮，要在相同页大小和记录表示下比较，不能脱离编码方式给出固定倍数。
InnoDB 与 PostgreSQL 的不同组织
InnoDB 的默认页大小为 16 KiB，并可在初始化时选择受支持的其他大小。聚簇索引叶页保存行记录，二级索引叶项包含用于定位聚簇记录的主键信息。读取索引已覆盖的列时，也可能避免回表。
估算树的容量，需要同时计入内部页扇出、叶页记录数、页头、槽目录和填充率。“一个页能放多少指针”不能直接当成“整棵树能放多少行”。例如，忽略开销的教学估算若采用扇出 f、每叶页 r 行，两层内部节点覆盖的量级是 f²×r 行，而不是只有 f² 行。MySQL 8.0 索引物理结构。
PostgreSQL 的普通表通常使用堆组织，索引项指向堆元组位置。但索引扫描不总是必须访问堆：查询所需数据被索引覆盖，且可见性信息满足条件时，Index-Only Scan 可以省去相应堆访问。PostgreSQL 索引仅扫描说明。
这些差异会影响查询路径，却不能仅凭结构名称判断哪个数据库更快。
B*Tree 的重点是重分配策略
B*Tree 是 B-Tree 家族提高占用率的一类变体。典型策略在节点满时先尝试与兄弟重分配；两个节点都满时，再把数据分到三个节点，使非根节点的最低占用率接近三分之二。
它的核心不是“多了兄弟指针”这一项，而是如何组织重分配和分裂。具体阈值、根节点例外与并发协议，仍需按定义和实现核对。
LSM：将写入与磁盘整理分开
以常见日志、MemTable 与 SSTable 结构为例，一次写入通常涉及：
- 按持久性配置追加 WAL，并在需要时等待同步
- 更新内存中的有序 MemTable
- MemTable 达到配置阈值后冻结，后台刷成不可变 SSTable
- 后台 Compaction 合并文件，整理重叠范围和仍需保留的版本
WAL 的成功追加、操作系统接收写入和介质持久化是不同阶段，不能把“有日志”直接当成任何配置下都不会丢数据。后台刷盘也不保证永不阻塞：内存缓冲积压、L0 文件过多或后台吞吐不足，都可能触发限速或写停顿。
SSTable 中常有数据块、索引、过滤器与元数据，但具体布局不是统一标准。不可变文件便于并发读取和批量压缩，整个引擎仍需协调文件生命周期、缓存与版本。
读取时，系统查找满足快照条件的最新可见记录。范围扫描可能需要归并多份有序数据；删除标记也不能随意丢弃，否则旧文件中的值可能重新出现。只有确认不会影响快照和其他版本的正确性，才能回收相应数据。
Compaction 如何改变成本
Tiered 类策略倾向于合并大小相近的有序文件或运行段，减少反复与大层重写的开销；Leveled 类策略更积极地约束每层的键范围重叠，通常以更多整理工作换取较少的查询候选和旧版本占用。
在 RocksDB 常见的 Leveled 组织中，L0 文件可以重叠，后续每层的文件键范围不重叠。层大小是目标而非每时每刻的精确值，动态层大小配置也不等于完全取消层间倍率。RocksDB Leveled Compaction。
| 策略倾向 | 可能改善 | 需要观察 |
|---|---|---|
| 减少或推迟合并 | 前台可用写入带宽 | 文件重叠、读取候选、旧版本空间 |
| 更积极整理范围 | 点查和空间占用 | 后台写入、CPU 与前台竞争 |
| 拆分并行任务 | 大合并完成时间 | 资源峰值与调度开销 |
| 限制后台速率 | 前台延迟干扰 | 积压和后续写停顿 |
这些是设计取舍，不是每一种工作负载下都成立的性能排名。
三种放大必须统一口径
写放大比较实际写入与逻辑写入量，是否包含 WAL、文件系统和设备内部写入需要说清。不能只看前台一次追加，就认为整个 LSM 写入只有一次。
读放大可以按候选文件、块访问或实际字节统计。这些口径不等价：查过滤器不一定读取数据块，命中缓存也不等于发生物理 I/O。
空间放大比较实际占用与有效数据量，需要交代是否包含日志、快照、删除标记和合并临时空间。压缩率也会改变分母与分子的解释。
RUM 视角提醒我们共同分析读取、更新和内存空间成本，但不应将它写成脱离模型、任何优化都必然损害另外两项的物理定律。改进编码或消除冗余，可能同时改善多个指标。
从访问模式出发选型
B+Tree 可以在缓存中合并多次页修改，再批量刷出脏页；LSM 也会承担后台读写和竞争。不能用“每笔 B+Tree 写至少两次随机 I/O”与“LSM 完全顺序 I/O”比较，更不能据此推导固定的 5–10 倍吞吐优势。
| 需要测量的条件 | 对判断的作用 |
|---|---|
| 点查、范围扫描与更新比例 | 明确主要成本在哪里 |
| 键值大小和热点分布 | 影响页容量、缓存与压缩 |
| 同步提交与恢复要求 | 统一持久性语义后才能比较延迟 |
| 长快照与删除比例 | 影响版本保留和空间回收 |
| 稳态后台工作 | 避免仅测到内存缓冲尚未耗尽的短时吞吐 |
| P50、P99 与写停顿 | 观察尾延迟，不由树形预先保证 |
| 内存、磁盘与 CPU 预算 | 评估整体成本及余量 |
底层索引结构不决定系统只能支持最终一致性或强事务，也不规定只能部署在单机 TB 或分布式 PB 规模。事务和分布式协议需要单独设计；B+Tree 与 LSM 都可能成为不同事务系统的组成部分。
混合方案要区分引擎能力与产品接口
RocksDB 的列族、后台并行、速率限制等机制，让同一结构可以适配不同工作负载。TiKV 等系统还在本地存储之上组织复制和事务；Raft 日志存储、Region 阈值和大 Value 分离能力，应按版本与配置核对，不能把历史默认值写成通用属性。
WiredTiger 的历史能力也不能直接推导为 MongoDB 用户可按集合自由选择 B-Tree 或 LSM。讨论 MongoDB 时，应以其实际暴露的存储、事务和压缩接口为准。MongoDB WiredTiger 文档。
更值得迁移的认识是：可以针对键、值、索引、日志和冷热数据采用不同组织方式，但每种组合都必须维持一致的读取、恢复和生命周期语义。
B+Tree 在页面结构中持续维护有序访问，LSM 在内存排序和后台归并中分摊整理工作。选择哪一种，应让真实访问模式与稳态测试给出答案，而不是让“读优化”或“写优化”的标签替代分析。