B+树的数学之美与工程演进：从数据结构到数据库索引的千年之旅

引言

当你在一个拥有上亿条记录的表中执行SELECT操作时，数据库可能在毫秒级内返回结果。这背后依赖着一个优雅而高效的数据结构 —— B+树。它不仅仅是教科书上的算法范例，更是现代数据库系统的基石。

本文将带你穿越数据结构的发展脉络，从二叉搜索树的红黑变体，到多路平衡搜索树的实际应用，最终聚焦于B+树在数据库索引中的核心地位。

一、搜索结构的演化

1.1 有序数组与二分查找

最朴素的搜索结构是有序数组配合二分查找，时间复杂度O(log n)。但插入和删除需要O(n)时间维护有序性。

1.2 自平衡二叉搜索树

AVL树严格维护左右子树高度差不超过1，红黑树放宽约束减少旋转次数。但二叉结构在磁盘场景下问题显著：10层高的红黑树意味着10次I/O。

二、B+树：为磁盘量身定制

B+树在B树基础上做了三个关键改造：第一，数据全部存储在叶子节点，内部节点仅存储索引键；第二，叶子节点通过链表串联；第三，以填充因子控制密度。

假设InnoDB页为16KB，索引键BIGINT（8字节），指针6字节，单个内部节点可容纳1170个键。三层B+树可索引约2192万行 —— 最多3次磁盘I/O。

三、真实数据库实现

MySQL InnoDB使用聚簇索引与辅助索引分离设计，短主键优于UUID。PostgreSQL使用TOAST、De-duplication等精细优化。SQLite整个数据库文件即一棵B-Tree。

四、工程优化策略

覆盖索引消除回表、最左前缀匹配、填充因子调优。B+树和LSM树代表读优化与写优化两个方向。向量搜索中HNSW、IVF-PQ、DiskANN成为新选择。

从1972年到今天，B+树经历了半个多世纪的考验，依然是计算机科学中最成功的抽象之一。