2、B+树深度剖析：层高计算、扇出因子与InnoDB的选择

聊到数据库索引，B+树是个绕不开的话题。很多同学背过它的定义，但真问到「为什么MySQL偏偏选了它？」就卡壳了。今天咱们把这棵树彻底扒开看看。

2.1 先聊聊B+树长什么样

说白了，B+树就是一棵「矮胖」的树。跟二叉树那种瘦高个儿不一样，B+树的每个节点能装很多个键值对。我习惯把它想象成一个多层抽屉的档案柜——最底层的叶子节点存真实数据，上层的非叶子节点只存「路标」。

这里有个关键设计：所有数据都落在叶子节点上，而且叶子节点之间用指针串成了有序链表。这意味着什么？你想想看，做范围查询时，找到第一个符合条件的记录后，顺着链表往后撸就行了，不用再回溯到父节点。

2.2 层高计算——树到底能长多高？

这是面试高频题。B+树的层高决定了查询需要几次磁盘I/O。层高越低，查询越快。

计算公式很简单：

层高 h = log_{扇出因子}(数据总量 / 每个叶子节点记录数) + 1

举个例子。假设InnoDB的页大小是16KB，一个索引键（比如bigint）占8字节，加上指针占6字节左右，一行索引记录约14字节。那么一个非叶子节点能装的记录数（扇出因子）大约是：

扇出因子 ≈ 16KB / 14B ≈ 1170

再假设每个叶子节点能存100条数据行（实际取决于行大小）。那么：

• 2000万行数据：层高 ≈ log_{1170}(20000000/100) + 1 ≈ 3
• 2亿行数据：层高 ≈ log_{1170}(200000000/100) + 1 ≈ 3

看到了吗？千万级和亿级数据，层高居然差不多！这就是B+树「矮胖」的威力。我在项目中遇到过一张5亿行的订单表，B+树索引也就4层高。每次查询最多4次磁盘I/O，这性能能不好吗？

2.3 扇出因子——决定树高矮的关键

扇出因子，就是每个非叶子节点能「扇出」多少个子节点。它直接决定了树的宽度和高度。

扇出因子越大，树越矮。为什么？因为每个节点能装更多「路标」，树的分支就多，层数自然就少了。

影响扇出因子的因素：

• 索引键大小：键越短，一个节点能装的记录越多。所以用int比用varchar(100)做索引好得多。
• 页大小：InnoDB默认16KB，可以调大。但调大了也有代价——浪费内存。
• 指针大小：这个基本固定，6字节左右。

我曾经优化过一个慢查询，排查发现索引键是varchar(255)，实际存的都是短字符串。我建议改成前缀索引，扇出因子从200提升到800，层高从4降到了3。查询响应时间直接砍半。

2.4 为什么MySQL InnoDB选了B+树？

这个问题，说白了就是B+树在磁盘I/O场景下太能打了。咱们对比一下就明白了。

数据结构	磁盘I/O次数（百万级数据）	范围查询	插入/删除
哈希表	1-2次	不支持	O(1)平均
二叉搜索树	20次左右	支持，但需回溯	O(log n)
B树	3-4次	支持，但需中序遍历	O(log n)
B+树	3-4次	叶子链表，极快	O(log n)

你看，哈希表虽然单点查询快，但没法做范围查询。二叉搜索树层数太高，磁盘I/O受不了。B树虽然层数也低，但非叶子节点存了数据，导致扇出因子变小，而且范围查询需要来回回溯。

B+树把数据和索引分离，非叶子节点只存「路标」，扇出因子大，树矮。叶子节点用链表串起来，范围查询就是链表遍历。这设计，简直就是为磁盘I/O量身定做的。

嗯，这里要注意一点：B+树的插入和删除可能会触发节点分裂或合并，但因为有「半满」机制，实际开销可控。我在线上见过一张表，频繁插入导致B+树节点分裂频繁，但通过调整填充因子（MERGE_THRESHOLD）就解决了。

2.5 一张图看懂B+树核心逻辑

下面这张SVG图，展示了B+树的核心结构。你可以看到非叶子节点只存键和指针，叶子节点存数据且形成链表。

从这张图可以清楚看到：查询数据时，从根节点一路向下，经过3层就到达叶子节点。叶子节点之间通过指针串联，做范围查询时，找到起点后顺着链表走就行，不用再往上回溯。

这就是B+树的精髓——用空间换时间，用「矮胖」换I/O效率。我个人觉得，理解了B+树的设计哲学，才算真正懂了MySQL索引。