后端文档教程【免费下载链接】system-design-101Explain complex systems using visuals and simple terms. Help you prepare for system design interviews.项目地址https://gitcode.com/GitHub_Trending/sy/system-design-101点击查看免费下载B-Tree 与 LSM-TreeLog-Structured Merge Tree日志结构合并树是现代数据库底层最核心的两种索引数据结构前者统治了几乎所有关系型数据库后者是 Cassandra、LevelDB、RocksDB 等 NoSQL 存储引擎的标配。本篇文章以 system-design-101 仓库中的 b-tree-vs.md 为骨架结合仓库内数据库索引、SQL 执行与扩展策略等相关文档系统讲解两者的工作原理、读写下差异、适用场景并给出系统设计与面试中的选型判断路径。从数据库索引说起为什么选型要先看数据结构在深入 B-Tree 与 LSM-Tree 之前需要先建立一个背景数据库性能的上限很大程度上由它选择的索引数据结构决定。正如仓库文档 8-data-structures-that-power-your-databases.md 所强调的数据可以放在内存或磁盘上数据格式千差万别系统可能是写密集或读密集的——这些因素共同决定了索引格式的选择。该文档列出的常见索引数据结构包括Skiplist跳表常见的内存索引类型Redis 使用它Hash index哈希索引“Map/Collection”数据结构的经典实现SSTable磁盘上不可变的“Map”实现LSM treeSkiplist SSTable高写吞吐B-tree基于磁盘的解决方案读写性能稳定Inverted index倒排索引用于文档索引Lucene 采用Suffix tree后缀树字符串模式搜索R-tree多维搜索如最近邻查找。可以看到B-Tree 与 LSM-Tree 正是这张索引谱系图中分别代表“磁盘读优化”与“写吞吐优先”的两极。理解这两者的差别是回答“如何为写密集/读密集系统选数据库”这类问题的基础。B-Tree关系型数据库的“读优先生”核心结构以页Page为基本存储单元B-Tree 是几乎所有关系型数据库中最广泛使用的索引数据结构。其基本存储单元通常被称为page页。B-Tree 是一棵多路平衡搜索树每个节点可以容纳多个键子节点数量由节点的键个数决定这正是“多路”的含义区别于二叉搜索树。整棵树保持平衡即从根到所有叶子的路径长度大致一致从而保证查找的复杂度稳定。一次典型的查找过程是从根节点出发沿键的范围逐层下钻直到定位到包含目标键的叶子节点取出实际值。由于每个节点对应一个磁盘页B-Tree 将一次磁盘 I/O 与一次节点访问对应起来因此查找的时间复杂度与树的层数高度直接相关配合节点内键的局部有序可以在一个页内通过二分查找快速定位。为什么 B-Tree 读得快磁盘顺序友好单个 page 内数据连续存放一次 I/O 能读取一整个节点并完成局部查找树高度低多路分支让 B-Tree 在数据量极大时依然只有几层查找只需数次磁盘 I/O局部性好范围查询时相邻键位于相邻叶子节点遍历成本低原地更新B-Tree 的写入通常是在已有页上做原地修改数据位置相对稳定利于数据库缓存buffer pool命中。正因如此SQL 执行流程中的读路径特别依赖 B-Tree 索引。仓库文档 how-is-a-sql-statement-executed-in-the-database.md 展示了典型流程SQL 经传输层进入命令解析器生成查询树再交给优化器生成执行计划执行器通过Access Methods访问方法从存储引擎取数——这里的访问方法在很多关系型数据库中正是基于 B-Tree 的索引扫描与全表扫描选择。读取型查询最终进入Buffer Manager在缓存或数据文件中查找数据而 B-Tree 的页结构恰好在缓存管理中表现出色。LSM-TreeNoSQL 世界的“写优先生”核心结构内存 Skiplist 磁盘 SSTableLSM-Tree 被许多 NoSQL 数据库广泛采用典型代表包括Cassandra、LevelDB 和 RocksDB。LSM-Tree 维护的是key-value 键值对其磁盘持久化依赖SSTableSorted Strings Table排序字符串表——表中的键是有序排列的。LSM-Tree 的基本工作方式是分层写入写入请求先进入内存结构如跳表 Skiplist这正是 8-data-structures-that-power-your-databases.md 中所说的“LSM tree Skiplist SSTable”在此完成排序与合并写入完全发生在内存因此速度极快当内存结构达到一定阈值整块数据被顺序刷盘生成一个新的 SSTable磁盘上的不可变有序文件新生成的 SSTable 归入Level 0 段后台进程将Level 0 的段周期性合并到 Level 1逐级下沉、归并整理。Compaction压缩合并LSM-Tree 的灵魂原文档特别强调Level 0 段定期合并为 Level 1 段这一过程称为 compaction压缩合并。Compaction 的作用包括将多个小 SSTable 合并成更大的有序文件减少文件数量降低读放大清理过期或已被覆盖的旧版本数据多版本合并维持每层文件的有序性保证查询路径可控。compaction 通常分为size-tiered大小分层与leveled层级式两类策略分别侧重写吞吐优化与读放大/空间放大优化。compaction 是后台异步执行的这也解释了 LSM-Tree 的一个典型特征写入路径峰值性能高但磁盘占用和读路径的稳定性会受 compaction 节奏影响。为什么 LSM-Tree 写得快顺序写数据先在内存排序再顺序追加到磁盘避免了 B-Tree 的随机页写入批量落盘内存中积累的一批写入一次性刷成一个大 SSTable摊薄了每次写入的 I/O 成本无原地更新SSTable 一旦生成就不可变写操作只追加天然对机械磁盘友好也易于发挥 SSD 的顺序写带宽。核心差异最快的对比结论原文档给出的最核心对比结论只有两条却足以指导大量工程决策B-Tree 提供更快的读faster readsLSM-Tree 提供更快的写fast writes二者本质上是读优化与写优化之间的权衡维度B-TreeLSM-Tree基本存储单元Page页SSTable排序字符串表 内存结构写入方式页内原地更新可能触发随机写内存排序后顺序追加落盘读取方式沿键范围下钻至叶子磁盘 I/O 次数少需在内存结构及多层 SSTable 中查找可能有多层读放大写吞吐受随机 I/O 限制相对较低顺序写显著更高读延迟稳定、低通常更高且受 compaction 影响空间占用较紧凑、稳定存在多版本与临时文件空间放大需要 compaction 控制典型数据库几乎所有关系型数据库如 PostgreSQL、MySQLCassandra、LevelDB、RocksDB 等 NoSQL/嵌入式存储如何选型把结构差异落到业务场景结合仓库中数据库选型与扩展策略相关文档可以给出可执行的判断路径。读密集 / 强一致性业务 → 优先 B-Tree仓库文档 how-to-choose-the-right-database.md 明确指出OLTP 事务系统需要强一致性。这类系统的典型特征是大量点查、范围查询、事务与小更新读延迟敏感。B-Tree 的原地更新与稳定的读路径使其成为默认选择——这也是为什么关系型数据库普遍采用 B-Tree 索引。若系统面临读压力也应优先考虑仓库文档 7-must-know-strategies-to-scale-your-database.md 中提到的**索引优化、缓存、读副本replication**等方案而不是轻易更换存储引擎。写密集 / 日志型业务 → 考虑 LSM-Tree如果业务是写为主、读可接受一定延迟的场景——例如时序数据、日志收集、消息队列落盘、IoT 传感器数据——LSM-Tree 的顺序写优势会带来数量级的写吞吐提升。这也是 Cassandra、LevelDB、RocksDB 在这些场景中被选中的根本原因。系统设计面试中的答题框架面试中被问及“B-Tree 还是 LSM-Tree”时建议按以下结构作答先讲结构B-Tree 以页为单位、多路平衡、原地更新LSM-Tree 以“内存结构 SSTable”分层组织写入先入内存再顺序落盘再讲机制LSM-Tree 强调 compaction 的合并过程B-Tree 强调查找沿键范围下钻的过程给出权衡B-Tree 读快、写相对慢LSM-Tree 写快、读相对慢且有读/空间放大落到场景结合 OLTP 强一致性倾向 B-Tree与写密集日志型倾向 LSM-Tree给出结论并说明可以通过缓存、读副本、compaction 策略等缓解各自短板。小结B-Tree 与 LSM-Tree 之争没有绝对赢家本质上是读延迟与写吞吐之间的工程权衡B-Tree 以稳定的读性能和紧凑的空间占用成为关系型数据库的默认索引LSM-Tree 以顺序写和异步合并换来更高的写吞吐成为写密集 NoSQL 存储的事实标准。结合 b-tree-vs.md 与仓库中 8-data-structures-that-power-your-databases.md、how-to-choose-the-right-database.md、7-must-know-strategies-to-scale-your-database.md 等文档理解这两棵树的差异就能在系统设计与面试中做出有理有据的存储选型决策。赞分享后端文档教程【免费下载链接】system-design-101Explain complex systems using visuals and simple terms. Help you prepare for system design interviews.项目地址https://gitcode.com/GitHub_Trending/sy/system-design-101点击查看免费下载相关推荐《设计数据密集型应用》第四章精读存储引擎全景——从 LSM-Tree、B-Tree 到列式存储与向量索引《设计数据密集型应用》第四章精读存储引擎全景——从 LSM Tree、B Tree 到列式存储与向量索引 本文以 DDIADesigning Data In文档教程RisingWave 状态存储设计深度解析Hummock 云原生 LSM-Tree 引擎与流式检查点RisingWave 状态存储设计深度解析Hummock 云原生 LSM Tree 引擎与流式检查点 本篇技术指南以 RisingWave 设计文档《An O数据库流处理后端数据工程nix-config项目迁移公告从GitHub到自建Git服务器的完整指南nix config项目迁移公告从GitHub到自建Git服务器的完整指南 nix config项目作为NixOS和nix darwin机器的配置文件集合已上一篇Higress vs Envoy云原生网关选型量化对比指南下一篇从回测到实盘AutoTrader 三步把量化策略跑起来的完整分步指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考