说到B树很多人的第一反应是啊数据库索引那个数据结构然后第二反应就是上课的时候没听懂课后自己看也没太看明白。我最早接触B树也是这样的状态概念背得滚瓜烂熟什么m阶叶子节点同层关键字有序但真让我画一棵树出来、或者手写一次插入分裂立刻就卡壳了。后来因为工作里要调MySQL的慢查询、要自己实现一个简易的LSM存储引擎才被迫把B树和B树从头到尾啃了一遍也踩了不少坑。这篇博文我就用图解加逐步推演的方式把B树的定义、查找、插入、删除全部过一遍重点放在每个操作到底在干什么、为什么要这么干上而不是停留在背结论的层面。无论你是准备面试、复习数据库原理还是真的要在代码里实现一个B树这篇文章都能给你一条足够清晰的上手路径。1. 磁盘IO才是B树的亲爹为什么数据库索引偏偏选中B树1.1 两种存储介质的巨大速度鸿沟要理解B树首先要跳出数据结构课本的视角站在计算机存储体系的角度看问题。内存RAM的访问延迟大概是几十纳秒级别而磁盘机械硬盘的随机访问延迟大概是几毫秒到十几毫秒固态硬盘SSD会好很多但也比内存慢几个数量级。更关键的在于操作系统读写磁盘是以块block为单位的数据库引擎读写磁盘往往以页page为单位比如InnoDB默认的页大小是16KB。也就是说哪怕你只想读一个字节底层也至少要整页读进内存。这就引出了一个核心矛盾如果我们用二叉树做索引树的节点通常只保存一个关键字那意味着查找一个数据可能要访问几十次甚至几十次磁盘页每一次都是漫长的IO等待。这个等待累计起来数据库基本就废了。1.2 二叉搜索树在磁盘场景下的致命伤二叉搜索树BST在内存里确实很优秀有序、查找快、实现简单。但把它搬到磁盘场景问题就暴露了。假设一棵高度为20的二叉搜索树存了100万个关键字查找时最坏要比较20次对应约20次磁盘IO。这个数据看起来还能接受那我们换个角度在数据库里几千万行数据是非常常见的量级树的高度自然就上去了。而且二叉树的每个节点只存一个关键字一个16KB的页能利用的空间非常有限指针之间的跳转极其频繁。更不要提如果二叉搜索树不平衡了退化成链表那查找就是灾难级的O(n)。红黑树呢红黑树确实是平衡二叉树的代表但它依然没有解决每个节点只存一个关键字这个根本问题。红黑树的高度在最坏情况下大概是2log₂(n)比普通BST稳定很多但依然是log₂级别的磁盘IO。磁盘IO是按次数算钱的每次IO的固定开销寻道、旋转、传输准备往往远大于数据传输本身的时间所以数据库真正想要的不是比较次数最少而是磁盘访问次数最少。在内存里比比较次数红黑树很优秀在磁盘上比较IO次数单节点的树结构天生吃亏。1.3 一个16KB页能装多少东西B树的高扇出优势B树高明的地方在于它颠覆了一个节点对应一个关键字的设计让一个节点可以存放多个关键字和多个子节点指针。InnoDB的一个B树节点就是16KB的一个页这个页里可以放下成百上千个索引关键字具体看字段类型。这样树的高度就变得非常低一个3层的B树如果每层每节点有几百个子指针轻松覆盖上千万甚至上亿条记录。而查找这些记录最多只需要3次磁盘IO根节点一次、中间层一次、叶子节点一次。同样的数据量换成红黑树高度可能是二三十层磁盘IO开销直接被拉爆。这就是数据库选择B树家族的根本原因为磁盘场景优化用空间换IO次数。2. B树的一纸契约阶数、节点和不变量读懂定义才能看懂图2.1 一棵m阶B树到底意味着什么网上讲B树的定义版本很多有的说每个节点最多有m个孩子有的说每个节点最多有m-1个关键字初学者特别容易搞混。我习惯这样记阶数m描述的是子节点指针的数量上限。一棵m阶B树每个节点最多有m个子节点相应地最多有m-1个关键字。因为关键字和子指针在排列上是交替出现的第一个关键字左边一个指针右边一个指针可以画成 [指针, 关键字, 指针, 关键字, ..., 指针] 的结构。一个节点如果有k个关键字那它一定有k1个子指针叶子节点除外叶子节点的子指针为null但逻辑上依然可以理解为它指向空子树。除了每个节点最多m个子节点这个上限B树还有一套完整的不变式每个节点内关键字按升序排列不重复所有叶子节点位于同一深度这保证了查询任何一条路径的长度一致不会出现有的数据很快查到、有的数据要绕很远的不均衡除根节点外每个非叶子节点至少有⌈m/2⌉个子节点等价于至少⌈m/2⌉-1个关键字如果根节点不是叶子节点它至少要有2个子节点。前三条是硬性守则只要违反了其中一条维护者就得通过插入分裂或删除合并来修树。2.2 围绕不变性质的四个常见误解我见过很多人在学B树时栽在几个概念细节上这里集中纠正一下。第一个误解是每个节点至少要有⌈m/2⌉-1个关键字——这句话只在非根节点上成立。根节点是个特殊角色一棵B树哪怕只有一个关键字只要它自己就是这棵树也完全合法。比如一棵空树插入一个关键字后根节点只有1个关键字这时当然不能套至少⌈m/2⌉-1的规则不然一棵只有1个关键字的3阶B树就违规了实际上它完全正常。第二个误解是叶子节点得存数据——这其实是B树的概念。在经典B树的定义里叶子节点同样存储关键字只是叶子没有子节点而已。真正的区别在于B树把数据全部集中在叶子层内部节点只存索引。很多文章不区分B树和B树把B树的特性安在B树头上导致理解错位。本文后续讲到B树时再展开对比。第三个误解是分裂就是把节点切成两半各放一半——实际分裂不是平均切而是挑中间的关键字上提到父节点左右两半留在两个新节点里。所以每次分裂会让树长高一格但树高只会在从根到叶的某一条路径上增加。第四个误解是删除就是删掉那个关键字再整理一下顺序就行——如果节点删完还满足最小关键字数那确实很简单但如果删完后关键字数跌破下限就需要借位或者合并。删除操作是三个操作里最容易写错的地方后面我会专门用一整章来推演。2.3 如何用节点上下限快速判断一棵树是不是B树我在面试别人的时候喜欢给一张画好的树让候选人判断它是不是一棵合法的B树。这个方法其实很机械就三步确定阶数m确认每个节点的关键字数都不超过m-1跳过根节点确认其他所有非叶子节点的关键字数都不少于⌈m/2⌉-1从上往下检查所有叶子节点是否在同一深度且每个节点内关键字严格递增。只要这三条全过这就是一棵合法的B树。这个方法对自查也很有用你手写插入后拿它检查一遍基本能确认节点的上下限有没有违规。3. 图解B树查找从根到叶的一次分层缩小过程3.1 节点内部的二分查找逻辑B树的查找逻辑和二叉搜索树非常像区别只在于二叉搜索树每个节点只有一个关键字一次比较之后要么相等、要么走向左子树、要么走向右子树而B树每个节点有多个关键字一次比较之后如果没找到相等值就要根据目标值落在哪两个相邻关键字之间选择对应的那棵子树继续向下找。由于节点内的关键字是升序排列的查找时可以在节点内做二分查找这会把节点内比较次数从O(k)降到O(log₂k)虽然IO层面的复杂度没变但CPU比较的开销降了不少。我自己实现时习惯先做二分找到第一个比目标值大的位置然后根据这个位置决定走哪个子指针逻辑很清晰也能和后面的插入删除共用同一套定位函数。3.2 一个查找全过程示例我手绘一棵4阶B树即每个节点最多3个关键字、4个子节点存放的关键字是根节点: [ 30, 60 ] 中间节点1: [ 10, 20 ] 中间节点2: [ 40, 50 ] 中间节点3: [ 70, 80, 90 ] 叶子节点: [ 5 ], [ 15, 18 ], [ 25 ], [ 35 ], [ 45, 48 ], [ 55 ], ...现在要查找关键字48。查找流程从根节点开始根节点存储 [30, 60]48 30 且 48 60所以进入30和60之间的子树即中间节点2中间节点2存储 [40, 50]对40和50做比较48 40 且 48 50进入40和50之间的子树在叶子节点里找到 [45, 48]二分命中48查找成功。整个过程只下探了3层对应3次节点访问如果按磁盘页来看也就是最多3次IO可以把根节点常驻内存实际IO更少。这个例子非常直观地说明了B树为什么高效它不追求比较次数最少而是把树压扁让每次IO都能成片地把关键字抓进来然后快速缩小范围。3.3 为什么查找复杂度常被写成O(log n)严谨地说B树查找的IO次数是O(logₘ n)这里的m是阶数。因为每一层能把搜索范围缩小到1/m的规模树的高度就是logₘ n。m值越大树越扁IO次数越少。m也不是越大越好一个节点放的关键字越多单个节点占的空间越大在内存中做二分查找的CPU成本越高而且和页大小、磁盘IO方式都有匹配问题。InnoDB的页大小16KB、使用B树时每个节点能存几百个索引关键字这个设计是经过工程权衡的。面试时如果被问到为什么用B树不用二叉树回答因为B树是矮胖的IO次数少就是关键得分点。4. 图解B树插入与分裂向上生长的唯一方式4.1 插入流程的分步描述B树插入的核心原则是所有的插入都发生在叶子节点。流程分几步走。第一步从根节点开始查找找到目标关键字应该插入的那个叶子节点位置。这里的查找路径和普通查找一模一样只是因为目标不存在最后会落在一个叶子节点上。第二步把关键字按升序插入到这个叶子节点的关键字数组里。第三步检查这个节点的关键字数量是否超过上限m-1。如果没有超过插入结束如果超过了就触发分裂。第四步分裂把当前节点从中间位置拆开中间的那个关键字上移到父节点左边的关键字留在原节点或左兄弟右边的关键字进到新的右兄弟节点。然后父节点的关键字数量也增加了需要继续向上检查父节点是否超限如果超限就继续分裂直到根节点。如果根节点也分裂了树就会增高一层。这个流程里有一个细节中间关键字怎么选我记得有些教材规定选中间靠左或中间靠右不同实现有微小差异。但从正确性来说只要保证拆出来的左右两部分都满足节点最小关键字数要求即可。对于偶数个关键字的情况选中间偏左或中间偏右都能满足条件无需纠结。4.2 分裂机制中间关键字上溢分裂是整个插入里最核心也最容易画错的环节。假设一棵3阶B树每个节点最多2个关键字的某个叶子节点已经存了 [7, 11, 14]这是插入第三个关键字后超出上限的状态正常合法状态下不可能出现这里只是演示超限时刻这时再插入一个关键字比如插入10后变成 [7, 10, 11, 14]关键字数达到4个超过m-12的限制。此时分裂做法是找到中间位置如果关键字个数为4中间位置取第2个或第3个都行演示中取第3个关键字11把11上提到父节点原来的节点保留 [7, 10]新创建一个节点存 [14]新节点作为原节点在父节点中的兄弟父节点的子指针数量随之加1。关键字的移动会引发子指针的联动调整如果当前分裂的是内部节点而不是叶子节点那么子指针也要跟着一分为二左半部分的子指针留在原节点右半部分的子指针移到新节点。我在自己实现时最常出问题的就是在分裂内部节点时忘记搬运右侧子指针导致树的结构直接断掉。所以每次分裂后我都习惯性打印一下全树结构确认每个节点的子指针数量和关键字数量符合k个关键字对应k1个子指针的规则。4.3 一个完整的插入序列演示从空树开始构造一棵3阶B树直接看定义容易晕我建议你拿一张纸跟着下面的序列一步步画。我们构造一棵3阶B树也就是每个节点最多2个关键字、最多3个子节点。非根节点的最少关键字数是⌈3/2⌉-11也就是说每个非根节点至少要有1个关键字。初始状态树为空。依次插入 1、2、3。插入1根节点为 [1]。插入2根节点变为 [1, 2]。插入3根节点先变成 [1, 2, 3]超过2个关键字的上限触发分裂。取中间关键字2上提为新的根左右两个节点分别存 [1] 和 [3]。此时树的高度变成2[ 2 ] / \ [ 1 ] [ 3 ]继续插入4、5。插入4查找路径落在右子树 [3] 上插入后 [3, 4]未超上限结束。插入5落在 [3, 4] 上插入后 [3, 4, 5]超上限。分裂中间关键字4上提给父节点 [2]父节点变成 [2, 4]左节点 [3]右节点 [5]。树变为[ 2, 4 ] / | \ [ 1 ] [ 3 ] [ 5 ]继续插入6、7、8、9。插入6落在 [5] 上插入后 [5, 6]未超限。插入7落在 [5, 6] 上插入后 [5, 6, 7]分裂6上提给父节点 [2, 4]父节点变成 [2, 4, 6]同时新增右节点 [7]。这时候父节点也超限了继续分裂中间关键字4上提为新根左节点 [2]右节点 [6]。树变为[ 4 ] / \ [ 2 ] [ 6 ] / \ / \ [ 1 ] [ 3 ] [ 5 ] [ 7 ]插入8落在 [7] 上插入后 [7, 8]。插入9落在 [7, 8] 上插入后 [7, 8, 9]分裂8上提给父节点 [6]父节点变成 [6, 8]新增右节点 [9]。最终树为[ 4 ] / \ [ 2 ] [ 6, 8 ] / \ / | \ [ 1 ] [ 3 ] [ 5 ][ 7 ][ 9 ]整个过程看下来你会发现B树长高只有一个原因根节点分裂。而分裂永远是从叶子节点开始向上逐层扩散的。这种向上生长的方式让B树始终保持所有叶子在同一深度非常优雅。实话说第一次手工画出这个完整过程时我才真正理解为什么B树的树高是稳定可预期的。5. B树的删除最考验手感借位、合并与下溢处理5.1 删除的三种情形删除操作比插入复杂主要原因是插入只涉及分裂一种修复手段而删除要根据实际上下文选择不同的修复方式。删除前先做查找定位目标关键字所在节点。第一种情形目标在叶子节点删掉之后节点关键字数仍然不低于最小值直接删除就结束。第二种情形目标在叶子节点删掉之后节点关键字数低于最小值。这时要看相邻兄弟节点的家底如果左边或右边的兄弟节点有多余的关键字就向兄弟借一个。借位的具体操作是从父节点取一个关键字垫下来同时把兄弟节点的某个关键字上提到父节点。这种操作在B树里叫旋转或借用本质上是把父节点当作中间缓冲既维持了父子之间的顺序关系也避免树的结构变动。如果两个兄弟都没有多余关键字那就执行合并把当前节点和某个兄弟节点合并同时父节点中夹在它们之间的那个关键字也跟着降下来一起并进合并后的节点。第三种情形目标在内部节点不能直接删。这时候的做法是从目标关键字左子树里找到前驱即该子树的最大关键字或者从右子树里找到后继即该子树的最小关键字用前驱或后继的值覆盖目标关键字然后转而去叶子节点删除那个前驱或后继。这样做的原因很直接内部节点承载着分叉的职责随便删一个关键字会导致左右子树的索引关系失衡而用叶子节点上的极端值来替换既能维持节点的有序性又能把难题抛给相对好处理的叶子节点删除。删除完还要继续沿路径向上检查每个祖先节点是否下溢关键字数低于下限如果父节点因为删除了某个垫下去的关键字而自身下溢就要对父节点执行借位或合并。这个递归推导和插入分裂的向上扩散非常对称。5.2 内部节点删除为什么要找前驱/后继这里值得多说一句。假设内部节点存了 [10, 20]它有三个子树左子树里的关键字都小于10中间子树里的关键字都在10和20之间右子树里的关键字都大于20。如果要删掉20直接把20踢掉那右子树就失去了分界标准右子树中的所有关键字都大于20现在父节点里没有20了但右子树仍然挂在原来的位置逻辑上就说不通。如果用右子树中的最小值比如21替换20那么右子树剩下所有值都大于21中间子树的所有值都在10和21之间整体仍然满足B树的有序性。这个用相邻极值替换的处理是内部节点删除的标准解法。实际编码时前驱和后继选哪个都行只要保持一致性。5.3 借位与合并的完整示例沿用上面构造的树[ 4 ] / \ [ 2 ] [ 6, 8 ] / \ / | \ [ 1 ] [ 3 ] [ 5 ][ 7 ][ 9 ]这是一棵3阶B树每个非根节点最少1个关键字。我们尝试删除1看会发生什么。删除1后节点 [1] 变成空节点下溢了。它的右兄弟是 [3][3] 有1个关键字而3阶B树非根节点的最大关键字数是2说明 [3] 还有富余准确说一个节点最多2个关键字[3] 只有1个关键字但1 最小值1所以[3]并没有富余到可以借出去。仔细观察[3] 这个节点里面只有1个关键字借走的话自己就空了所以不能借。此时只能合并。合并操作把当前空节点 [ ] 和右兄弟 [3] 合并同时父节点中夹在它们之间的关键字2降下来一起并入。于是新节点存 [2, 3]父节点 [4] 只剩一个关键字 [4]。检查父节点这是根节点关键字数1合法。合并后的树[ 4 ] / \ [ 2, 3 ] [ 6, 8 ] / \ / | \ null null [5][7][9]注意[2,3] 这个节点本身内部包含了2和3它作为左子树挂根节点4下没问题。原来 [1] 节点和 [3] 节点没了合并成了一个 [2,3] 节点。这时候 [2,3] 节点的子节点数 关键字数 1 3个虽然子树都是null但从内部节点角度看是合法的。这样整棵树依然满足所有叶子同一深度、每个非根节点至少1个关键字的规则。再演示一次借位。假设初始树是[ 4 ] / \ [ 1, 2 ] [ 6, 8 ] / | \ / | \ ... ... [5][7][9]现在删除6节点 [6,8] 如果直接删6会变成 [8]没有下溢。那刻意构造一个下溢节点 [8] 只有1个关键字如果强删一个就空了。但我们如何进入这种状态更常见的场景是从一个只有1个关键字的叶子节点删除。比如树[ 4 ] / \ [ 2, 3 ] [ 8 ] / \ / \ [1] [2.5] [5][9]删除5节点 [5] 空了左兄弟是 [2.5] 节点吗不对节点 [5] 的兄弟应该是 [9]也不对要看树的结构。上面的树里[8] 节点有两个子节点 [5] 和 [9]删除5后 [5] 空它的右兄弟是 [9]。检查 [9] 节点里面1个关键字不能借。但根据3阶B树规则节点 [9] 是叶子它的父节点 [8] 允许最多2个关键字。此时要合并从父节点 [8] 取关键字8降下来和空节点 [ ] 与右兄弟 [9] 合并成 [8,9]。父节点 [8] 变成空下溢了。然后父节点现在是 [4]的左子树 [2,3] 有2个关键字右子树空出问题此时可以向左兄弟借位左兄弟 [2,3] 的最右关键字3上提到父节点 [4]父节点的原关键字4降下来。最终树变成[ 3 ] / \ [ 2 ] [ 4, 8, 9 ]?等一下这里不能随便写。借位操作要保证父节点 [3] 关键字的左子树关键字都小于3右子树的关键字都大于3。原来的右子树是 [8,9] 吗合并后节点 [8,9] 的元素都大于3合法。原来的左子树 [2] 的关键字都小于3合法。所以最终树为[ 3 ] / \ [ 2 ] [ 8, 9 ] / \ / | \ [1][2.5] null null null我承认这个例子里的树形结够紧凑节点也够小实际上是在手推时临时构造的用来展示借位和合并交替发生的完整链路。真正在纸上画的时候你会发现删除操作最磨人的地方不在于单步逻辑而在于删完之后连锁反应可能要一路延伸到根节点让原本看好的结构变形。这也是为什么我很推荐用代码去跑删除逻辑手工画容易漏掉边缘条件程序却可以反复验证。6. 从B树到B树工程世界的选择与我的建议6.1 B树与B树的关键差异聊到这里你可能会问既然B树本身已经足够优秀为什么数据库源码里基本都是B树而不是B树两者的核心区别在于三点。第一B树的内部节点不存数据只存索引关键字和子指针数据全部存放在叶子节点。这意味着在同样大小的一页内存里B树的内部节点能存下的关键字数远多于B树节点树的扇出更大、高度更低。对于动辄上亿行的表这种更矮的树在IO次数上的优势是压倒性的。第二B树的叶子节点之间用链表串起来形成了一个有序链表范围查询从左端开始往后遍历即可不需要反复从根节点下探。而B树的叶子节点之间没有这种链接你要查询一个区间就得不停地走内部节点成本高得多。做数据库的同学应该深有体会范围查询、排序查询、分页查询是业务里的高频操作这个特性几乎是数据库的刚需。第三B树的任何一次查询路径都是根到叶查询每一行数据的IO次数完全一致延迟稳定而B树的关键字可能出现在内部节点命中内部节点和命中叶子节点的路径深度不同。稳定性对于数据库调优很重要毕竟你不希望某次查询突然慢一个数量级。6.2 数据库和文件系统里的真实变体最常见的自然是InnoDB的B树。普通二级索引的叶子节点存储索引字段值和主键值聚簇索引的叶子节点直接存储完整行记录。这意味着你在MySQL里建一张表、查一条数据背后基本都是B树的查找与遍历。InnoDB一个数据页16KBPage Directory里还做了类似二分查找的优化目的都是让单次定位尽可能快。文件系统里也有B树家族的影子比如ext4的Htree索引就是基于B树改造的变体用来加速目录项的查找。日志结构合并树LSM-Tree则是另一种存储思路它不维护在线有序树而是用内存缓冲加多层级合并的方式批量写入适合写多读少的场景。你会发现凡是需要在磁盘上做有序数据管理的地方B树家族几乎是绕不开的基础设施。6.3 给自己一个能跑起来的模拟实现建议如果你真心想弄懂B树我强烈建议自己动手写一个最小实现。不用上生产环境不用做复杂的内存管理就用一门你熟悉的语言定义一个节点结构体实现查找、插入、删除并加上一个打印整棵树的调试函数。我自己的经验有两个特别大的收益。第一只有当你亲手实现插入分裂时才会理解节点内关键字移动和子指针搬运之间的联动关系。调试器里盯着错乱的结构看十分钟胜过背十遍五条性质。第二当你把删除的各种分支整理成代码时才会发现网上有些教程讲的删除分支并不完整实际用例会自动暴露出合并之后连锁借位的情况。我写删除逻辑时反复对照教材图例才把所有case补齐那种终于通了的感觉非常值。具体实现时建议按这个顺序来先写一个Search函数返回目标关键字所在节点和位置再写InsertByName流程注意插入前先处理满节点可以自顶向下地预分裂也可以自底向上地后分裂前者代码更规整最后写Delete流程先处理内部节点的替换再处理叶子节点的下溢修复每一步都要打印整棵树肉眼确认结构合法。代码写的过程中你会遇到一个经典惊喜预分裂和回溯分裂这两种策略写出来的代码长度差异很大。大多数教材喜欢讲自底向上的递推分裂但工程实现里反而更常用自顶向下的预分裂因为每个节点只要保证到了就必然是安全的就不会出现回溯。理解了两种策略的差异你对B树的理解差不多就超越八成的背诵型选手了。回到开头那个问题B树到底难不难如果只是背定义那确实枯燥但如果你愿意动手画几棵小树、插几个节点、删几个节点或者干脆写几行代码你会很快建立直觉。所谓图解B树最值钱的不是记住那张图长什么样而是看懂图里每个结构变化背后的动机为了好少IO、为了有序、为了保证平衡。理解到这一层看数据库索引、看文件系统目录结构、看各种存储引擎的设计思路都会顺畅很多。