故事
黄河改道那年,测绘局和老河工陈三吵过一架。测绘局的洋学生姓杜,留过德,带回来一台水准仪和一套"断面测量法":每隔五十步打一根铁钎入河底,量深浅、记坡度、当场绘成河床剖面图。杜学生说陈三的桦皮册是"懒办法",只记不改,越积越厚,查起来翻死人。
陈三没争辩,只请他看汛期作业。
七月半,洪峰过龙门。杜学生带着三个助手扛铁钎下滩,第一根打到七尺深,泥沙塌了,铁钎歪了;拔出来重打,第二根位置偏了三丈。等到第四根打完,第一根的量数已经不准——河底被水冲得变了形。助手们浑身泥水,剖面图上的点连不成线。陈三的徒弟蹲在岸上,往桦皮册里记:"未时三刻,塌岸十七步,水深增四尺。"一笔写完,册子一合。
杜学生不服,说平时没洪水的时候,铁钎法总是准的。陈三反问:"黄河一年汛期几个月?"杜学生算了一下:伏秋大汛四个月,桃汛凌汛两个月,加上凌汛前的解冻期滩土松软,铁钎根本立不住。一年里头,能安安稳稳打钎的日子不到一半。
"你那法子,"陈三说,"不是不好,是挑时辰。挑时辰的法子,挑不到时辰就瘫痪。"
民国十五年,杜学生进了交通部,主持编纂《黄河志》。他学乖了,把两种法子并列写进卷首:"铁钎法"精确而即时,宜于枯水期修堤、筑坝、定桥基;"桦皮册法"冗余而延迟,宜于汛期抢记、灾后追溯、长期河势分析。他加了一句按语:二者非争胜负,乃争"何者为底、何者为变"——以铁钎为底,桦皮册为变,则枯水期强而汛期弱;以桦皮册为底,铁钎为变,则全年可用,唯精确稍逊。
后来修三门峡水库,工程师们果然两种都用:枯水期用铁钎定坝基坐标,汛期改陈三簿记水情,等到霜降再归总比对。有人嫌麻烦,问何必两套。总工程师说:"你要是只读一种册子,要么汛期睁眼瞎,要么枯水期累断腰。"
概念解析
B-Tree与LSM树的对照,本质是"就地更新"与"追加写入"两种世界观的对照。
B-Tree:铁钎法。数据页固定大小(通常4KB或16KB),写入时找到目标页,读入内存,修改,写回磁盘。读路径短——从根节点逐层下沉,最多三到四次IO即可定位;写路径复杂——随机写入可能触发页分裂、级联平衡、重做日志刷盘。B-Tree为"读优化"而生,假设工作负载里读远多于写,且每次读取追求最低延迟。
LSM树:桦皮册法。写入只往内存里的MemTable追加,满后顺序刷入不可变的SSTable。读路径长——须合并MemTable与多层SSTable,按时间戳取最新版本;写路径极简,近乎纯顺序写入。LSM树为"写优化"而生,假设写入密集、顺序写入为主,愿意用读放大和空间放大换取写吞吐。
2010年代的战场。MySQL、PostgreSQL、Oracle的InnoDB引擎基于B-Tree;Cassandra、HBase、LevelDB、RocksDB、TiKV基于LSM树。2014年前后,Facebook把MySQL的UDB存储引擎从B-Tree迁移到MyRocks(RocksDB的MySQL封装),只为解决复制延迟——B-Tree的随机写入在SSD上放大为大量擦写,从库追不上主库。同一时期,MongoDB的WiredTiger引擎引入B-Tree与LSM的混合选项,让用户按集合选择。
各自的软肋。B-Tree的页分裂造成写放大与空间碎片,长期运行后需要OPTIMIZE TABLE或VACUUM重整;并发写入同一页时,latch竞争剧烈。LSM树的合并之苦(Compaction)在写入峰值与读取长尾之间制造抖动——RocksDB的"写停顿"(write stall)是生产环境最头疼的调参对象;范围查询若跨多层SSTable,延迟不可预测。
现代融合。PebblesDB用"片段化LSM"降低写放大;WiscKey把键值分离,让LSM树只排序键、值存在日志里,削减合并开销。B-Tree一侧,Bw-Tree(微软Hekaton、Azure SQL)用 latch-free 的CAS链更新页,避免锁竞争;LMDB把整个B-Tree映射进单一内存文件,用COW(写时复制)替代就地更新,兼得B-Tree的读性能与LSM树的不可变优势。
杜学生的《黄河志》按语里藏着一种更深的选择:不是哪种结构更好,而是你的系统里"底"与"变"如何配比。读多写少、点查为主、延迟敏感——B-Tree是底;写密集型、顺序写入、需要时间维度回溯——LSM树是底。真正复杂的系统,像三门峡水库的工程档案室,两种册子并排立在架上,枯水期翻铁钎图,汛期读桦皮册,霜降后对照归总——这叫做"存储引擎的选型",也叫做"承认没有银弹"。