如果让我给 Java 后端面试题按出现频率排个序“聊聊 MySQL 的 B 树”绝对是前排常客甚至可以说是一道绕不过去的“必答题”。我面试这些年几乎每一轮都会遇到它有时候当主问题有时候用来引出“慢查询为什么慢”“索引为什么会失效”这类实际调优话题。它被归入八股文但它真的是一道好题因为三个字就能把“背答案的人”和“真懂的人”区分开。大多数候选人能脱口而出B 树是一种多路平衡查找树所有数据都存在叶子节点叶子节点用链表串起来支持范围查询。但再往下追问几句场面往往就开始卡壳了“为什么 MySQL 不选 B 树”“一页 16KB 到底能放多少条索引记录”“UUID 做主键为什么反而更慢”“最左前缀原则的根因是什么”这些问题全都长在同一棵树上。这篇就是想把这些背下来的结论补上推导过程顺便分享一下手撕简化版 B 树的思路对准备面试的人和日常写 SQL 想搞懂索引原理的 Java 后端工程师都适用。1. 为什么面试官总爱从 B 树开刀1.1 一道题背后藏着的三层考察点先说个我自己的观察。面试官问 B 树表面上考的是数据结构实际上想看见三层东西。第一层概念是否清晰。你能不能准确说出 B 树的定义、结构与 B 树的区别这个只要背过都能答。第二层是否理解数据库为什么这么设计。从磁盘 I/O 到页存储从局部性原理到顺序访问这些才是一个能在数据库领域独当一面的工程师该具备的视角。第三层能不能跟实际工作联动。比如“为什么建索引要选区分度高的列”“为什么不要在索引列上套函数”“为什么 JOIN 列要建索引”这些问题的答案最后都能落脚到 B 树的形态上。有过线上排查经验的人会明显占优势。我之前遇到过一次线上订单表写入抖动原因是主键是 UUID插入位置随机B 树频繁做页分裂。没经历过的人很难从“用 UUID 不好”这种结论里体会到现场有多痛。面试官问 B 树其实就是想把这类有深度的人提前筛出来。1.2 从二叉树一路“长成”B 树的几步关键推演如果不看历史直接看 B 树会觉得很突兀但把它放进数据结构演进的链条里每一步都有明确的动机。最早的二分查找要求数据有序但有序数组的插入和删除代价太高于是有了二叉搜索树。二叉搜索树在极端情况下会退化成链表于是有了 AVL 树、红黑树这类自平衡结构保证查找是 O(logN)。到这里内存里的问题基本解决了。但数据库的数据放不下内存大量数据在磁盘上这时逻辑就得变树的高度等于一次查找要经历的磁盘 I/O 次数因为每往下一层就要沿着子指针去磁盘读一个新节点。所以“减少树高”比“减少比较次数”重要得多。红黑树再平衡、再稳定它终究是二叉树存一千万数据时层数要二十多层也就是二十多次磁盘 I/O这是不能被接受的。B 树的做法是让一个节点存多个键、有多个孩子把高度压到三到四层。B 树又进一步把数据全部集中到叶子节点内部节点只存键当路标。于是能站在面试官面前的原因就齐了结构够经典、设计动机够强、展开后还能关联到一大堆实战问题。2. 拆开 B 树节点、指针、页和那棵“三层千万行”的树2.1 一切要从磁盘 I/O 说起聊 B 树之前得先把一个数字刻在脑子里磁盘随机 I/O 一次大约是 10 毫秒而内存访问大约是 100 纳秒差了十万级。数据库每秒能服务的请求数量很大程度上被这个数字卡住。所以数据库索引设计的核心目标从来只有一个尽量少触发磁盘 I/O。InnoDB 默认的页大小是 16KB也就是一次 I/O 至少读 16KB 的数据。当你从根节点往下走每读一层节点其实是一次页读取。B 树的设计要让“树高 磁盘 I/O 次数”这件事变得尽可能小因此每个节点都尽量塞满键。一个页读进来以后节点内部的查找是纯内存操作可以忽略不计。换句话说一次 I/O 换一个节点那棵树当然越矮越好。2.2 B 树和 B 树到底差在哪很多人背得出结论但说不清楚关键差异。拿张表来看对比项B 树B 树数据存放位置内部节点和叶子节点都存数据只有叶子节点存数据内部节点只存索引键叶子节点连接叶子节点之间没有链表叶子节点通过链表串联范围查询方式需要中序遍历多次回溯找到起始叶子后沿链表顺序扫描单页可容纳的索引键数少因为要腾空间存数据多空间全部留给键和指针查找路径稳定性可能在中间节点就命中路径不稳定必须走到叶子层路径长度恒定这个差异不是凑出来的细节它解决了两个实际问题。第一内部节点只存键同样 16KB 的页能装更多索引键指针扇出更大树更矮I/O 次数更少。第二叶子节点串成链表之后范围查询不再需要回溯父节点找到第一条记录然后顺着链表往下读就行。你平时写的BETWEEN、ORDER BY、LIKE 前缀%吃的都是链表顺序扫描的红利。2.3 “千万行数据三层就够”是怎么算出来的这是我很推荐大家在面试里主动演示的一段计算它能立刻把你和别的候选人区分开。假设主键用 BIGINT8 字节子节点指针在 InnoDB 里指向页号按 6 字节估算。一条非叶子节点记录大约 14 字节。一页 16KB 16384 字节16384 / 14 ≈ 1170。也就是说一个非叶子节点大概能放 1170 个键指向 1171 个子页。再看叶子节点。假设一行记录平均 1KB一个 16KB 的叶子页能存 16 行。那么2 层 B 树1170 × 16 ≈ 1.9 万行3 层 B 树1170 × 1170 × 16 ≈ 2190 万行4 层 B 树1170 × 1170 × 1170 × 16 ≈ 256 亿行所以“一张千万级的表三层 B 树就能覆盖查找只要三次 I/O”的说法是这样算出来的。这不是记忆题而是顺着页大小和键大小推出来的。面试官听到这里通常会眼睛一亮。3. MySQL 为什么偏偏选择了 B 树而不是红黑树、哈希3.1 红黑树在内存里很强在磁盘上很弱红黑树本身没有任何毛病它是内存里的优秀结构Java 的TreeMap、TreeSet底层就是它。问题只在于它是二叉树树高太大。一千万条数据红黑树的查找路径长度大约在 20 到 24 层左右等于一次查询最多要二十多次磁盘 I/O。哪怕数据库做了各种缓存热点数据都在内存里冷数据的首次访问依然会被这二十多次 I/O 拖垮。相比之下 B 树用多路平衡把高度压到三到四层一次查询 3 次 I/O 和 25 次 I/O差的不是一个量级而是系统能不能撑住的问题。红黑树适合的场景是进程内的内存数据结构你把它当作数据库索引的候选之前要先问问自己这里的瓶颈真的是 CPU 比较次数吗数据库的瓶颈当然不是IO 才是。3.2 哈希索引适合等值查询但撑不起真实业务哈希索引在等值查询上理论复杂度是 O(1)看起来比 B 树的 O(logN) 快。MySQL 的 Memory 引擎就支持哈希索引但生产环境里大多数核心表不会用它原因特别实在不支持范围查询、、BETWEEN直接失效不支持排序ORDER BY得走临时表和文件排序不支持最左前缀匹配LIKE abc%用不上哈希冲突变严重时性能还会退化真实业务里等值查询和范围查询是混在一起的。B 树刚好两者都接得住等值查询靠叶子节点的有序数组也能做二分范围查询靠叶子链表顺序扫描。这里插一句InnoDB 确实也有“自适应哈希索引”但它本质是在 B 树之上给高频访问页做缓存加速并不是一种独立的索引结构不改变 B 树作为基础组织的地位。3.3 叶子链表带来的顺序 I/O 优势还有一个容易被忽略的点叶子节点之间是用链表按序连接的这给顺序 I/O 创造了条件。机械硬盘时代顺序读比随机读快得多到了 SSD 时代虽然随机读改善很多但顺序预读依然有价值。InnoDB 有预读机制当你顺序扫描一个区的叶子页时它会提前把后续页面载入缓冲池。B 树叶子链表天然适配这种预读策略范围查询能享受近乎顺序 I/O 的待遇。哈希索引做不到红黑树也做不到因为数据物理位置不连续遍历需要反复跳转。4. 进了 InnoDB 之后聚簇索引、二级索引和回表4.1 聚簇索引InnoDB 的表本身就是一棵 B 树很多人以为表是表、索引是索引两回事。但 InnoDB 里主键索引就是整张表本身。聚簇索引的叶子节点直接存放完整行记录数据行按主键排序挂在 B 树的叶子层。这解释了一个经典结论InnoDB 表必须有主键。如果你建表时没指定主键InnoDB 会找第一个非空的唯一索引来作为聚簇索引如果连唯一索引也没有它会在内部生成一个隐藏的 ROW_ID 来当主键。这个隐藏主键对应用透明但不利于你对数据的控制。所以建表时显式指定主键不只是规范而是直接决定数据在 B 树里怎么组织。聚簇索引有个连带代价主键值会出现在每一个二级索引的叶子节点里。所以主键越短二级索引占用的空间就越小。这也是“主键尽量选整型自增别用超长字符串”的原因之一。4.2 二级索引和回表是面试常客除了主键聚簇索引其它索引都是二级索引。二级索引也是一棵 B 树但叶子节点不存整行数据只存“索引列 主键值”。执行SELECT * FROM user WHERE name 张三如果只有name索引流程是先走二级索引找到主键 id再用主键去聚簇索引里查一次完整行这个过程叫回表。回表意味着多一次 B 树查找是成本。想省掉它可以让查询列都包含在索引列里这叫覆盖索引。比如查询SELECT id, name FROM user WHERE name 张三数据在二级索引里已经拿齐EXPLAIN的 Extra 列会显示Using index不需要回表。面到覆盖索引这里通常已经算深入了。下一步面试官可能会丢出“索引下推”这也是吃 B 树形态的优化。4.3 索引下推在叶子节点内提前过滤索引下推ICPIndex Condition Pushdown是 MySQL 5.6 引入的优化。拿联合索引(name, age)举例查询条件是WHERE name LIKE 张% AND age 20。没有 ICP 时InnoDB 会把所有姓张的记录从索引里捞出来逐一回表拿整行再在服务层过滤age 20。有 ICP 后age 20这个判断被下推到存储引擎直接在叶子页扫描时就过滤掉只回表真正满足条件的行。表面看这是个执行计划优化根源依然是 B 树叶子节点存储了完整的索引键可以在索引层完成多字段判断。EXPLAIN的 Extra 列显示Using index condition就是它触发了。5. 从增删改看 B 树页分裂、自增主键和最左前缀5.1 页分裂是怎么发生的代价有多大B 树不是只读结构插入和删除都会改变节点形状。当插入一条记录目标叶子页满了就必须分裂把一半记录搬到新页在叶子链表里接入新页再把一个分隔键插入父节点。如果父节点也满就继续向上分裂最坏一路裂到根节点树高加一。页分裂的成本不只是多写一次磁盘。分配新页、重写父子页、更新指针这一串操作都会增加 I/O高并发下还可能造成页面闩锁竞争。对一个频繁插入的热点表来说页分裂是实实在在的性能杀手。理解了这一点你就会明白为什么生产环境那么强调主键有序性。5.2 自增主键和 UUID 主键的差距就在这里自增主键插入时新记录基本追加到当前最右侧叶子页B 树不需要频繁分裂表空间也更紧凑。UUID 主键则是随机的新记录可能落在任意一个叶子页命中一个快满的页就得分裂还容易留下很多半满页既浪费空间又增加随机 I/O。我之前维护过一张日志流水表最初的主键设计就是 UUID写入高峰时段经常出现大量“页分裂”相关的性能毛刺。后来把主键改成自增 BIGINT配合按时间分表情况立刻好转。面试时提到这个场景比干背“自增更快”有说服力得多。5.3 那些经典索引问题的根因全在树结构里很多 Java 面试题看着是 MySQL 使用规范根子其实都在 B 树为什么有最左前缀原则联合索引按第一列、第二列的顺序在页内排序跳过了第一列后续列的有序性无从谈起。为什么索引列不要套函数函数改变了键的原始顺序B 树按原值组织无法对函数结果做二分查找。为什么索引列不宜太长键越长一个页能装的键越少同样千万行数据树就越高I/O 次数增加。为什么SELECT *不推荐它很可能让覆盖索引失效迫使 MySQL 回表取完整行。这些问题的模板答案网上到处都有但如果能把每一条都落回“B 树的有序性和扇出”上面试官基本会认为你是真理解而不是背题库。6. 手撕一个简化版 B 树Java 实现与面试演示6.1 手撕目标证明你懂分裂而不是要写生产代码面试里被要求手写 B 树时不要慌。面试官不是要一个能上生产线的 B 树而是要看你理解不理解“节点分裂”和“指针维护”这两个核心机制。我建议写一个内存版简化实现只存 int 键每节点最多 4 个键不落盘不考虑并发不处理删除。核心逻辑就是三步找叶子节点、插入有序数组、满了就分裂上提。6.2 核心结构节点类与查找插入下面是一个能演示核心逻辑的 Java 实现我保留了类定义、查找、插入和分裂部分。import java.util.Arrays; public class SimpleBPlusTree { private static final int MAX_KEYS 4; // 每个节点最多 4 个 key private Node root; static class Node { int[] keys; int keyCount; Node[] children; // 内部节点使用 Node parent; Node next; // 叶子节点指向右兄弟 boolean leaf; Node(boolean leaf) { this.leaf leaf; this.keys new int[MAX_KEYS]; this.keyCount 0; this.parent null; this.next null; if (!leaf) { this.children new Node[MAX_KEYS 1]; } } } public boolean search(int key) { if (root null) return false; Node leaf findLeaf(key); for (int i 0; i leaf.keyCount; i) { if (leaf.keys[i] key) return true; } return false; } private Node findLeaf(int key) { Node cur root; while (!cur.leaf) { int i 0; while (i cur.keyCount key cur.keys[i]) i; cur cur.children[i]; } return cur; } public void insert(int key) { if (root null) { root new Node(true); root.keys[0] key; root.keyCount 1; return; } Node leaf findLeaf(key); insertIntoLeaf(leaf, key); if (leaf.keyCount MAX_KEYS) { split(leaf); } } private void insertIntoLeaf(Node leaf, int key) { int pos leaf.keyCount - 1; while (pos 0 leaf.keys[pos] key) { leaf.keys[pos 1] leaf.keys[pos]; pos--; } pos; leaf.keys[pos] key; leaf.keyCount; } private void split(Node node) { int mid node.keyCount / 2; int upKey node.keys[mid]; Node right new Node(node.leaf); right.parent node.parent; // 叶子节点从 mid 开始把后半段搬到新节点 // 内部节点mid 位置的 key 上提到父节点后半段从 mid 1 开始搬 int transferFrom node.leaf ? mid : mid 1; int idx 0; for (int i transferFrom; i node.keyCount; i) { right.keys[idx] node.keys[i]; } right.keyCount idx; if (!node.leaf) { idx 0; for (int i mid 1; i node.keyCount; i) { right.children[idx] node.children[i]; if (right.children[idx] ! null) { right.children[idx].parent right; } idx; } right.keyCount idx - 1; } if (node.leaf) { right.next node.next; node.next right; } node.keyCount node.leaf ? mid : mid; if (node.parent null) { Node newRoot new Node(false); newRoot.keys[0] upKey; newRoot.children[0] node; newRoot.children[1] right; newRoot.keyCount 1; node.parent newRoot; right.parent newRoot; root newRoot; } else { insertIntoInternal(node.parent, upKey, right); if (node.parent.keyCount MAX_KEYS) { split(node.parent); } } } private void insertIntoInternal(Node node, int key, Node rightChild) { int pos node.keyCount - 1; while (pos 0 node.keys[pos] key) { node.keys[pos 1] node.keys[pos]; node.children[pos 2] node.children[pos 1]; pos--; } pos; node.keys[pos] key; node.children[pos 1] rightChild; node.keyCount; } public static void main(String[] args) { SimpleBPlusTree tree new SimpleBPlusTree(); for (int i 1; i 50; i) { tree.insert(i * 2); } System.out.println(tree.search(100)); // true System.out.println(tree.search(101)); // false } }运行结果 true false6.3 面试手撕时的讲解重点代码写完后关键是能讲清两个细节。第一个是分裂时的边界选择叶子节点分裂后分隔键可以留在右侧节点中同时上提到父节点因为 B 树父节点保存的本来就是“右子节点的最小键”。第二个是内部节点和叶子节点的孩子数量差别有 k 个键的内部节点有 k1 个孩子分裂搬孩子时要盯住“孩子数始终比键数多 1”这个约束代码里节点数组大小就按MAX_KEYS 1来开。生产版本远比这复杂还要处理值数组、父指针的完整维护、删除后的合并、页的磁盘序列化以及并发访问控制。面试时你主动说一句“这个演示版省略了这些实际工程里还要考虑……”反而能体现你清楚 B 树的完整复杂度边界在哪里。我个人在实际面试和带新人时有个体会与其背一百条“索引最佳实践”不如把 B 树这一棵树的原理吃透。很多看似独立的 MySQL 问题——索引失效、慢查询、分表键选择、主键设计——到最后都是同一个答案的不同侧面。面试时如果被追问到“为什么”试着从磁盘 I/O 开始讲再落到“一页能放多少键”的计算上这个回答框架既自然又经得起追问。希望这篇能帮你把那些背下来的八股文变成真正长在自己知识树上的东西。