如果你去看数据库的底层实现，不论 MySQL 的 InnoDB、PostgreSQL，还是商用的 Oracle，一提到索引，几乎全是 B+ 树的天下。很多人念书的时候都学过 B 树，难免会嘀咕：B+ 树不就是叶子节点多了一串链表吗，真就非它不可？放到工程里，差别比想象中大得多，而这差别的根源，几乎都来自一个慢得让人抓狂的东西——磁盘。
数据库的数据老老实实躺在硬盘上，磁盘读写是毫秒级的，内存访问是纳秒级的，差了好几个数量级。索引结构好不好，关键就看谁能让磁盘少动弹两次。B+ 树的第一个优点就埋在这里：内部节点只存索引键，不存实际数据或数据地址，像一本极薄极清晰的目录。一个 16KB 的磁盘页，能塞进的键数远比 B 树多，扇出（每个节点能指出去的分支数）被撑得很大。同样体量的数据，B+ 树的高度往往比 B 树矮一层甚至更多。树矮一层，查找就能少一次磁盘 I/O；在海量数据下，每少一次 I/O 都是白花花的性能。而且，因为内部节点足够瘦，数据库能把高层内部节点全缓存在内存里，根到叶的路径更短、命中率更高，这点对高并发场景尤其实在。
再往深一层想，B 树有个“小聪明”：数据允许挂在内部节点上，运气好查个键直接在中间就拿到，不用每次都走到叶子。乍一听像是优势，但这点小便宜对数据库反而添乱。B+ 树索性做得更绝——把所有数据都压到叶子节点，想找任何一个键，都必须乖乖从根爬到叶子。听着像多走了路，可恰恰让每一次查询的开销变得极其稳定，没有任何波动。查询优化器做代价估算、响应时间监控，都能吃准“每次都固定走到底”的规律。对线上系统来说，稳定的平均延迟比偶尔极快、偶尔极慢要重要得多。这种底层的可预测性，是 B+ 树送给数据库工程师的一颗定心丸。
不过，B+ 树真正的杀手锏，还是范围查询和顺序扫描。叶子节点被一条双向链表串在一起，所有数据天然按顺序排好。比如要找 age BETWEEN 20 AND 30，系统先定位到键值 20 的叶子，然后顺着链表一口气往后捋，一直捋到 30 收工——这完完全全是磁盘最喜欢的顺序读，速度逼近连续拷贝文件，预读机制也能放心大胆地把后续数据页提前拽进缓存。
反过来看 B 树，范围查询只能靠中序遍历，在树上跳来跳去，每一步都大概率是一次随机 I/O，数据量越大，这种差距越是天壤之别。日常 SQL 里的大于、小于、ORDER BY、GROUP BY、全表扫描，几乎处处都是“顺序流水”的场景，B+ 树这个设计简直就是为关系型数据库量身定做的。
容易被忽略的，还有内部节点精简之后的维护成本。删除或更新一条记录，B+ 树往往只需要动叶子节点，内部节点最多微调一下键值就行；而 B 树若数据恰好卡在内部节点，调整起来麻烦得多。插入分裂时，B+ 树也只需操心叶子层链表的重接和父节点的键更新，整体实现的清晰度、并发控制的复杂度，都比 B 树友好。再加上内部节点小巧紧凑，内存里能放更多索引页，缓存命中率又拉高了一截，相当于又省了一笔磁盘 I/O。
最后不得不提，B+ 树跟数据库的物理存储模型契合得天衣无缝。在 InnoDB 这样的聚簇索引里，叶子节点直接存放整行数据，索引即数据；非聚簇索引的叶子则存主键值，回表时再顺着主索引的 B+ 树去取。无论是覆盖索引直接扫叶子拿结果，还是利用叶子链表快速分页，那种“内部纯索引 + 叶子链数据”的结构，让存储引擎的代码既统一又高效。
说回来，B+ 树放弃的，只是“偶尔在内部节点提前命中”的这点运气，换来的却是更矮的身材、完全可预测的查询延迟、对顺序扫描几乎偏执的优化，以及和磁盘特性极度匹配的结构。在高并发、海量数据的真实世界里，这些取舍让 B+ 树几乎找不到对手。翻翻数据库内核的书你就会发现，B+ 树从来不是偶然的选择，而是被磁盘、SQL 模式和工程权衡三方合力推上去的那个最佳解。
评论(0)