想象你要在一座有100万本书的图书馆里找一本书。你肯定不会从第一本翻到最后一本——那得翻到猴年马月。图书馆管理员会告诉你：「去三楼东侧，计算机科学区，编号TP311.13那一排。」你走过去，扫一眼书脊，十秒就找到了。
数据库也是这样。几百万行数据摆在那，不加索引就是暴力扫描——每查一次扫全表，硬盘累死，你也等疯。所以数据库需要一种「图书分类法」，让查找变成楼层→区→排→书的过程。
问题来了：为什么几乎所有主流数据库（MySQL、PostgreSQL、SQLite）的索引底层，都选了同一种数据结构——B+树？
从二分查找说起
先回到最简单的场景。如果数据是排好序的数组 [1, 3, 5, 7, 9, 11, 13]，要找7在哪里：二分查找先看中间那个（7），一次命中，复杂度 O(log n)。听起来很完美，对吗？
但你想想，数据库的数据存在硬盘上，不是内存。硬盘读一个数据块的时间是内存的几十万倍。更麻烦的是，数据不断插入、删除、更新，排好序的数组每次插入都要挪动后面的全部元素——100万行数据的表，在最前面插一条，后面99万9999行都得往后挪一格。这谁受得了。
于是计算机科学家发明了「平衡二叉树」（AVL树、红黑树）：每次操作只影响 O(log n) 个节点，不用大规模移动数据。看起来很不错。但对数据库来说，二叉树的节点「太瘦」了——每个节点只存一个数据，树太高。100万条数据，二叉树高度大约 20 层。意味着查一次数据，硬盘要读 20 次。每次读都是慢如蜗牛的磁盘I/O。
核心矛盾出现了：二叉树数学上很好，但磁盘物理上很不喜欢它。
多叉树：把树压扁
理解了上面的矛盾，B+树的设计就呼之欲出了——如果把每个节点从「只存1个数据」改成一页能存几百个数据，树的高度就从20层降到了3层左右。查一次数据，硬盘只要读3次。
这就像图书馆不只有一个目录柜，而是每层楼放一个目录，每个目录里写着「这一排的书按这个范围排列」。你要找一本书，先翻总目录确定去三楼，到了三楼翻分区目录找到东侧，走过去扫一排就行了。
B+树具体长这样：
- 内部节点：不存实际数据，只存「门牌号范围」，像楼层指引牌一样，告诉你应该往哪棵子树走
- 叶子节点：存实际数据，并且所有叶子节点用链表串起来——这意味着你想按顺序遍历全部数据时，顺着链表走就行
- 所有叶子在同一层：树是「平衡」的，查任意一条数据需要的I/O次数都一样
三个特点合在一起，产生了几个奇妙的后果。
为什么B+树赢了B树？
你可能会问：还有个叫「B树」的东西，和B+树就差一个「+」，差别在哪？
B树的内部节点也存数据，B+树只有叶子节点存数据。这个区别看似微小，却在数据库场景下产生了巨大影响：
-
一次能索引更多数据。内部节点不存数据，只存「钥匙」，同一页能装下几百把钥匙——这意味着一棵树能管理的数据量比B树大一个数量级。
-
范围查询是神速。B+树的所有叶子都串成了链表。查「年龄在20到30之间的所有用户」时，B+树找到20的第一个叶子，然后顺着链表往前走就行。B树呢？查到20的节点后，还得在树里反复上下跳跃去找下一个节点——就像在迷宫的不同楼层之间来回跑。
-
缓存命中率高。内部节点小，操作系统更容易把它们留在内存缓存里。实际运行时，B+树的上两层可能常驻内存，绝大多数查询只需要一次硬盘I/O。
现实世界中的B+树
在MySQL的InnoDB引擎里，B+树的一个节点刚好对应一个「页」（默认16KB）。16KB能存多少「钥匙」？假设主键是BIGINT（8字节）+ 指针（6字节），一页大约能存 16384 ÷ 14 ≈ 1170 个条目。三层B+树能索引的数据量是：1170 × 1170 × 16 = 约 2190 万行数据。在四层的时候，这个数字膨胀到 1170³ × 16 ≈ 256 亿。
这就是为什么一个百万行级的表，随便你怎么查，最多读3次硬盘就能找到任何一条数据。
一点哲学思考
B+树的设计充满了「你知道物理世界什么样，所以别跟它对着干」的务实精神。计算机科学里很多优美的结构（平衡二叉树）在磁盘面前水土不服，而B+树这种看起来「粗暴」的多叉方案反而统治了数据库世界几十年。
它提醒我们一件事：最优的解决方案，往往不是数学上最优雅的那个，而是最理解物理限制的那个。
下次你在APP里点一下「我的订单」，一秒内看到所有历史记录时，背后是几百万行的数据在B+树的指引下、以最多三到四次硬盘读取的速度找到了你。而你的手机屏幕闪了一下，就过去了。