1. 前言在面试后端开发、数据库内核、存储引擎相关岗位时「B 树和 B 树的原理及区别」几乎是必考题目。这个问题看似基础却能把候选人对数据结构、磁盘 I/O、操作系统页缓存、索引设计等知识的理解程度一次问透。很多人能背出「B 树所有数据都在叶子节点」「叶子节点之间有链表」这几句话但一旦面试官追问「为什么 MySQL 不用 B 树而用 B 树」「为什么非叶子节点不存数据」「一个节点到底能放多少个 key」「B 树的高度怎么估算」往往就答不完整。本文尝试用大约 2 万字的篇幅从最基础的二分查找、磁盘 I/O 特性讲起逐步推导出 B 树和 B 树的设计动机再详细讲解两者的定义、查找、插入、删除等核心算法最后通过对比表格和面试题清单帮助你建立一套完整的知识体系。阅读建议如果你只想快速回顾面试答案可以直接跳到第 11 节看对比表格和第 12 节看常见面试题如果想真正理解「为什么」建议从头开始重点关注前 5 节的推导过程。2. 一切从「查找」说起索引本质上是为了加速查找。在讨论 B 树和 B 树之前我们先回顾几种最基本的查找结构理解它们在数据量变大之后会遇到什么问题。2.1 顺序查找顺序查找是最朴素的做法从数组或链表的第一个元素开始逐个和目标值比较直到找到或者遍历结束。它的时间复杂度是 O(n)。当数据量只有几百条时顺序查找完全够用但当数据量达到千万、亿级别时线性扫描的时间成本会高到无法接受。顺序查找的最大优点是结构简单、对数据是否有序没有任何要求。但它的缺点同样明显每次查找平均要比较一半的元素失败查找更是要把全部元素都扫一遍。2.2 二分查找如果数据已经按关键字有序存储在一个可以随机访问的结构比如数组中我们就可以使用二分查找。二分查找每次取中间元素和目标值比较如果中间元素等于目标值查找结束如果中间元素大于目标值说明目标值只可能在左半区缩小范围继续查找如果中间元素小于目标值说明目标值只可能在右半区缩小范围继续查找。二分查找每次比较都能把问题规模缩小一半因此时间复杂度是 O(log₂n)。这个复杂度在数据量很大时优势非常明显对于 10 亿条数据二分查找最多只需要大约 30 次比较。public class BinarySearch { public static int search(int[] arr, int target) { int left 0; int right arr.length - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return -1; } }然而二分查找有一个致命的前提数据必须存放在内存中的连续数组里。当数据规模超过内存容量时数据只能落盘而磁盘的访问方式和内存完全不同。这就是引出 B 树的关键。3. 磁盘 I/O多路搜索树诞生的真正原因很多教材直接给出 B 树的定义却没有解释「为什么要多路」导致很多人只会背定义。其实 B 树的本质动机只有一个减少磁盘 I/O 次数。3.1 内存访问和磁盘访问的差距计算机存储体系是分层的CPU 寄存器最快其次是一级缓存、二级缓存、三级缓存然后是内存最后是磁盘。每一层之间的访问速度差距通常是一个数量级甚至更多。粗略来看访问一次内存的延迟大约是几十到一百纳秒访问一次机械硬盘的延迟大约是几毫秒其中主要是寻道时间和旋转延迟即便是 SSD随机读的延迟也在几十微秒量级仍然比内存慢 2 到 3 个数量级。也就是说一次磁盘 I/O 的时间代价足够执行几十万甚至上百万次内存操作。因此对外存数据结构来说优化的首要目标不是「少比较几次」而是「少读几次盘」。3.2 磁盘的「块」和操作系统的「页」磁盘并不是按字节读取的。机械硬盘的最小寻址单位是扇区通常是 512 字节或 4096 字节操作系统在和磁盘交互时则以「页」为单位典型大小是 4KB。即使你只想读 1 个字节操作系统也会把包含这个字节的整个页读进内存。这个特性对数据结构设计有重大影响如果我们能把经常一起访问的数据放在同一个页里一次 I/O 就能把它们全部读进来后续对它们的访问就不再需要额外的磁盘 I/O。B 树和 B 树正是利用了这个特性。它们把节点的大小设计成接近一个页的大小或者页大小的整数倍一次磁盘 I/O 就能读取一个完整节点节点内部的查找完全在内存中完成。3.3 从二叉树到多路树传统的二叉搜索树BST每个节点只保存一个关键字、最多只有两个孩子。对于存放在内存中的平衡二叉树如 AVL 树、红黑树查找时间复杂度是 O(log₂n)非常优秀。但是当数据大到必须放在磁盘上时问题就出现了。假设有 10 亿条记录用平衡二叉树存储树高大约是 log₂(10⁹) ≈ 30。这看起来不大但在磁盘背景下树高近似等于查找过程中需要进行的磁盘 I/O 次数。如果每次查找都要进行 30 次随机磁盘 I/O即使每次只有 5 毫秒合计也要 150 毫秒对高并发数据库来说是完全不可接受的。能不能让树「变矮」答案就是把二叉树变成多路搜索树每个节点不只保存一个关键字而是保存多个关键字拥有更多的孩子。假设每个节点能放 1000 个关键字、拥有 1001 个孩子那么 3 层树就能容纳大约 10 亿个关键字查找时最多只需要 3 次磁盘 I/O。这种「矮胖」的多路平衡搜索树就是 B 树的雏形。4. 为什么 AVL 树和红黑树不适合做磁盘索引理解了磁盘 I/O 特性之后就能很清楚地回答这个经典问题为什么数据库索引不用 AVL 树、红黑树这类二叉平衡树树高太高二叉树每个节点只有一个关键字节点数量等于关键字数量。上亿条数据意味着树高达到 20 到 30 层以上每层都可能触发一次磁盘 I/O。节点过小浪费页一个二叉树节点通常只有几十字节而操作系统一次 I/O 会读 4KB 甚至更大的页。也就是说为了读一个几十字节的节点却要付出读取整个页的代价其余数据都没用上。更糟的是二叉树的节点在内存中分散存放一个页里很难装下父子节点导致每次访问一个节点都可能是一次随机 I/O。无法高效利用局部性B 树把大量关键字聚合在一个节点里一次 I/O 读入一个节点后可以在内存中完成几十次、几百次比较大大摊薄了 I/O 成本。所以结论是AVL 树和红黑树本身是非常优秀的内存数据结构但它们的设计假设是「节点访问成本相同且便宜」而磁盘场景下节点访问成本极高因此必须使用能够把树压矮、把节点做大的多路搜索树也就是 B 树。5. B 树的定义与性质B 树B-tree是一种自平衡的多路搜索树。它由 Rudolf Bayer 和 Edward M. McCreight 在 1970 年左右提出。「B」的含义有多种说法常见的有 Balanced、Bayer、Boeing 等但学术界普遍认同它是一种平衡树这一点比字母本身更重要。5.1 严格的 B 树定义一棵 m 阶degreeB 树或者说一棵阶数为 m 的 B 树是满足以下性质的空树或非空树每个节点至多有 m 个孩子除根节点外每个非叶子节点至少有 ceil(m/2) 个孩子若根节点不是叶子节点则根节点至少有 2 个孩子一个有 k 个孩子的非叶子节点恰好包含 k-1 个关键字所有叶子节点都出现在同一层并且不携带信息或携带指向数据的指针节点内部的关键字按从小到大排序并且节点满足搜索树的性质对于关键字 key[i] 和它的左右孩子左子树中所有关键字都小于 key[i]右子树中所有关键字都大于 key[i]。需要注意的是不同教材对于「阶」的口径略有差别。有的教材用「m 阶」表示节点最多有 m 个孩子这种情况下节点最多有 m-1 个关键字有的地方直接说「节点最多有 m 个关键字」。本文统一采用经典定义m 阶 B 树的节点最多有 m 个孩子、最多 m-1 个关键字除根节点外每个节点至少能有 ceil(m/2) 个孩子、至少 ceil(m/2)-1 个关键字。5.2 一个直观例子下图用文字描述一棵 5 阶 B 树每个节点最多 5 个孩子、最多 4 个关键字除根外至少 3 个孩子、至少 2 个关键字[ 20 | 40 | 60 ] / | | \ [5|10] [25|30] [45|50] [70|80|90] / | \ / | \ / | \ / | | \ 叶子们全部在同一层这棵树有 3 层。根节点有 3 个关键字因此有 4 个孩子第二层每个节点都有 2 到 3 个关键字满足「除根外至少 2 个关键字」的约束所有叶子节点位于同一层保证了树的绝对平衡。5.3 B 树高度的估算B 树之所以能支撑海量数据关键在于它能被压得非常矮。下面推导 B 树高度与关键字数量的关系。设一棵 m 阶 B 树除根节点外每个节点至少有 ceil(m/2) 个孩子记为 tt ceil(m/2)常被称为最小度数 minimum degree。那么第 0 层根至少有 1 个节点、至少 1 个关键字第 1 层至少有 2 个节点至少 2(t-1) 个关键字第 2 层至少有 2t 个节点至少 2t(t-1) 个关键字第 h 层至少有 2t^(h-1) 个节点。因此高度为 h 的 B 树至少包含的关键字个数为n ≥ 1 (t-1) × (2 2t 2t² ... 2t^(h-2)) 1 2(t-1) × (t^(h-1) - 1) / (t - 1) 2t^(h-1) - 1由此可以得到高度上限h ≤ log_t((n1)/2)对于 5 阶 B 树t3。如果有 10 亿个关键字高度上限大约是 log₃(5×10⁸) ≈ 18 左右。如果换成常见的更大阶数例如每个节点能放 1000 个关键字此时 t≈501那么 10 亿条数据的高度大约只有 log₅₀₁(10⁹) ≈ 3也就是最多 3 到 4 次磁盘 I/O 就能完成一次查找。这就是 B 树「矮胖」结构带来的巨大价值。6. B 树的查找B 树的查找过程和二叉搜索树非常相似区别在于每个节点内有多个关键字需要先在当前节点内部找到合适的位置再决定进入哪个孩子节点。6.1 查找算法描述假设我们要在 B 树中查找关键字 k从根节点开始。在当前节点内部内存中查找 k因为节点内关键字有序可以直接使用二分查找或用线性扫描。如果在当前节点中找到了 k查找成功返回对应位置。如果没找到根据 k 落在哪两个相邻关键字之间确定应该进入哪个孩子节点然后继续递归查找。如果到达叶子节点仍然没找到说明 k 不存在查找失败。6.2 查找伪代码BTreeSearch(node, k): i 0 while i node.n and k node.keys[i]: i i 1 if i node.n and k node.keys[i]: return (node, i) // 在当前节点找到 if node.isLeaf: return null // 已是叶子未找到 return BTreeSearch(node.children[i], k)6.3 时间复杂度分析B 树的查找分为两个维度沿树向下走的层数即树高 h决定了磁盘 I/O 次数。对于大阶数 B 树h 通常只有 3 到 4。每个节点内部的比较次数节点内关键字有序使用二分查找的复杂度是 O(log₂m)其中 m 是节点可容纳的最大关键字数。如果节点大小固定为 4KBm 通常为几百到上千内部的 log 运算代价很小。因此B 树查找整体非常高效磁盘 I/O 次数极少内存内比较次数也层层降低。7. B 树的插入与分裂B 树的插入比查找复杂因为它必须维护「所有叶子都在同一层」这个平衡性质。核心机制是节点满了就分裂并且分裂产生的新关键字向上提升到父节点。7.1 基本插入流程先执行一次查找定位到目标关键字应该插入的叶子节点。如果该叶子节点还有空闲位置关键字数小于 m-1直接按顺序插入即可。如果该叶子节点已经满了关键字数等于 m-1插入后会有 m 个关键字违反 B 树约束需要进行分裂。7.2 节点分裂split所谓分裂就是把一个满节点从中间拆成两个节点并把中间的关键字提升到父节点中。具体步骤如下假设当前节点有 m-1 个关键字、插入后临时为 m 个关键字找到中间位置通常是下标 ceil(m/2) 或从左数第 t 个关键字tceil(m/2)。把该中间关键字从原节点中取出准备提升到父节点。原节点左半部分middle 左边的关键字和孩子保留在原节点右半部分middle 右边的关键字和孩子放入一个新创建的节点把中间关键字插入父节点的适当位置并让父节点指向新分裂出的右节点。如果父节点也满了递归地继续分裂父节点如果一直分裂到根节点则创建一个新的根节点树的高度加 1。正是「根节点分裂」这一操作会让树整体长高且由于只有根节点分裂才会增加高度而分裂是从下往上传播的因此所有叶子节点的深度始终一致树的平衡性得以维护。7.3 一个插入分裂的例子考虑一棵 5 阶 B 树的某个叶子节点里面已经有 4 个关键字[ 10 | 20 | 30 | 40 ]现在向这个叶子节点插入关键字 25。由于节点内关键字必须保持有序插入后的临时状态为[ 10 | 20 | 25 | 30 | 40 ] // 插入后临时有 5 个关键字5 阶 B 树每个节点最多只能有 4 个关键字因此这个节点违反了约束必须分裂。取中间关键字第 3 个25 提升到父节点原节点拆成左右两个节点左节点[ 10 | 20 ] 右节点[ 30 | 40 ] 父节点新增关键字25并分别指向左、右两个子节点如果父节点原本还有空闲位置这次插入就结束了如果父节点也因为新增 25 而变满则继续对父节点重复上述分裂过程直到不再违反约束为止。若分裂一直传播到根节点根节点分裂后会创建一个新根树的高度加 1。这就是 B 树在插入过程中保持平衡的核心机理。8. B 树的删除删除操作比插入更复杂因为它不仅可能让节点变空还可能让节点关键字数低于下限 ceil(m/2)-1。总体策略是先想办法让目标关键字落到叶子节点再在叶子节点中删除如果删除后节点关键字过少就通过「借关键字」或「合并节点」来恢复 B 树约束。8.1 删除的基本情况设最小度数 t ceil(m/2)除根节点外每个节点至少应有 t-1 个关键字。删除关键字 k 时可以分成两种情况k 在叶子节点中直接删除即可。如果删除后该叶子节点仍有至少 t-1 个关键字删除结束否则进入「下溢」处理。k 在内部节点中找到 k 的前驱关键字左子树最右下的关键字或后继关键字右子树最左下的关键字替换 k然后在对应的叶子节点中删除该前驱或后继关键字。这样就把删除内部关键字的问题转化为删除叶子关键字的问题。8.2 借位与合并当某个节点删除后关键字数不足 t-1也就是发生「下溢」时需要依据兄弟节点的情况处理向左/右兄弟借关键字如果相邻兄弟节点关键字数大于 t-1就可以把父节点中的一个关键字「下沉」到当前节点同时把兄弟节点中的一个关键字以及对应孩子「上移」到父节点。本质上是把父节点关键字和兄弟节点关键字做一次旋转。与兄弟节点合并如果相邻兄弟节点都只有 t-1 个关键字无法再借就把当前节点、父节点中的一个关键字、兄弟节点合并成一个节点。合并会让父节点少一个关键字父节点可能继续下溢因此需要递归向上处理如果根节点最后被合并空了就把合并后的节点作为新的根树的高度减 1。借位不会改变树高合并可能减少父节点关键字数最坏情况下会一直传播到根并导致树变矮。这也保证了 B 树始终「自底向上」地维持平衡。8.3 一个删除的例子假设一棵 5 阶 B 树中某叶子节点为[ 10 | 20 | 30 ]在 5 阶 B 树中t3叶子节点至少应有 t-12 个关键字。若删除 10节点变为[ 20 | 30 ]仍满足下界删除直接完成。若原节点只有[ 10 | 20 ]删除 10 后只剩 1 个关键字发生下溢。此时若右兄弟是[ 40 | 50 | 60 ]可以从右兄弟借一个关键字。假设父节点分界关键字是 35借位后父节点分界关键字变为 40原右兄弟变为 [50|60]当前节点变为 [20|35]恢复合法状态。9. B 树的定义与性质B 树是 B 树在数据库索引场景下最常见的变体也是 MySQL InnoDB 等存储引擎默认使用的索引结构。它保留了 B 树「矮胖、多路、自平衡」的全部优点同时对数据存储和范围查询做了专门优化。9.1 严格的 B 树定义一棵 m 阶 B 树满足以下性质与 B 树相同每个内部节点至多有 m 个孩子除根外至少 ceil(m/2) 个孩子所有叶子节点在同一层。非叶子节点只保存索引关键字用于路由不保存真实数据记录。非叶子节点有 k 个孩子时恰好包含 k-1 个关键字。所有真实数据都保存在叶子节点中。叶子节点包含全部关键字以及指向对应数据记录的指针。叶子节点之间按关键字顺序用链表串连通常为双向链表以支持高效的范围查询和顺序扫描。内部节点的关键字是孩子节点中键值范围的「副本」或「上界值」。例如某个内部关键字值 v意味着左子树中所有键 ≤ v右子树中所有键 v不同实现有细微差别。9.2 B 树与 B 树的关键区别数据存放位置不同B 树的关键字和数据可以同时出现在内部节点B 树的数据只出现在叶子节点内部节点只是纯索引。查询稳定性不同B 树任何值的查找路径长度都相同都必须走到叶子节点查找时间更稳定。范围查询效率不同B 树叶子节点有链表定位起点后顺序扫描即可B 树范围查询需要反复在树中上下回溯。扇出更大因为内部节点不存数据单个索引项更小一个节点能容纳更多关键字树更矮I/O 次数更少。9.3 一个直观例子一棵 5 阶 B 树的简化结构如下[ 30 | 60 ] / | \ [10|20] [30|45] [60|80] | | | 叶子: [10]-[20] [30]-[45] [60]-[80] 叶子之间还有双向链表相连注意内部节点中的 30、60 只是索引边界真实关键字 10、20、30、45、60、80 全部出现在叶子节点里查找任何值都必须走到叶子层这也解释了为什么 B 树查找成本是稳定的。10. B 树的查找、插入与删除B 树的操作整体遵循 B 树的框架区别主要来自「数据都在叶子」「叶子之间有链表」「内部节点保存副本」这三点。10.1 查找从根节点开始在内部节点中找到正确的孩子并逐层向下最终一定会到达叶子节点。在叶子节点中用顺序或二分方式找到关键字若存在则返回指向数据记录的指针不存在则查找失败。由于内部节点只存索引、扇出更大树高通常比 B 树更低。对于千万、亿级数据B 树高度通常稳定在 3 到 4 层查找需要 3 到 4 次磁盘 I/O范围查找在定位到起点叶子后顺着链表向后读取即可非常高效。10.2 插入与分裂插入总是发生在叶子节点。找到目标叶子并插入后如果叶子节点关键字数超过上限就进行分裂把中间关键字提升到父节点同时保留叶子节点之间的链表关系。叶子分裂时被提升到父节点的关键字通常还会保留在右叶子中作为最小键副本这保证了查找时能正确路由。定位目标叶子节点并插入新关键字。若叶子节点未满插入结束若已满分裂成左右两个叶子中等关键字提升到父节点。维护叶子链表左叶子的 next 指向右叶子右叶子的 prev 指向左叶子。若父节点因插入新索引关键字而变满父节点同样需要分裂并继续向上传播根分裂时树高加 1。10.3 删除删除同样发生在叶子层。删除叶子中的关键字后叶子未下溢删除直接结束。父节点中的索引副本键可以保留不动即使该关键字在叶子中已不存在只要它仍能作为正确的分界值即可也有的实现会更新为新的最小键。叶子下溢优先向相邻叶子借关键字若兄弟也不足则与兄弟合并。合并后需要更新父节点索引并递归处理父节点下溢。总体上说B 树的删除与 B 树思路一致先转换到叶子删除再通过借位或合并自底向上修复平衡。11. B 树与 B 树对比这张对比表可以帮助你在面试或实际选型时快速回答「B 树和 B 树到底差在哪里」对比维度B 树B 树数据存放关键字和数据可同时存在于内部节点数据只存叶子节点内部节点仅存索引查找稳定性可能在某层提前命中路径长度不一致任何查找都要到叶子路径长度稳定范围查询需要在中序方式下反复回溯定位起点后沿叶子链表顺序扫描树高节点包含数据扇出相对较小树相对更高内部节点小、扇出大树更矮更新代价插入删除后局部调整即可额外维护叶子链表和索引副本实现更复杂空间利用内部节点也存数据空间利用率较高叶子存全部数据内部索引会额外占用空间典型用途适合键值访问、无强范围扫描场景数据库索引首选项如 MySQL InnoDB一句话总结B 树牺牲了一定的写入和维护复杂度换来了更矮的树高、更稳定的单点查询和更高效的范围扫描因此更适合数据库这类读写混合、范围查询频繁的持久化索引场景。12. 常见面试题清单最后把这些高频问题整理成一份自测清单。建议每题都能用自己的话解释清楚而不是只会背答案为什么数据库索引不用 AVL 树、红黑树而用 B 树或 B 树B 树的「阶」是什么意思m 阶 B 树节点最多有几个孩子、几个关键字B 树为什么所有叶子节点必须在同一层根节点分裂时树高怎么变化B 树插入后节点满了怎么办请描述分裂过程。B 树删除时节点关键字数低于下限怎么办借位和合并有什么区别B 树和 B 树的主要区别有哪些为什么 MySQL InnoDB 选择 B 树B 树中内部节点保存的关键字和数据有关系吗是否一定在叶子节点中重复出现B 树叶子节点之间的链表有什么作用对范围查询和排序有什么帮助如何估算一棵 B 树或 B 树的高度10 亿条数据大概需要多少层为什么 B 树非叶子节点不存数据可以提高扇出、降低树高什么是聚簇索引、二级索引它们和 B 树有什么关系B 树的插入、删除分别会触发哪些维护操作哪些情况会导致树变高或变矮13. 总结从二分查找到磁盘 I/O从 B 树到 B 树整个推导链条的核心只有一件事在磁盘场景下一切数据结构设计都要围绕「减少磁盘 I/O」展开。B 树把二叉树「压矮」成多路平衡树B 树又进一步把数据集中到叶子并用链表连接最终形成现代数据库索引的基石。理解这些内容不是为了背出一堆定义而是为了在面试和实际工作中能够回答两个根本问题为什么选它以及它好在哪里。把查找、插入、删除的每一步都亲手画一遍再配合 InnoDB 的真实索引设计去理解你会对 B 树和 B 树有更深的认识。 面试官：请你说说 B 树、B+ 树的原理及区别
1. 前言在面试后端开发、数据库内核、存储引擎相关岗位时「B 树和 B 树的原理及区别」几乎是必考题目。这个问题看似基础却能把候选人对数据结构、磁盘 I/O、操作系统页缓存、索引设计等知识的理解程度一次问透。很多人能背出「B 树所有数据都在叶子节点」「叶子节点之间有链表」这几句话但一旦面试官追问「为什么 MySQL 不用 B 树而用 B 树」「为什么非叶子节点不存数据」「一个节点到底能放多少个 key」「B 树的高度怎么估算」往往就答不完整。本文尝试用大约 2 万字的篇幅从最基础的二分查找、磁盘 I/O 特性讲起逐步推导出 B 树和 B 树的设计动机再详细讲解两者的定义、查找、插入、删除等核心算法最后通过对比表格和面试题清单帮助你建立一套完整的知识体系。阅读建议如果你只想快速回顾面试答案可以直接跳到第 11 节看对比表格和第 12 节看常见面试题如果想真正理解「为什么」建议从头开始重点关注前 5 节的推导过程。2. 一切从「查找」说起索引本质上是为了加速查找。在讨论 B 树和 B 树之前我们先回顾几种最基本的查找结构理解它们在数据量变大之后会遇到什么问题。2.1 顺序查找顺序查找是最朴素的做法从数组或链表的第一个元素开始逐个和目标值比较直到找到或者遍历结束。它的时间复杂度是 O(n)。当数据量只有几百条时顺序查找完全够用但当数据量达到千万、亿级别时线性扫描的时间成本会高到无法接受。顺序查找的最大优点是结构简单、对数据是否有序没有任何要求。但它的缺点同样明显每次查找平均要比较一半的元素失败查找更是要把全部元素都扫一遍。2.2 二分查找如果数据已经按关键字有序存储在一个可以随机访问的结构比如数组中我们就可以使用二分查找。二分查找每次取中间元素和目标值比较如果中间元素等于目标值查找结束如果中间元素大于目标值说明目标值只可能在左半区缩小范围继续查找如果中间元素小于目标值说明目标值只可能在右半区缩小范围继续查找。二分查找每次比较都能把问题规模缩小一半因此时间复杂度是 O(log₂n)。这个复杂度在数据量很大时优势非常明显对于 10 亿条数据二分查找最多只需要大约 30 次比较。public class BinarySearch { public static int search(int[] arr, int target) { int left 0; int right arr.length - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return -1; } }然而二分查找有一个致命的前提数据必须存放在内存中的连续数组里。当数据规模超过内存容量时数据只能落盘而磁盘的访问方式和内存完全不同。这就是引出 B 树的关键。3. 磁盘 I/O多路搜索树诞生的真正原因很多教材直接给出 B 树的定义却没有解释「为什么要多路」导致很多人只会背定义。其实 B 树的本质动机只有一个减少磁盘 I/O 次数。3.1 内存访问和磁盘访问的差距计算机存储体系是分层的CPU 寄存器最快其次是一级缓存、二级缓存、三级缓存然后是内存最后是磁盘。每一层之间的访问速度差距通常是一个数量级甚至更多。粗略来看访问一次内存的延迟大约是几十到一百纳秒访问一次机械硬盘的延迟大约是几毫秒其中主要是寻道时间和旋转延迟即便是 SSD随机读的延迟也在几十微秒量级仍然比内存慢 2 到 3 个数量级。也就是说一次磁盘 I/O 的时间代价足够执行几十万甚至上百万次内存操作。因此对外存数据结构来说优化的首要目标不是「少比较几次」而是「少读几次盘」。3.2 磁盘的「块」和操作系统的「页」磁盘并不是按字节读取的。机械硬盘的最小寻址单位是扇区通常是 512 字节或 4096 字节操作系统在和磁盘交互时则以「页」为单位典型大小是 4KB。即使你只想读 1 个字节操作系统也会把包含这个字节的整个页读进内存。这个特性对数据结构设计有重大影响如果我们能把经常一起访问的数据放在同一个页里一次 I/O 就能把它们全部读进来后续对它们的访问就不再需要额外的磁盘 I/O。B 树和 B 树正是利用了这个特性。它们把节点的大小设计成接近一个页的大小或者页大小的整数倍一次磁盘 I/O 就能读取一个完整节点节点内部的查找完全在内存中完成。3.3 从二叉树到多路树传统的二叉搜索树BST每个节点只保存一个关键字、最多只有两个孩子。对于存放在内存中的平衡二叉树如 AVL 树、红黑树查找时间复杂度是 O(log₂n)非常优秀。但是当数据大到必须放在磁盘上时问题就出现了。假设有 10 亿条记录用平衡二叉树存储树高大约是 log₂(10⁹) ≈ 30。这看起来不大但在磁盘背景下树高近似等于查找过程中需要进行的磁盘 I/O 次数。如果每次查找都要进行 30 次随机磁盘 I/O即使每次只有 5 毫秒合计也要 150 毫秒对高并发数据库来说是完全不可接受的。能不能让树「变矮」答案就是把二叉树变成多路搜索树每个节点不只保存一个关键字而是保存多个关键字拥有更多的孩子。假设每个节点能放 1000 个关键字、拥有 1001 个孩子那么 3 层树就能容纳大约 10 亿个关键字查找时最多只需要 3 次磁盘 I/O。这种「矮胖」的多路平衡搜索树就是 B 树的雏形。4. 为什么 AVL 树和红黑树不适合做磁盘索引理解了磁盘 I/O 特性之后就能很清楚地回答这个经典问题为什么数据库索引不用 AVL 树、红黑树这类二叉平衡树树高太高二叉树每个节点只有一个关键字节点数量等于关键字数量。上亿条数据意味着树高达到 20 到 30 层以上每层都可能触发一次磁盘 I/O。节点过小浪费页一个二叉树节点通常只有几十字节而操作系统一次 I/O 会读 4KB 甚至更大的页。也就是说为了读一个几十字节的节点却要付出读取整个页的代价其余数据都没用上。更糟的是二叉树的节点在内存中分散存放一个页里很难装下父子节点导致每次访问一个节点都可能是一次随机 I/O。无法高效利用局部性B 树把大量关键字聚合在一个节点里一次 I/O 读入一个节点后可以在内存中完成几十次、几百次比较大大摊薄了 I/O 成本。所以结论是AVL 树和红黑树本身是非常优秀的内存数据结构但它们的设计假设是「节点访问成本相同且便宜」而磁盘场景下节点访问成本极高因此必须使用能够把树压矮、把节点做大的多路搜索树也就是 B 树。5. B 树的定义与性质B 树B-tree是一种自平衡的多路搜索树。它由 Rudolf Bayer 和 Edward M. McCreight 在 1970 年左右提出。「B」的含义有多种说法常见的有 Balanced、Bayer、Boeing 等但学术界普遍认同它是一种平衡树这一点比字母本身更重要。5.1 严格的 B 树定义一棵 m 阶degreeB 树或者说一棵阶数为 m 的 B 树是满足以下性质的空树或非空树每个节点至多有 m 个孩子除根节点外每个非叶子节点至少有 ceil(m/2) 个孩子若根节点不是叶子节点则根节点至少有 2 个孩子一个有 k 个孩子的非叶子节点恰好包含 k-1 个关键字所有叶子节点都出现在同一层并且不携带信息或携带指向数据的指针节点内部的关键字按从小到大排序并且节点满足搜索树的性质对于关键字 key[i] 和它的左右孩子左子树中所有关键字都小于 key[i]右子树中所有关键字都大于 key[i]。需要注意的是不同教材对于「阶」的口径略有差别。有的教材用「m 阶」表示节点最多有 m 个孩子这种情况下节点最多有 m-1 个关键字有的地方直接说「节点最多有 m 个关键字」。本文统一采用经典定义m 阶 B 树的节点最多有 m 个孩子、最多 m-1 个关键字除根节点外每个节点至少能有 ceil(m/2) 个孩子、至少 ceil(m/2)-1 个关键字。5.2 一个直观例子下图用文字描述一棵 5 阶 B 树每个节点最多 5 个孩子、最多 4 个关键字除根外至少 3 个孩子、至少 2 个关键字[ 20 | 40 | 60 ] / | | \ [5|10] [25|30] [45|50] [70|80|90] / | \ / | \ / | \ / | | \ 叶子们全部在同一层这棵树有 3 层。根节点有 3 个关键字因此有 4 个孩子第二层每个节点都有 2 到 3 个关键字满足「除根外至少 2 个关键字」的约束所有叶子节点位于同一层保证了树的绝对平衡。5.3 B 树高度的估算B 树之所以能支撑海量数据关键在于它能被压得非常矮。下面推导 B 树高度与关键字数量的关系。设一棵 m 阶 B 树除根节点外每个节点至少有 ceil(m/2) 个孩子记为 tt ceil(m/2)常被称为最小度数 minimum degree。那么第 0 层根至少有 1 个节点、至少 1 个关键字第 1 层至少有 2 个节点至少 2(t-1) 个关键字第 2 层至少有 2t 个节点至少 2t(t-1) 个关键字第 h 层至少有 2t^(h-1) 个节点。因此高度为 h 的 B 树至少包含的关键字个数为n ≥ 1 (t-1) × (2 2t 2t² ... 2t^(h-2)) 1 2(t-1) × (t^(h-1) - 1) / (t - 1) 2t^(h-1) - 1由此可以得到高度上限h ≤ log_t((n1)/2)对于 5 阶 B 树t3。如果有 10 亿个关键字高度上限大约是 log₃(5×10⁸) ≈ 18 左右。如果换成常见的更大阶数例如每个节点能放 1000 个关键字此时 t≈501那么 10 亿条数据的高度大约只有 log₅₀₁(10⁹) ≈ 3也就是最多 3 到 4 次磁盘 I/O 就能完成一次查找。这就是 B 树「矮胖」结构带来的巨大价值。6. B 树的查找B 树的查找过程和二叉搜索树非常相似区别在于每个节点内有多个关键字需要先在当前节点内部找到合适的位置再决定进入哪个孩子节点。6.1 查找算法描述假设我们要在 B 树中查找关键字 k从根节点开始。在当前节点内部内存中查找 k因为节点内关键字有序可以直接使用二分查找或用线性扫描。如果在当前节点中找到了 k查找成功返回对应位置。如果没找到根据 k 落在哪两个相邻关键字之间确定应该进入哪个孩子节点然后继续递归查找。如果到达叶子节点仍然没找到说明 k 不存在查找失败。6.2 查找伪代码BTreeSearch(node, k): i 0 while i node.n and k node.keys[i]: i i 1 if i node.n and k node.keys[i]: return (node, i) // 在当前节点找到 if node.isLeaf: return null // 已是叶子未找到 return BTreeSearch(node.children[i], k)6.3 时间复杂度分析B 树的查找分为两个维度沿树向下走的层数即树高 h决定了磁盘 I/O 次数。对于大阶数 B 树h 通常只有 3 到 4。每个节点内部的比较次数节点内关键字有序使用二分查找的复杂度是 O(log₂m)其中 m 是节点可容纳的最大关键字数。如果节点大小固定为 4KBm 通常为几百到上千内部的 log 运算代价很小。因此B 树查找整体非常高效磁盘 I/O 次数极少内存内比较次数也层层降低。7. B 树的插入与分裂B 树的插入比查找复杂因为它必须维护「所有叶子都在同一层」这个平衡性质。核心机制是节点满了就分裂并且分裂产生的新关键字向上提升到父节点。7.1 基本插入流程先执行一次查找定位到目标关键字应该插入的叶子节点。如果该叶子节点还有空闲位置关键字数小于 m-1直接按顺序插入即可。如果该叶子节点已经满了关键字数等于 m-1插入后会有 m 个关键字违反 B 树约束需要进行分裂。7.2 节点分裂split所谓分裂就是把一个满节点从中间拆成两个节点并把中间的关键字提升到父节点中。具体步骤如下假设当前节点有 m-1 个关键字、插入后临时为 m 个关键字找到中间位置通常是下标 ceil(m/2) 或从左数第 t 个关键字tceil(m/2)。把该中间关键字从原节点中取出准备提升到父节点。原节点左半部分middle 左边的关键字和孩子保留在原节点右半部分middle 右边的关键字和孩子放入一个新创建的节点把中间关键字插入父节点的适当位置并让父节点指向新分裂出的右节点。如果父节点也满了递归地继续分裂父节点如果一直分裂到根节点则创建一个新的根节点树的高度加 1。正是「根节点分裂」这一操作会让树整体长高且由于只有根节点分裂才会增加高度而分裂是从下往上传播的因此所有叶子节点的深度始终一致树的平衡性得以维护。7.3 一个插入分裂的例子考虑一棵 5 阶 B 树的某个叶子节点里面已经有 4 个关键字[ 10 | 20 | 30 | 40 ]现在向这个叶子节点插入关键字 25。由于节点内关键字必须保持有序插入后的临时状态为[ 10 | 20 | 25 | 30 | 40 ] // 插入后临时有 5 个关键字5 阶 B 树每个节点最多只能有 4 个关键字因此这个节点违反了约束必须分裂。取中间关键字第 3 个25 提升到父节点原节点拆成左右两个节点左节点[ 10 | 20 ] 右节点[ 30 | 40 ] 父节点新增关键字25并分别指向左、右两个子节点如果父节点原本还有空闲位置这次插入就结束了如果父节点也因为新增 25 而变满则继续对父节点重复上述分裂过程直到不再违反约束为止。若分裂一直传播到根节点根节点分裂后会创建一个新根树的高度加 1。这就是 B 树在插入过程中保持平衡的核心机理。8. B 树的删除删除操作比插入更复杂因为它不仅可能让节点变空还可能让节点关键字数低于下限 ceil(m/2)-1。总体策略是先想办法让目标关键字落到叶子节点再在叶子节点中删除如果删除后节点关键字过少就通过「借关键字」或「合并节点」来恢复 B 树约束。8.1 删除的基本情况设最小度数 t ceil(m/2)除根节点外每个节点至少应有 t-1 个关键字。删除关键字 k 时可以分成两种情况k 在叶子节点中直接删除即可。如果删除后该叶子节点仍有至少 t-1 个关键字删除结束否则进入「下溢」处理。k 在内部节点中找到 k 的前驱关键字左子树最右下的关键字或后继关键字右子树最左下的关键字替换 k然后在对应的叶子节点中删除该前驱或后继关键字。这样就把删除内部关键字的问题转化为删除叶子关键字的问题。8.2 借位与合并当某个节点删除后关键字数不足 t-1也就是发生「下溢」时需要依据兄弟节点的情况处理向左/右兄弟借关键字如果相邻兄弟节点关键字数大于 t-1就可以把父节点中的一个关键字「下沉」到当前节点同时把兄弟节点中的一个关键字以及对应孩子「上移」到父节点。本质上是把父节点关键字和兄弟节点关键字做一次旋转。与兄弟节点合并如果相邻兄弟节点都只有 t-1 个关键字无法再借就把当前节点、父节点中的一个关键字、兄弟节点合并成一个节点。合并会让父节点少一个关键字父节点可能继续下溢因此需要递归向上处理如果根节点最后被合并空了就把合并后的节点作为新的根树的高度减 1。借位不会改变树高合并可能减少父节点关键字数最坏情况下会一直传播到根并导致树变矮。这也保证了 B 树始终「自底向上」地维持平衡。8.3 一个删除的例子假设一棵 5 阶 B 树中某叶子节点为[ 10 | 20 | 30 ]在 5 阶 B 树中t3叶子节点至少应有 t-12 个关键字。若删除 10节点变为[ 20 | 30 ]仍满足下界删除直接完成。若原节点只有[ 10 | 20 ]删除 10 后只剩 1 个关键字发生下溢。此时若右兄弟是[ 40 | 50 | 60 ]可以从右兄弟借一个关键字。假设父节点分界关键字是 35借位后父节点分界关键字变为 40原右兄弟变为 [50|60]当前节点变为 [20|35]恢复合法状态。9. B 树的定义与性质B 树是 B 树在数据库索引场景下最常见的变体也是 MySQL InnoDB 等存储引擎默认使用的索引结构。它保留了 B 树「矮胖、多路、自平衡」的全部优点同时对数据存储和范围查询做了专门优化。9.1 严格的 B 树定义一棵 m 阶 B 树满足以下性质与 B 树相同每个内部节点至多有 m 个孩子除根外至少 ceil(m/2) 个孩子所有叶子节点在同一层。非叶子节点只保存索引关键字用于路由不保存真实数据记录。非叶子节点有 k 个孩子时恰好包含 k-1 个关键字。所有真实数据都保存在叶子节点中。叶子节点包含全部关键字以及指向对应数据记录的指针。叶子节点之间按关键字顺序用链表串连通常为双向链表以支持高效的范围查询和顺序扫描。内部节点的关键字是孩子节点中键值范围的「副本」或「上界值」。例如某个内部关键字值 v意味着左子树中所有键 ≤ v右子树中所有键 v不同实现有细微差别。9.2 B 树与 B 树的关键区别数据存放位置不同B 树的关键字和数据可以同时出现在内部节点B 树的数据只出现在叶子节点内部节点只是纯索引。查询稳定性不同B 树任何值的查找路径长度都相同都必须走到叶子节点查找时间更稳定。范围查询效率不同B 树叶子节点有链表定位起点后顺序扫描即可B 树范围查询需要反复在树中上下回溯。扇出更大因为内部节点不存数据单个索引项更小一个节点能容纳更多关键字树更矮I/O 次数更少。9.3 一个直观例子一棵 5 阶 B 树的简化结构如下[ 30 | 60 ] / | \ [10|20] [30|45] [60|80] | | | 叶子: [10]-[20] [30]-[45] [60]-[80] 叶子之间还有双向链表相连注意内部节点中的 30、60 只是索引边界真实关键字 10、20、30、45、60、80 全部出现在叶子节点里查找任何值都必须走到叶子层这也解释了为什么 B 树查找成本是稳定的。10. B 树的查找、插入与删除B 树的操作整体遵循 B 树的框架区别主要来自「数据都在叶子」「叶子之间有链表」「内部节点保存副本」这三点。10.1 查找从根节点开始在内部节点中找到正确的孩子并逐层向下最终一定会到达叶子节点。在叶子节点中用顺序或二分方式找到关键字若存在则返回指向数据记录的指针不存在则查找失败。由于内部节点只存索引、扇出更大树高通常比 B 树更低。对于千万、亿级数据B 树高度通常稳定在 3 到 4 层查找需要 3 到 4 次磁盘 I/O范围查找在定位到起点叶子后顺着链表向后读取即可非常高效。10.2 插入与分裂插入总是发生在叶子节点。找到目标叶子并插入后如果叶子节点关键字数超过上限就进行分裂把中间关键字提升到父节点同时保留叶子节点之间的链表关系。叶子分裂时被提升到父节点的关键字通常还会保留在右叶子中作为最小键副本这保证了查找时能正确路由。定位目标叶子节点并插入新关键字。若叶子节点未满插入结束若已满分裂成左右两个叶子中等关键字提升到父节点。维护叶子链表左叶子的 next 指向右叶子右叶子的 prev 指向左叶子。若父节点因插入新索引关键字而变满父节点同样需要分裂并继续向上传播根分裂时树高加 1。10.3 删除删除同样发生在叶子层。删除叶子中的关键字后叶子未下溢删除直接结束。父节点中的索引副本键可以保留不动即使该关键字在叶子中已不存在只要它仍能作为正确的分界值即可也有的实现会更新为新的最小键。叶子下溢优先向相邻叶子借关键字若兄弟也不足则与兄弟合并。合并后需要更新父节点索引并递归处理父节点下溢。总体上说B 树的删除与 B 树思路一致先转换到叶子删除再通过借位或合并自底向上修复平衡。11. B 树与 B 树对比这张对比表可以帮助你在面试或实际选型时快速回答「B 树和 B 树到底差在哪里」对比维度B 树B 树数据存放关键字和数据可同时存在于内部节点数据只存叶子节点内部节点仅存索引查找稳定性可能在某层提前命中路径长度不一致任何查找都要到叶子路径长度稳定范围查询需要在中序方式下反复回溯定位起点后沿叶子链表顺序扫描树高节点包含数据扇出相对较小树相对更高内部节点小、扇出大树更矮更新代价插入删除后局部调整即可额外维护叶子链表和索引副本实现更复杂空间利用内部节点也存数据空间利用率较高叶子存全部数据内部索引会额外占用空间典型用途适合键值访问、无强范围扫描场景数据库索引首选项如 MySQL InnoDB一句话总结B 树牺牲了一定的写入和维护复杂度换来了更矮的树高、更稳定的单点查询和更高效的范围扫描因此更适合数据库这类读写混合、范围查询频繁的持久化索引场景。12. 常见面试题清单最后把这些高频问题整理成一份自测清单。建议每题都能用自己的话解释清楚而不是只会背答案为什么数据库索引不用 AVL 树、红黑树而用 B 树或 B 树B 树的「阶」是什么意思m 阶 B 树节点最多有几个孩子、几个关键字B 树为什么所有叶子节点必须在同一层根节点分裂时树高怎么变化B 树插入后节点满了怎么办请描述分裂过程。B 树删除时节点关键字数低于下限怎么办借位和合并有什么区别B 树和 B 树的主要区别有哪些为什么 MySQL InnoDB 选择 B 树B 树中内部节点保存的关键字和数据有关系吗是否一定在叶子节点中重复出现B 树叶子节点之间的链表有什么作用对范围查询和排序有什么帮助如何估算一棵 B 树或 B 树的高度10 亿条数据大概需要多少层为什么 B 树非叶子节点不存数据可以提高扇出、降低树高什么是聚簇索引、二级索引它们和 B 树有什么关系B 树的插入、删除分别会触发哪些维护操作哪些情况会导致树变高或变矮13. 总结从二分查找到磁盘 I/O从 B 树到 B 树整个推导链条的核心只有一件事在磁盘场景下一切数据结构设计都要围绕「减少磁盘 I/O」展开。B 树把二叉树「压矮」成多路平衡树B 树又进一步把数据集中到叶子并用链表连接最终形成现代数据库索引的基石。理解这些内容不是为了背出一堆定义而是为了在面试和实际工作中能够回答两个根本问题为什么选它以及它好在哪里。把查找、插入、删除的每一步都亲手画一遍再配合 InnoDB 的真实索引设计去理解你会对 B 树和 B 树有更深的认识。