B树和B+树：数据库背后的高效存储逻辑

你有没有想过，为什么数据库在几百万条数据里找一条记录，还能秒出结果？其实这背后离不开一种叫“B树”和“B+树”的数据结构。它们就像图书馆的图书索引系统，帮你快速定位目标，而不是一本本翻。

B树：平衡多路搜索树

B树是一种自平衡的树结构，特点是每个节点可以有多个子节点，不像二叉树只能有两个分支。它的设计目标是减少磁盘I/O次数——毕竟数据库的数据大多存在硬盘上，读一次慢一次。

比如一个3阶B树，每个节点最多存2个关键字，分成3个子树。查找时从根节点开始，利用有序性快速跳转到对应区间。这样即使数据量很大，树的高度也能控制在3~4层，查起来也就3~4次磁盘读取。

B+树：B树的升级版

你在用MySQL的时候，InnoDB引擎默认用的就是B+树。它和B树最大的不同在于：所有数据都存在叶子节点，非叶子节点只存索引。而且叶子节点之间用指针连成链表，方便范围查询。

举个例子，你要查“销售额在10万到50万之间的订单”，B+树能顺着链表一路扫过去，而B树可能得反复上下树，效率差不少。

代码结构示意

虽然实际实现复杂，但B+树的节点结构大概长这样：

struct BPlusNode {
    bool is_leaf;
    vector<int> keys;
    vector<BPlusNode*> children;
    BPlusNode* next; // 叶子节点的后向指针
};

插入和分裂逻辑会保证树始终平衡。比如叶子节点满了，就拆成两个，并把最小值提上去，父节点也可能跟着分裂，直到根节点。一旦根分裂，树就长高一层——但这种情况很少见。

为什么数据库偏爱它们？

关键还是“少读磁盘”。B树和B+树通过增大节点、减少树高，让每次查找尽可能命中缓存或一页磁盘数据。特别是B+树，顺序访问能力强，适合数据库常见的范围扫描场景。

下次你执行一条SELECT语句看到毫秒级响应，别忘了背后可能是B+树默默跑了几十行C++代码，在千万级数据中精准导航。