【数据结构（邓俊辉）学习笔记】高级搜索树02——B树

文章目录

• 1. 大数据
• • 1.1 640 KB
  • 1.2 越来越大的数据
  • 1.3 越来越小的内存
  • 1.4 一秒与一天
  • 1.5 分级I/O
  • 1.6 1B = 1KB
• 2. 结构
• • 2.1 观察体验
  • 2.2 多路平衡
  • 2.3 还是I/O
  • 2.4 深度统一
  • 2.5 阶次含义
  • 2.6 紧凑表示
  • 2.7 BTNode
  • 2.8 BTree
• 3. 查找
• • 3.1 算法过程
  • 3.2 操作实例
  • 3.3 算法实现
  • 3.4 主次成本
  • 3.5 最大高度
  • 3.6 最小高度
• 4. 插入
• • 4.1 算法框架
  • 4.2 分裂
  • 4.3 再分裂
  • 4.4 分裂到根
  • 4.5 实例演示
  • 4.6 实现
• 5. 删除
• • 5.1 算法框架
  • 5.2 旋转
  • 5.3 合并
  • 5.4 实例演示
  • 5.5 道法自然

1. 大数据

1.1 640 KB

接下来我们要学习一种非常有趣同时也是非常有用的数据结构，也就是B树。

从严格意义上讲，B树并不是二分查找树。我们很快就会看到，在物理上，B树的每一个节点都可能包含多个分支。然而也正如我们很快就会看到的，从逻辑上讲，它依然等效于我们此前所介绍的二分查找树，因此我们依然将它归入高级搜索树之类。

那么首先一个自然的问题就是，既然B树也完全等效于我们此前所介绍过的BST，那我们还有什么必要要引入并介绍它呢？也就是说，设计和实现这种搜索树的动机何在呢？我将会看到，B树的最初也是最主要的功能在于弥合不同存储级别之间在访问速度上的巨大差异，也就是现实高效的IO。

不妨让我们穿越到30多年前，Bill Gates的一句话曾经被很多人当作笑柄，因为他那时曾经断言，640KB，也就是dos的基本存储容量，已经足以满足任何实际应用的需要了。尽管这句话不免显得有些武断和短视，但我却坚信，你在学习完B树以后，一定会认为这句话实际上是千真万确的真理。

1.2 越来越大的数据

实际上，我们不愿意承认，但又不得不接受的一个基本事实是，从某种意义上讲，我们在计算过程中所能够使用和借助的内存是在日益的变小，而不是如我们直觉那样，变得越来越大。这听起来似乎是个悖论，因为对我们此前所介绍的典型计算模型来说，存储器的大小本身就不是问题，难道不是这样吗？

就RAM模型而言，所谓的存储器，无非就是一组寄存器，而且它的数量是无限的。而图灵机的存储器呢？也就是纸带，你应该记得，无论是纸带的长度，还是纸带上单元格的数目，都是无限的。然而无论是RAM机还是图灵机，在这一点上都做了过于理想的假设。

而在真实的世界中，存储器的容量必然是有限的。而且相对于实际应用的需求，会显得非常非常的有限。

事实情况是，在我们的计算机系统中，存储容量的增长速度要远远小于应用问题规模的增长速度。

为此我们不妨来看这样一组统计数字，按照我们通常对存储容量的规模分级，从 千—Kilobyte 到 兆 —Megabyte 到G—Gigabyte 和 T—Terabyte 以及 P—Petabyte 诸如此类。
  ~  
而我们人类所拥有的数字化信息的总量，在过去的半个多世纪中，增长速度是惊人的，比如截至2010年总量以及达到Zettabyte，也就是1后面要接21个0。我们知道中国的人口大致是十多亿，也就是10的9次方左右。因此，分摊下去，每个人可能都需要一个TB规模的硬盘。

请注意，这里我们说的还只是硬盘，而如果考虑内存，这方面的压力就更大了，我们不妨来进一步看些数字。

1.3 越来越小的内存

我们来对不同年代典型的数据库规模以及当时内存的容量规模做一对比，在上世界80年代，一个典型的数据库大致只有10M，当时的电脑典型的内存容量大致是1M，二者之比大致是10倍的压力。而在经过短短20年，我们进入到新世纪之后，随着技术的发展，典型的内存容量已经从M的量级跃升到G的量级，提高了1000倍。然而在另一个方面，实际应用中的数据规模却跃升到了TB量级，提升了大致10的5次方至6次方。

审视当今的实际应用，我们会发现，典型的数据集已经大多以TB作为度量单位了，这方面的例子举不胜举，无论是生物分子学、医学、物理学还是核能以及气象。因此即使从保守的角度来估计，数据库规模的增长之于内存容量的压力，也提高了至少100倍以上。

总而言之，尽管随着技术的发展，内存的绝对容量的确是在增加，但是相对于实际应用的需求而言，内存的容量实际上是在越来越小。

那么一个很自然的问题就是，为什么我们不把内存做得更大一些呢？实际上不难理解，这个美好的愿望是很难兑现的。这背后的原因在于，我们不得不在存储器的容量与它的访问速度之间，做一取舍折中。因为很自然的，存储器的容量越大，它的速度也就会更慢 。 反过来，为了使得存储器的访问速度更快，我们就不得不在容量上做些必要的牺牲。

1.4 一秒与一天

当然，面对存储器在速度和容量之间的内在矛盾，我们并非只能无所作为，其中采用高速缓存就是一种被证明行之有效并且普遍采用的方法和技巧。为此我们需要对不同层次存储器的性能做进一步的了解。

这包括两个方面。首先容量和类型不同的存储器在访问速度上的差异是极其悬殊的。

就以我们最常见的磁盘以及内存这两级存储为例，他们在访问速度上的差异究竟有多大呢？
   ~~   
其实我们只要找到相关产品的性能指标说明就不难看出这种差异，就传统的旋转式磁盘而言，它的访问速度大致是毫秒量级。而典型的内存呢？大致是纳秒量级。不要小看了m和n之间的差异，以一秒为基准，前者是10的-3次方，而后者呢是10的-9次方，因此，二者的差异大致是在10的5至6次方，是的，即使保守估计，也是5个数量级。

如果你还记得介绍过的封底分析，你应该意识到这种差别是一秒之于一天，没错，一秒之于一天。

也就是说，如果将内存的一次访问比作是一秒，那么相应的一次外存操作则是一天。
  ~  
再打个形象的比喻，假设一次内存访问就相当于从讲台上拿起一支粉笔，这可以在一秒钟之内瞬时完成。那么对应的外存操作呢？就相当于要去买一张火车票，然后赶到火车站，乘上火车，经过一天的路程到达比如说广州，然后在当地再乘同样的火车，连夜返回目的地。

1.5 分级I/O

无独有偶，所谓天上方数日，人间已千年，反应的呢？也是高达5至6个数量级的差异。因此我们在设计与实现算法的时候，为了避免一次外存访问，我们宁可去访问内存十次、百次、甚至千次万次也在所不惜。

这也是为什么通常的存储系统都是按层次分级组织的。

比如一个典型的存储系统可能包括CPU，当然是其中的寄存器了，以及内存RAM和DISK磁盘，DISK ARRAY磁盘阵列以及等等等。随着层次的深入，存储器的容量越来越大，但是反过来访问的速度也越来越低。

这样一种分级的结构，之所以能够高效的运转，在于其中采用了一种策略，也就是将我们最常用的数据尽可能放在更高的层次，因为尽管它的存储容量有限，它的速度能够最高。而不常用的数据呢？会自适应的通过兑换，转移到更大但是速度更慢的级别中去。

在这个系统中，相对于任何一个存储级别，如果希望向更低的存储级别写入，或者反过来，从更低的存储级别读入数据，我们都称之为输出和输入，简称IO。对于更上层的存储级别而言，对于更底层的存储级别的访问，都可以称作是外存访问。当然鉴于上层存储级别与下层存储级别在访问速度上的天壤之别，我们应该经可能减少它们之间的IO。以刚才的粉笔为例，除非本地的所有粉笔都已经消耗殆尽，否则我们是绝对不会轻易的外出专门采购。

1.6 1B = 1KB

关于存储器特性的第二个事实是个好消息，这个事实指出，如果我们希望从磁盘之类的外存中去读取一个字节，其时间成本与读入一千个字节几乎是一样的。

刚才的例子依然可以来说明这样的一个特性，也就是说，如果我们的确需要乘火车去广州采购粉笔，那么采购一支与采购一千支，其时间成本几乎是一样的。

典型的存储系统的确大多是采用批量式的方式来支持读或者写操作的。具体来说，无论我们是需要从内存向外存输出数据，还是需要从外存向内存读入数据，涉及的数据都是以页面为单位进行核算和组织的。

比如，在C语言标准库的输入输出库中，你应该能发现这样一段代码

其中servbuf接口就允许你来设置页面缓冲区的大小，以及缓冲的工作模式等等。

因此，在涉及频繁而大量数据访问的算法中，我们就需要充分利用这样一个特性，也就说我们要逐渐习惯批量式的访问，要么就一次性读写若干个KB，要么就一个字节也不访问。

这就犹如我们要集中的去一次广州，采购一大批粉笔，要么就一支粉笔也不采购。

就边际的时间成本来说，这样的一种组织和访问方式，才可能达到尽可能的优化。那么我们的主角B-Tree在期间又能起到什么作用呢？

2. 结构

2.1 观察体验

好的，现在就让我们来揭开B树神秘的面纱，看看它的内部究竟是怎样一番摸样。

这就是一棵典型的B树。

与此前的二叉查找树一样，B树也是用来存放一组具有关键码的词条的数据结构，但是它的特点也非常鲜明。

1. 我们可以看到首先这里每一个节点未必只有两个分叉，实际上，可以拥有更多的分叉。
2. 其次呢？所有底层节点的深度都是完全一致的，从这个意义上讲，它不失为一种理想平衡的搜索树。
3. 最后，也是最重要的一个整体特征，我们注意到相对于常规的二叉查找树，B树会显得更宽，更矮。

那么为什么B树会长成这样一幅模样呢？背后又有什么原因呢？现在回答这个问题还略早，不妨先将这个问题记下来，看看在这一节学习完成之后，是否能够独立的给出背后的答案。

当然B树也是可以动态变化的，比如我们可以在其中插入一个新的词条100。

请注意一个新的词条出现了，而且在插入词条之后，B树有可能会相应的自我调整。比如

同样，逆向的操作也是可行的，比如可以将刚插入的这个词条100删除掉，我们首先查找到这个词条

并且将其摘除

为了删除某个词条，B树同样有可能进行拓扑结构的调整。比如继续删除其中的这个111，同样我们需要通过查找对它进行定位

接下来摘除掉这个词条，并相应的进行拓扑结构的调整，直至重新恢复为一棵B树。

那么在B树的这样一个静态结构，以及刚才我们看到的动态调整的背后，究竟是什么样的一些规则呢？又为什么会采用那样一套规则呢？

2.2 多路平衡

正如我们所看到的，B树的设计者将其定义为一种平衡的多路搜索树。这样一种多路的收索树，与我们此前所熟知的二路搜索树在本质上讲，其实是等价的。

如果我们将多路搜索树中的每一个节点称作超级节点的话，那么每一个超级节点都可以认为是由若干个二路节点讲过适当的合并以后得到的。

来看上上面实例，如果忽略掉这些方框，不难看出这其实就是一棵二叉搜索树的局部。现在我们两层两层的来考察其中这些节点。
  ~  
具体来说，每一个节点以及它的左和右孩子，如果我们将每一组这样的父子三个节点合并成一个超级节点，那么整棵树就可以等价变化成上图下面的形式。具体的，原先的父节点居中，原先的孩子则经过提升与之并行的列于左右，这种节点的确可以称作是超级节点，因为其中不再只含有一个关键码，而是多个，就这个例子而言，每一个超级节点都含有3个关键码，同时相应的也就拥有4个分支，可以看到，如此每两代两代的合并之后，每个节点都将拥有3个关键码以及4个分支。

推而广之，也有可能每3代的合并起来，从而使得每个超级节点里含有7个关键码以及8路分支。一般的，如果每d代都进行一次合并，那么每个超级节点都将拥有2的d次方路分支，以及相应再减少1个单位的关键码。

同样的，这里依然存在一个问题，既然我们已经看到，这种多路的搜索树与以前的二路搜索树并没有本质的区别，那么为什么还要引入B树呢？这依然是我们需要回答的一个问题。

2.3 还是I/O

这背后的原因恰恰在于，在我们通常都是按多个层次来分组组织的存储系统中，如果使用B树可以针对我们此前所说的外部操作，大大降低IO访问的次数，从而极大的提高计算效率。

那么难道此前已熟悉的AVL树在这方面还不够吗？不妨具体估算，考察某个由10的9次方，1G个记录的数据集。

如果将它们组织为一棵AVL树，高度大致为30层。也就是说，在最坏情况下，单次查找需要深入30层，而每一次我们都需要执行一次IO操作。

那么 B树又能如何呢？

我们刚刚看到，B树中的超级节点同时包含多个而不是单个关键码，因此在B树中每下降一层，都可以超级节点为单位，读入一组而不是单个关键码，从而将外存批量访问的特点，转化为实在的优点。
  ~  
如果将关键码比作粉笔，那么每一个超级节点都相当于那列火车的一节车皮，其中既可以装载一根粉笔，也可以装载一大堆。既然如此，采用B树的策略将它们成批的而不是单个的读取，也是再自然不过的。

那么这样一节车皮具体的应该设计为多大呢？这取决于磁盘等外存本身所设定的数据缓存页面的大小。

通常的情况下，都是若干个KB，如果每个关键码通常取做4个字节的话，那么很自然的就应该将每个节点的规模设置为200至300之间。
  ~  
比如若将超级节点的规模取做256，也就是2的8次方，那么同样存放1G个记录的B树，高度不会超过4，这就意味着即便在最坏的情况下，单次查找所需要进行的IO操作也同样不超过4次，是的，4次对30次，我们说这是很大的一个提高。

讲到这里你或许会有一个疑问，难道4和30不都是可以视作常数吗？

是的，就渐进的意义而言，的却如此。但是当这个常数的每一个单位都相当于10的5至6次方时，我们就不得不斤斤计较了。这就犹如索然1秒和1天乃至1年，都可以视作是常数，但是对于有限的人生来说，却有本质的区别。比如绝大多数人都会接受花费4年的时间就读大学获得一个学士学位，但是如果将这个期限换成30年，我想应该不会有很多人继续做此选择了。

2.4 深度统一

以下我们就给出 B树的严格定义

任何B树都有一个固定的指标，也就是它的阶次。一般的，所谓m阶B树，就是m路的平衡搜索树。

正如我们在此前的实例中所看到的， 作为B树的最重要的特征，所有叶节点的深度都是一样的，同时相应的所有外部节点的深度，也是一样的。我们知道所谓的叶节点，是在树中真实存在的末端节点，因此就宏观特征而言，在B树中所有叶节点应该集中分布于

这里还牵涉到另一个概念，也就是所谓的外部节点external nodes。在此前，我们并没有严格的区分，外部节点和叶节点，甚至在很多文献中，二者可以彼此互称。但是在B树中这两个概念是断乎不同的，尽管它们之间存在着紧密的联系。具体来说，所谓的external nodes就是叶节点的那些数值为空，其实并不存在的孩子。因此在B树中，叶节点的深度统一，其实也就等效的蕴含着外部节点的深度统一。

也与通常的二叉搜索树不同，B树的高度实际上是相对外部节点而不是叶节点而言。

2.5 阶次含义

那么B树的阶次m究竟扮演了一个什么角色呢？实际上，它既给出了B树中每个超级节点规模的上限，同时也给出了下限。

在上限方面，每个节点所拥有的分支数都不得超过m，相应的其中所含关键码的数目，自然也就不得超过m-1个。这里我们不妨约定以n来表示节点中所含的关键码数，因此拥有n个关键码的节点也就对应于n+1分支。

在下限方面，每个节点所对应的分支数也不能太少，具体来说，不得少于m的一半。请注意，这里使用的是上整，所以在m为奇数的时候是需要格外小心的。

如果将定义B树的这一套规则比喻作是一部法律，那么其中还有一条显得不那么美的额外的修正案，就分指数的下限而言，树根节点是允许例外的。在极端的情况下，树根只需2个分支足矣。

那么为什么这里需要附加这样一条显得似乎不那么自然的修正案呢？这是我们需要在此后不断理解和回答的一个问题。

既然如此，我们也用超级节点所拥有分支数的下限上限来命名B树。比如m=5的时候，每个节点的分支数自然不得超过5，同时一般节点所拥有的分支数也不得少于3，所以我们也可以称之为（3，5）树。对于6阶B树而言，分支的上限自然是6，而下限同样是3，所以称之为（3，6）树，相应的有（4，7）树、（4，8）树等等。

而在往上呢？对于4阶B树而言，自然的也可以称之为（2，4）树，饶有趣味的是，（2，4）树在B树中具有非常独特的作用和地位。我们将会看到（2，4）树与红黑树有不解的渊源。

2.6 紧凑表示

在这节开始，我们曾经通过实例对B树有了一个感性的认识，你应该记得当初我们归纳的一个特点就是，B树会显得相对而言更加的矮，更加的宽，因此在画法上，也需要做特别的处理。

如果需要完整的将一棵B树画出来，那么我们都不得不为其中的每一个关键码分别针对它的左右后代，在它的左和右画出2个引用，就像上面图一样。实际上关键码再稍多之后，无论是老师的讲稿还是教材篇幅都会很快不够用的。

一种略微紧凑的形式就是，将所有的这些引用都简化为一个点，从而得到上图（左下图）的表示。这种表示是可行的，依然清晰明了，不至产生任何歧义。

进一步的，既然所有的外部节点都位于同一层，所以不妨也将它们一概省略掉，从而得到上右图更为紧凑的表示方法。这也是老师在后续讲解中将采用的方法。

那么需要大家注意的是，不要被这些紧凑的表示方法误导。尽管没有画出，在B树中的确存在很多外部节点，而且也存在足够多个引用。

好了，接下来的一个问题自然是，这样一种逻辑结构应该如何用代码具体表示和定义呢？

2.7 BTNode

现在来讨论B树的定义与实现，与BST一样，我们首先将注意力集中于如何实现B树的节点类BTNode。

既然每一个超级节点都包含n个关键码，以及n+1个分支，不妨分别将它们视作一个线性序列。相应的，我们也可以通过此前所学过的线性序列直接来实现它，比如使用向量， 因此一个超级节点在内部可以实现为两个向量。其中的一个用以存放n个关键码，而另一个呢？则用于存放穿插于其间的n+1个分支引用。

按照这一思路，我们可以给出超级节点类的一种实现方法。每一个节点拥有一个指向父亲的引用，此外更主要的，拥有一个向量，用以存放所有的关键码，还有一个向量用以存放指向它所有后代的各个引用。

这里也给出了两种常用的构造方法，首先是构造一个空节点。另外呢？我们也可以生成一个初始规模为1的超级节点。只包含一个关键码，以及两个孩子。

而具体的实现过程呢？完全是借助此前向量以实现的操作接口。

2.8 BTree

我们再来看B树类的接口定义

作为一棵树，它首先需要记录它的规模，阶次以及根节点等必要信息。

与BST类似，这里也需要内部提供一个名为_hot的引用，以便辅助动态的操作。

就公共的接口而言，依然是我们常用的3种，静态的查找，以及动态的插入和删除。这些接口背后的具体算法以及实现，也是我们接下来将要分别讨论的话题。

需要提前指出的是，其中关键的技术，无非是在B树经过动态调整之后，一旦违反定义，我们应该如何进行调整，使之恢复为合法。

我们后面会看到非法情况无非是发生节点的上溢以及下溢，而一旦发生这种非法情况，我们都需要通过节点的分裂或合并相应的处置。因此，不妨将这两种主要的调整算法以内部接口的形式予以定义，并在稍后详细实现。

3. 查找

3.1 算法过程

在给出了B树的结构定义之后，接下来的一个话题自然就是，如何才能充分利用它，并且有效的维护它。首先来看，如何在B树中有效查找。

假定这就是一棵B树，我们此前曾经讲过，B树中所存放的词条数量极多，以至于不变完全容纳在内存中，甚至根本不能由内存容纳。因此，我们假定它相对的只能存放在速度更慢的外存中。

我们将会看到，所谓B树的查找，其诀窍在于只需要将必须的若干个节点载入内存，也就是说，通过这种策略可以尽可能的减少IO的次数。

当然，对于一棵处于活跃状态的B树而言，不妨假设它的根节点已经常驻于内存。现在假设我们需要在这棵树中，查找特定的关键字key。

1. 于是 我们首先会在常驻于内存的这个根节点中进行一次查找。你应该记得，每一个节点中的关键码均已存成一个向量，因此我们这里实施的无非是一个顺序查找。如果能够在某个特定位置命中，我们的查找随即以成功告终。

2. 因此我们不妨再看如果查找失败，又当如何处置？假设失败于一个特定的位置，我们知道在这个特定的位置，应该预先已经记录了一个引用，这个引用将会指向B树中下一层的某一个节点。是的，因此我们继而可以沿着这个引用，找到下层的那个节点，并且将它载入到内存之中，也就是说，我们的查找深入一层，而代价呢？做了一次读入性的IO操作。

3. 当然，既然我们已经搜索到这样一个节点，就可以断定，如果目标关键码的确存在于这棵树中，那么就必然存在于这个节点所对应的子树中，于是我们继续在这个新载入的节点中进行一次查找。同样，我们可能在某个位置命中，从而成功返回。

请注意，借助向量结构，我们在此只需进行一次顺序的查找。

4. 而反过来，如果在这个节点中的查找以失败告终呢？此时我们在新的节点中，也必然会停止于某个适当的位置，而且在这个位置，必然也预先记录了一个引用，使得我们可以顺利的找到在这棵B树中下一层的某个节点。同样，如果目标关键码存在于整个B树中，那么至此可以断定，它必然存在与这个节点所对应的这棵子树中。

5. 因此，为了进一步进行查找，我们也需要再做一次IO，将这个下层的节点载入内存。以下的过程和刚才几乎一样，具体来说，我们也需要在这个新载入的节点中做一次顺序查找，如果成功，完则罢了，否则的话，我们依然借助在失败位置的引用，进而找到再下一层的节点，乃至再下一层，乃至再再下一层。

6. 在最坏情况下，这个过程有可能会反复持续到叶节点。也就是说，充其量我们需要抵达B树底层的一个叶节点。在这里，我们依然需要针对目标关键码做一次顺序查找。同样，查找可能成功，也可能失败。而且即便失败，也不要紧，因为我们依然可以顺着失败方向的引用，找到下一层的节点。没错，下一层的节点尽管它并不是真实存在的节点，而只是一个虚拟的外部节点。至此，我们就可以报告整个查找以失败告终。当然，还有另外一种情况，也就是这个外部引用，实际上指向的是一棵存放于相对而言更低层次存储级别上的B树，这也是为什么将此类节点称作外部节点。因为借助它们，我们可以将存放于不同存储级别上的B树串接起来，构成更大的B树，当然再此，我们不妨将目光放在当前这一级存储上，而假设查找的确是以失败告终。

纵观整个过程，可以看到所谓对B树的查找，无非是由一些列在内存中的顺序查找，一级一些列的IO操作，相间隔组成的一个操作序列。

3.2 操作实例

来看这样一个具体的实例。首先确认这是一棵5阶的B树，也就是所谓的（3，5）树，因此，其中每个节点至多拥有5个分支，而除根节点之外，其他的节点也至少应该拥有3个分支。就关键码而言，每个节点至多拥有4个，而除根节点之外，每个节点也至少拥有2个。

现在我们假设需要查找75，于是我们首先对常驻于内存的根节点进行一次顺序查找，并且顺利在这个位置命中。

接下来，再考察一个略微复杂一些的情况，也就是试图查找69。为此我们同样首先需要对常驻内存的根节点进行一次顺序查找，这次查找终止于介乎53与75之间的这个引用，于是我们顺藤摸瓜，沿着这个引用将下层的这个节点63读入内存（此处省略1000000秒），并且在其中进行一次顺序查找，不出意料，最终可以成功的找到这个关键码。

再来看一个更为复杂的情况，不妨试图查找关键码49。同样的，我们的查找依然起始于常驻于内存的根节点，经过在根节点的一趟顺序查找，虽然以失败告终，但是却可以确定一个引用，这个位于53左侧的引用指向下层的另一个节点，因此我们需要经过IO操作将这个节点19 载入内存（同样，再次省略100000秒），并且依然在其中针对49做一趟顺序查找，不出意料尽管这趟查找依然失败，但是它却会给出一个引用，顺着这个引用，我们又可以深入到B树的下一层，并且将对应的那个节点38经过IO载入内存（还是省略100000秒），接下来依然需要在这个新的节点中针对目标49做一趟顺序查找，不出意料，查找将会成功的终止于49。

作为失败查找的一个实例，我们不妨来考察针对于45的一次查找，经过简单的目测，不难确定，查找应该失败于这里的41和49两个关键码之间。就整个查找所涉及的节点而言，针对于45的查找，与刚才针对于49的查找实际上是一样的。也就是说，我们首先要对根节点进行查找，然后再转向这个节点19（依然省略100000秒），接下来再进而转向这个节点38（依然省略100000秒），并且在这个节点中，经一趟顺序查找，最终失败于41和49之间。请注意，这里的查找失败，是以介乎41和49之间的那个外部节点来指示。尽管在这种紧凑的画法中这些指向外部节点的引用并不能看见，但它们的确存在，而且是十分重要的。

由此我们也可以得出一个推论：对于B树的失败查找，必然都失败于最底层叶节点所下属的某个外部节点处。简单记忆法：失败查找必然终止于外部节点。

3.3 算法实现

以上B树查找算法的策略，又当如何以代码的形式具体实现呢？这里给出一种可能的是实现方法。

假设我们的目标关键码为e。

1. 查找过程中的逐层深入在这里是通过一个while循环来具体兑现的，在进入循环之前，首先需要对内部的_hot引用进行初始化，同时将v初始化为指向树根节点，在这个引用v变空之前，整个循环会持续的进行下去。
2. while循环的每一步迭代，都对应于在当前层当前节点中的一趟顺序查找。具体的，这可以兑现为在当前节点的关键码向量中，通过向量的查找接口，查找目标关键码，如果查找成功，则直接返回这个节点，这也是该算法成功返回的出口。反之，至此意味着当前顺序查找是失败，于是我们就需要找到当前节点的某个孩子，通过IO将其读入，并且重新令v指向这个新的节点，当然在此之前，我们还需要同步的更新hot引用。

那么究竟是哪个孩子节点呢？这里的原则是，如果此前失败返回的秩为r，则应该转向第r+1个孩子。

请注意，在这里每个节点中所包含的关键码，以及对应的后代引用，尽管分别都是组织为向量，但在逻辑上不妨将它们稍作错位，按上图这种形式来排布。这种排布是有道理的，因为它可以更加便捷和清晰的让我们看出每个节点与它的左右孩子之间的关系，是的，每个节点与它的左和右孩子。你也应该记得，我们此前在实现向量的查找算法时，曾经对返回值的语义做过严格的界定，也就是说，返回的必然是不大于目标关键码的最大值。因此如果顺序查找失败于第r个关键码，也自然应该顺着第r+1个引用深入到下一层继续搜索。

请记住这样的对应关系，第r个关键码以及第r+1个后代引用。

因此，这种迭代也不可能一直持续下去，即便在最坏的情况下，v也迟早会变成空。此时可以退出while循环，并且通过返回null报告查找失败。

3.4 主次成本

那么按照以上的策略以及实现方式，B树的查找算法，需要运行多长时间呢？
无论是从刚才的代码，还是从上图示意图，我们都可以看出，对B树的查找，依然是一个逐层深入，不断减而治之的过程，而且在每一个层次上，至多只会涉及到一个节点，因此，影响整个查找算法效率的最主要因素应该是树的高度。

那么在每一个高度层次，我们都需要做哪些工作呢？我们所消耗的时间，都去哪了呢？
无非两个方面。

1. 第一就是这些灰色线条 （上图中带箭头的曲线），也就是为了读入对应的节点所进行的IO操作。我们已经详细分析过，就单次操作而言，此类操作要远远慢于任何一次内存的操作，因此这方面的时间消耗，也构成了我们在每一层次上所需时间的主体。
2. 而另一方面呢？无非是在每个节点内部进行的顺序查找。没错，是顺序查找，尽管在我们刚刚给出的具体实现中，这部分查找都是通过向量内在的查找算法予以实现的。你应该记得，对于这种有序向量，完全可以采用性能更高的查找，比如二分查找，但是鉴于内外存访问在速度上的巨大差异，这种优化效果，实际上是微乎其微的，甚至反而可能是有害的，这背后的原因非常值得细细的体味和把玩。

我们此前介绍过，为了与IO操作的延迟相匹配，每一个节点的大小应该尽可能设计与一次IO对换的页面大小相匹配，通常这个数值大致为若干个KB，因此每个节点内所含关键码的数目都大致取做几百，而实验结果表明，对于如此规模的有序向量，相对于顺序查找，二分查找的效率反而更低。

接下来一个问题就是，B树的高度h与关键码数目n之间是一个什么样的关系呢？可以预期，渐进的应该依然是logn，那么关键是，常系数又会有多大的区别呢？

3.5 最大高度

以下，分别从最大和最小两个方面，对B树树高范围做以估算和界定。

首先再次强调，对于B树而言其高度由外部节点的深度决定的。

如果从0开始自顶而下依次编号，那么树根节点所在的就应该是第0层，其孩子节点所在的应该是第1层，再往下，第2层，依此类推，直至叶子节点所属的 h-1 层，以及外部节点所属的第h层。

我们的第一个问题是，对于固定阶次的B树，如果其中包含的关键码数也固定为N，它的最大高度，可能达到多少呢？

不难理解，在阶次与关键码数固定的前提下，为使整棵树的高度更大，每个内部节点中所包含的关键码数都应该反过来尽可能的少。形象的说，每个内部节点都需要尽可能的瘦，因此其中关键码的数目都应该尽可能的取做下限，而相应的分支数应该取做m/2的上整，如此我们来考察各层的节点数。

1. 首先顶层应该始终只包含树根这一个节点，其次作为根节点的特权，它在最瘦的时候，可能只包含一个关键码，同时只相应的拥有两个分支。
2. 而以下的各层呢？每个节点分支数都至少是m/2的上整，因此以下各层所含节点的数目应该以m/2的上整为倍数成几何级数递增。

具体来说，第K层所含的节点数，自然应该就是 $n_k=2\ast [m/2{]}^{k-1}$。

3. 这个规律适用于所有各层，直至我们需要考察的外部节点所在的第h层，自然的，这层所含的节点数就是$2\ast [m/2{]}^{h-1}$。

应该记得，我们在介绍B树实例时曾经总结的一条规律：如果一棵B树中包含的真实关键码数为N的话，那么其对应的外部节点总数应该恰好就是N+1。

具体到这里，也就是 N + 1 = $n_h$，通过数学归纳，不难证明这一性质。我们也可以对这一结论做一简单的理解，也就是说，树中所包含的N个关键码，如果理解作对应于N种成功查找的可能，那么外部节点也各自对应于一种失败的情况。既然有N种成功的可能，自然也就是N + 1 种失败的可能。
  ~  
N个内部节点，N+1个外部节点
N种可能情况，N+1种失败可能

总而言之，我们借助算两次的技巧，分别得出了$n_h$的一个确界和下界，现在$n_h$的历史使命已经完成，我们可以将其忽略掉，并转而考察由它的确界和下届所构成的不等式，略加整理之后，我们即可得到这样一个不等式$h\le 1+lo{g}_{m/2}[(N+1)/2]=O(lo{g}_{m}N)$ ，在大O意义下，也就是log以m为底N的对数，如果将m视作常数，也就是logn。与BST性能，渐进同阶。

然而正如我们所设计的，B数的意义并不在于降低搜索的渐近时间复杂度，而是更加关注于常系数意义下的优化。那么关于常系数的改进，这里的阶次m又扮演了一个什么角色呢？

将B树性能与常规BBST的性能做一对比，即可得到这样一个结果

比如按照常规的设置，将阶次 m取做256，即可发现B树的高度，大致是所对应BBST高度的1/7。应该还记得我们此前关于大学4年学制和30年学制的比喻，是的，这个结果背后的原因恰恰正在于此。

3.6 最小高度

采用类似的方法，我们也可以对B树的高度给出一个下届。

我们的问题完全对称，当阶次规模确定时，B树的高度最小不过多少？

1. 同样的，为了使全树的高度最低，每个内部节点所包含的关键码，就应该尽可能的多。想象的说，他们都应该尽可能的胖，当然这种胖必须符合B树的规则。也就是说，分支数不得超过m。因此尽管根节点只能有1个，但它却可能拥有m个孩子，而这m个孩子呢，可能又分别各自拥有m个孩子，以至$m^2$个孙子，如此类推。
2. 接下来，同样考察外部节点所在的最后一层，由上类推，我们可以得到外部节点数的一个上限，而另一方面，此前的恒等式$N+1=n_h$依然成立，至此只需忽略掉起临时桥梁的$n_h$，并略作调整，即可得到不等式
   
   在渐进意义下，这个下届依然是$lo{g}_{m}N$ 。同样的，为了体验阶次数m对计算成本的影响，不妨以256阶B树为例，经过简单的估算不难发现，相对于规模相仿的BBST，256阶B树的高度尽管有所下降，但是充其量不过下降到1/8，是的1/8，你应该记得，B树的高度上界在大O的意义下也渐近的应该是$lo{g}_{m}N$。

综合起来，我们可以得知，当关键码总数固定时，B树高度的上下浮动范围是非常有限的，或者等效的说，其高度几乎不发生变化。

此前我们也估算过，相对于同等规模的BBST，256阶B树的高度至少也应降低至1/7，这两个数值相差不大，这也具体的验证了B树的高度变化幅度有限这一事实。

4. 插入

4.1 算法框架

在了解了B树的查找算法及其效率之后，接下来一个自然的问题就是，B树的动态操作，又当如何高效的实现？以下，首先讨论它的插入算法。

假设经过查找，我们确定需要在上述节点的两个关键码之间插入一个新的关键码，也就说，从逻辑上看，这个节点需要变成上面这种形式，这个深色的节点正是我们希望插入的关键码。那么这样一个转换的过程应当如何实现呢？

来看一种可能的实现方法

1. 首先，我们需要调用B树的查找算法，并且不妨假设，经过查找之后，可以确定该关键码尚不存在。于是根据我们的语义约定，这次查找最后应该终止于一个由_hot所指向的真实节点，你应该记得，_hot所指向的应该是位于最底层的一个叶节点。
2. 于是接下来，我们进一步在这个节点的关键码向量中查找，以确认新的关键码究竟应该插入在哪个原有关键码的后边。请特别注意，这里_hot->key.search( e )的search是向量的接口，而这里BTNodePosi v = search( e )的search是B树的查找接口。于是，根据向量查找操作的接口语义，它的确会返回不大于目标关键码的那个最大的关键码。
3. 因此，如果返回的秩为r，我们自然就应该将新的关键码作为第r+1个元素，插入向量当中。从图中所示的逻辑次序而言，也就是，紧随于插入位置之后，插入在这里。
4. 在关键码增加一个之后，分支数也需要相应的增加一个。应该还记得，建议的画法，也就是让关键码向量与分支引用向量，如此交错的对齐，如此，便可清晰明了地显示，每个关键码及其对应的左右分支，这里为了理解方便，我们不妨认为，因为这个新的关键码的插入，而引入的新的分支，就是该关键码的右侧分支。这也是为什么我们在r+2的位置上插入一个新的分支，当然，新的这个分支目前为空。

其实，稍加观察，不难发现，既然此时的这个节点是位于底层的叶节点，因此，其下属的分支，无论是此前的，还是新引入的，都应该是空。因此，一种更为简明的方法是，直接在分支向量的最后插入一个空分支，这种方法与这里给出的方法完全等效，至不过稍微费解而已。

5. 接下来，如果没有什么特殊情况发生，我们只需动态的更新全树的规模，即可成功返回。

然而不幸的是，在引入一个新的关键码之后，当前这个节点可能会违反B树的约定，也就是因为其下属的分支增加了一个，从而导致分支总数超过了B树的阶次m，因为新关键码的引入，而导致所属节点的分支数超过B树阶次的情况，称作上溢 overflow，这样的一种非法情况，必须及时处理。为此，我们需要借助一种技术，称作分裂。

4.2 分裂

确切的说，如此发生上溢的节点应该恰好拥有m+1个分支，相应地，也恰好有m个关键码，我们不妨将其记作$k_0$一直到$k_{m-1}$。

对上一节点的分裂要尽可能的均衡，因此，在这里不妨采用中位数s作为分割线。

中位数（median）亦称作中值在向量中，就是秩居中的元素。亦称，A[0,n)中的A[n/2]，比如，A[0,5)中的A[2]，又如，A[0,6)中的A[3]。

也就是说，左侧取0到s-1，右侧取s+1到m-1，而$k_s$作为独立的关键码，居于两者之间。

而具体的分裂规则是需要将分界的$k_s$关键码提升一层，交给此前的父亲（如果有的话），并将刚才左右的两组关键码分别作为它对应的孩子分支。

来看一个具体的实例。

假设在上图上面的节点中，因为某个关键码的插入，使得关键码的总数多达6。如果该节点所属的恰好是一棵6阶B树，那么这就意味着，在此处发生了一次上溢。为了进行修复，我们要在这6个关键码中选取其中的中位数，相应地，以关键码37为界，原先的关键码将会分为左侧的3个一组，以及右侧的2个一组，接下来，中位数关键码37将顺着指向该节点的那个引用逆行向上，并在其父节点中插入于这个引用所对应的左右两个关键码之间，其结果如上图下图所示。
  ~  
相应地，原先的这一组关键码就被分割为了左右两组，各自成为一个独立的B树节点。在增加一个引用之后，这两个分裂出的节点恰好可以作为此前被提升的那个中位数关键码的左和右孩子。

至此你不妨验证一下，经如此分裂之后所得的左右两个新节点，尽管关键码的数量相对于此前几乎折损一半，但依然不会低于B树关于关键码数所设定的下限。

相应地，我们也不妨反过来体味一下，B数关键分支数所设定的上界和下届，具体来说，也就是m和[m/2]的上整，正是得益于这条规则的精妙 ，使得我们的分裂操作可以在这两个界限之间游刃有余。

至此，刚才一度存在的上溢缺陷的确在这个高度已经得到了修复，但故事并没有就此终结。细心的你可能已经发现，这等效于在这个父节点中插入一个新关键码，不难理解，父节点在此时同样存在发生上溢的风险。比如倘若它在此前恰好已经处于即将发生上溢的临界状态的话。

4.3 再分裂

是的，如果上溢节点的父亲原本已经处于饱和状态，那么，如果经过分裂，并将中位数关键码插入其中的话，父节点也将随即发生上溢。

当然这并不是什么了不起的事情，这无非也是一次上溢而已。如此，我们完全可以如法炮制，继续在这个新的上溢节点中挑选出中位数关键码68，并以它为界，将这个节点一分为二。同时，中位数关键码提升一层，转交给它的父亲。

当然，这种上溢的现象的确可能会持续的发生，然而，好消息是这种上溢的传播过程满足单调性。上溢缺陷可能会传播，但只能是逐层向上。也就是说，就高度而言，逐次发生上溢的节点应该会持续的向上。也就是说，充其量也不过是自底而上的遍历各层，并最终抵达根节点。

当然，根节点的上溢处理的确有些不同。

4.4 分裂到根

比如，仍以刚才的6阶B树为例，假设经过若干次传播之后，最终在它的根节点处也发生了上溢。此时，我们依然需要以这个中位数关键码为界，将原先的节点一分为二，同时，依然试图将这个中位数关键码向上转交给父节点，然而此时作为根节点，它的父节点并不存在。这这种情况下，我们不妨就令这个提升之后的中位数关键码独自成为一个节点，也就是说，它将成为这棵B树新的根节点，因此，整棵B树的高度也会随之增加一层。这也是导致B树增高的唯一情况。

请注意，在B树刚刚长高的这个时刻，新的根节点只拥有两个分支，无论B树的阶次是多少。

现在你应该理解了吧，为什么在定义B树的那一整套规则中，非要加入一条貌似不是那么完美的修正案。是的，正是因为有那么一条修正案，才使得B树的根节点拥有少于m/2个分支是合法的。也就说那条修正案是必须的，是断乎不可省略或变通的。

好了，由以上的分析我们可以看出，在消除上溢缺陷的过程中，我们最多只需在B树的每一层次做一次分裂，也就说，累计不过h次，而每一次分裂本身，只不过是一个常数的操作O（1），因此，总体而言，整个插入算法所需要的时间应该线性正比于B树的高度，即O(logmN)。这也是我们所期望的。

4.5 实例演示

接下来，就通过几个实例加深对B树算法过程的理解。

首先，请确认这是一棵4阶B树。其特点是，每个节点的分支数至多是4，至少是2。或者等价的，每个节点所包含的关键码数至多为3，至少为1。

首先，假设我们要插入555，经过简单目测，不难发现，应该将其紧邻于556，插入于这个节点之中。是的，经过逐层查找，可以确定待插入的位置。

接下来，我们也的确只需将555紧邻于556的左侧，插入于这个节点之中。

现在，我们来检查一下，尽管这个节点增加了一个关键码，但关键码的总数依然不超过4阶B树所对应的上限。这就意味着这次插入操作顺利结束。

以下，我们再假设需要插入关键码444，经简单的目测，不难发现，应该将其紧邻于435的右侧，插入于这个节点之中。是的，我们的确可以通过查找，确定这个节点的位置。

并的确如我们所预期的，将其紧邻于435的右侧，插入于这个节点之中。

然而，与刚才的情况不同的是，当前这个节点，在接收了444之后，其所含关键码的总数已经超过了上限3，也就是说，此时发生了上溢。根据我们修复上溢的算法，此时应该以其中的中位数关键码为界，将这个节点一分为二，同时，中位数关键码提升一层，并纳入到父节点。

当然，在父节点接纳了一个新的关键码之后，我们依然要对它再进行一次核对，所幸的是，它依然是合法的。

再接下来，我们假设需要插入500。整个过程是，我们首先通过查找，确定这个节点，并且相应地，将500插入于482与511之间。

接下来，我们同样会发现这个节点因此发生了上溢，为修复这一缺陷，我们依然故伎重演。也就是，以中位数关键码511为界，将这个节点一分为二。同时，511提升一层，插入于父节点中的适当位置。

至此，尽管底层的上溢缺陷得到了修复，但父节点却因为额外接纳了一个关键码，而随即发生上溢，当然，在这种情况下，我们依然可以如法炮制，继续在此做一次分裂操作。

同样的，我们可以看到，刚才那一层上所出现的上溢缺陷得到了修复。然而遗憾的是，再上一层的父节点，也就是此时的根节点，也随即发生了上溢。当然，在这时，我们也依然需要对这个节点做一次分裂操作。

请注意，刚才的那个中位数关键码虽然因此得以提升一层，但是因为此前已经是树根，它并没有实质的父节点，因此，这时的处理方法就应该是，让这个被提升的关键码独自成为一个根节点，而整棵树的高度也因此增加一层。我们讲过，这也是B树得以长高的唯一可能，至此，关键码500的插入过程才得以最终完成。

尽管我们这里展示了一个，因为某关键码的插入，而需要不断分裂，并一直持续到根的所谓最坏情况。但是需要指出的是，这种最坏情况出现的概率其实非常非常的低。其概率之低，远远超出了你的直观想象。

4.6 实现

结合下面示例，理解上述代码

5. 删除

5.1 算法框架

接下来，我们讨论B树的第二类动态操作，也就是删除。那么B树的删除操作是否只是插入操作简单的逆过程呢？我们将会看到二者有很紧密的联系，但又不尽相同。那么，应该如何将某个特定的关键码从其所属的节点中剔除掉，从而完成这样的一个转换呢？这里给出一种可能的实现方法。

1. 首先，与插入算法一样，我们也需要经过一次查找，并不失一般性，假设待删除的关键码的确存在，而且就存在于返回的节点v中。
2. 于是，进而通过向量的查找算法，在v中确定，目标关键码e所对应的秩。
3. 当然，我们希望此时的节点v是一匹叶子，然而，这一点并非总能保证。如果它不是一个叶节点，我们就要深入到关键码e所对应的右子树中，然后一路的沿着最左侧的分支向下，如此最终抵达的节点u就必然是e的直接后继。以下，只要令u和v互换位置，即可等效的保证，待删除的关键码e来自名为v的某一个叶节点中，而且这个关键码在v中对应的秩为r。
4. 因此只需将这个关键码从关键码向量中剔除。同时，删除其对应的那个分支。 与插入算法同理，如果你不太在意算法的可读性，在这里，你要删除的未必是第r+1个分支，而可以选择其中的任意一个，比如最后一个。因为所有的这些孩子，此时无非都是空。
5. 同样的，在你更新了规模记录之后，故事还并没有完结。因为与插入过程完全对称的，在损失了这样一个关键码之后，当前的节点v，有可能会突破B树关于分支数所设定的下限，对称的，我们也称这种现象为下溢——underflow。为此我们在返回之前，还需要检查并且处理这种情况。

那么具体的，如何处置这种情况呢？

5.2 旋转

首先，请确认，若节点v果真刚刚发生下溢，那么它应该恰好包含m/2-1个分支，以及m/2-2个关键码。是的，刚刚发生下溢的节点v应该恰好只包含m/2-2个关键码。

联想到插入算法中，通过分裂来解决上溢问题，你可能会首先想到通过合并来解决下溢问题。是的，这只是可供选择的预案之一，但优先级更高的，并不是它。

事实上，这个刚刚下溢的节点会首先左顾右盼，如果有某一个兄弟拥有足够多个关键码，比如不是一般性，假设它的左兄弟存在，而且这个兄弟所拥有的关键码数不少于m/2的上整。那么它的这个左兄弟，就有可能向v借出一个关键码。这里你需要核算一下，在这种情况下，左兄弟向v借出一个关键码之后，即可解决v的下溢问题，同时自己也不至因此而发生下溢。你的构思非常的好，可惜有一点小小的难题需要解决。

我们知道，如果的确存在这样的两个兄弟，那么它们的父亲也必然存在，而且在它们的父亲中必然有一个关键码，比如说y，会介于它们之间。作为搜索树，B树同样应该符合中序遍历意义上的顺序性，这就意味着，作为左子树中的一员，L中的所有关键码，都应该小于y，对称地，作为右子树中的一员，V中的所有关键码都应该大于y。因此，将L中的任何一个关键码直接移送到V中，都将破坏这一局部，乃至全局的顺序性，这是万万不可的。

然而，反过来，这里的技巧也恰在于此，这样一种转接的思路，关键在于，我们需要借助关键码y，曲线地转接，就像所谓地三角借债一样。

实际上，V并非是直接向它的左兄弟去借入一个关键码，而是从它的父节点中，去借出y这个关键码。你没听错，的确是从父节点中借出一个关键码，不难想象到，在借出了这个关键码之后，父节点在y这个位置上应该会出现一个空缺。然而，这并不要经，不要忘了，这里还有一个节点L，它还足以向父节点借出一个关键码，以填补刚才所留出的空当。问题是，在L中，应该借出谁呢？是的，应该借出的是在其中数值最大，从图中看，位于最右侧的这个关键码，我们不妨称之为x。这样，在经过了连续的两次借出之后，节点v从父节点处获得了一个关键码y，使得自己不再下溢，同时，父节点也从左侧节点中，借入了一个关键码x，从而实现了收支的平衡。同时，左侧的这个兄弟节点L，也并没有因为损失一个关键码，发生下溢。更重要的是，经过了这样一种貌似曲折的转借，局部乃至全局的顺序性依然得到了延续。整个变化过程，可以转化作关键码y被转化至节点V，而关键码x则从L转移至P。因此，也不妨形象的将这种调整，称作旋转。

当然，只要下一节点V拥有一个满足同样条件的右兄弟R，我们也可以通过对称的旋转来修复下溢。然而很遗憾，这样的左兄弟和右兄弟未必存在。一种极端情况是，V的左右兄弟或者不存在，或者不足以借出任何的关键码，对于这样的情况，我们又当如何应对和处置呢？

5.3 合并

好，我们现在就来考察这样一种情况，这也是我们需要考察的最后一种情况，也就是说发生下意的节点在经过左顾右判以后，发现无论是它的左兄弟还是右兄弟，都或者不存在，或者所包含的关键码还不足够多，以至于不足以借出一个。当然，情况不至于糟糕透顶，因为左右兄弟中还至少存在其一，不失一般性，假设下溢节点 v 的左兄弟至少是存在的，尽管它不足以借出任何关键码。

当然，此时处于下溢临界状态的节点 L 应该恰好拥有 m/2 -1 个关键码。细加观察，不难发现一个现象，此时无论是 V 还是 L，关键码数都非常的少。这三者的总和也没有超出B树关于单个节点中所含关键码总数所设定的那个上限，具体来说也就是 m -1。顺着这个思路，我们不难得到一种修正此处下溢的方法，具体来说也就是从父节点中将这个分隔的关键码 y 取出来，并且就以这个关键码作为粘合剂，将刚才的 V 以及它的左兄弟 L 合并起来，成为一个新的节点。

在这个新的节点中，尽管表面看来所含的关键码很多，但是正如我刚才所分析的，其总数也不是超出 m -1。因此它必然是一个合法的节点。而相应的，原先节点 V 所发生的下溢，也在无行之中被排解掉了。

在此之后，原先关键码y所对应的两个分支也应该合并起来，并指向这个新生成的大节点。同样，我们需要验证一下，至此这个局部乃至全树都依然保持中序遍历意义上的顺序性。在某一种情况下，故事依然没有完结。

什么情况呢？细心的你可能已经注意到了，经过这样的处理之后，父节点无形之中损失了一个关键码。我们可以等效的认为刚才是从父节点中删除了这个关键码。因此在这个父节点处可能相继地发生一次下溢。

不难理解，这也是故事得以延续，使得我们必须做进一步处理的唯一可能。那么果真发生这种情况，又当如何处理呢？可以送给你4个字，如法炮制。没错，借助旋转以及合并这两种手段，我们足以处理每一次新发生的下溢。

当然，这里的好消息依然是即便会继续发生下溢，它的高度相对于此前的那次下溢也必然会有所提升，也就是说整个过程具有单调性。因此整个调整的过程或者在中途停止，或者充其量抵达树根。

也就是说，如果全树高度为h，那么整个修复下溢的过程，累计迭代步数也不超过O（h），这也是我们预期的好结果。

5.4 实例演示

接下来，通过几个实例加深对B树算法过程的理解。

首先确认这是一棵5阶B树，其特征是节点内所含的关键码数最多为4。而除根节点外的其他节点所含关键码至少有两个。现在，假设删除249，为此，我们首先需要通过查找定位其所属的节点。

接下来将这个关键码从该节点中剔除掉，导致这个节点发生下溢。我们知道在修复下溢时，我们并不急于去做合并，而应该首先左顾右盼。的确，此时的右兄弟包含四个关键，足以借出一个。

当然我们也知道这种借出是迂回的，具体来说下溢节点应该首先向它的父节点借出268，而右兄弟的最左侧关键315则应该转而交给父亲填补268留下的空缺。这就是我们所说的旋转。

请注意，果真若是发生了旋转，不仅原下溢节点会得到修复，其余所涉及的节点，无论兄弟还是父亲都不至因此继而发生下溢。因此这种解决方案是彻底的，也就是说整个删除操作至此顺利结束。

当然还有其他的可能，比如我们可能会接下来需要删除619。同样的，为此我们需要经过查找确定619所属的那个节点，然后将这个关键码从这个节点中剔除掉。

可以看到在损失了一关键码之后，这个节点发生了下溢。为了修复这一缺陷，我首先要站在这个节点的角度左顾右盼。然而很遗憾，它没有左兄弟，而右兄弟虽然存在，但可惜自己已经处于即将下意的边缘，临界状态并不足以借出任何关键码。

也就是说，旋转的技巧在此并不可行。我们只得借助另一技巧，也就是合并，这等同于分裂的逆过程。就这个例子而言，我们需要从这两个节点的父节点中找到介于他们之间的那个关键码，也就是703，并且将这个关键码取出下移作为粘合剂，将这两个节点和二为一。

请注意，尽管此前位于最底层的下溢缺陷得到了修复，但是更高一层的这个父节点却随即也发生了下溢。为了修复这一缺陷，我们依然需要站在这个节点的角度左顾和右盼。情况与刚才居然类似，没有右兄弟，而左兄弟依然因为处于下溢的临界状态而无法借出任何关键码。

因此我们不得不再次求助于第二种技巧，也就是合并。具体来说需要从父节点，也就是此时的树根中找到介于下溢节点及其兄弟之间的那个关键码，可以注意到，其实此时根节点只含有唯一的一个关键码 528。

尽管如此，我们也需要将这个关键码取出，并且下移作为粘合剂，将下溢节点及其兄弟粘着合起来，构成一个合法的节点。

可以看到，的确如我们所期望的，在这一层上的下溢缺陷的确得到了修复。然而接下来出现的问题是，原先只包含唯一关键码的那个根节点，现在却变成空的了。我们知道在B树中根节点拥有特权，只需拥有两个分支即可，但即便如此，却不可能只拥有一个分支。

实际上这样一个跟节点是没有任何实际用处的，因此这时我们不妨将它删去，而用刚才经合并所得的这个节点取而代之作为新的树根节点。因此结果是这样，可以看到整棵B树的高度因此降低了一层。

这也是B树高度得以下降的唯一可能，具体来说，在删除节点之后需要进行合并操作，而且这种合并操作会不断地向上蔓延，直到树根，而树根节点只含有唯一的一个关键码，以至于在借出这个关键码之后，树根成为空节点。

同样需要说明的是，尽管这种最坏情况不难构造出来，但在实际运转过程中却是十分罕见的。

5.5 道法自然

在告别本节之前，不妨重新打开这幅我们已经非常熟悉的图，应该记得我们在本节开篇所提过的那样一个问题，B树为什么会被设计成为这样一种相对比较矮却又比较宽的形状呢？

现在你应该可以做一总结，并且有所领悟。我们知道所谓对B树的访问，无非是由一系列的外存操作和内存操作交替的组成。有多少次外层操作就有多少次内存操作。因此为了保证整个访问的高效率，一个基本的原则就是应该是外存操作的代价与内存操作的代价大致相当。

实际上 B 树能够做到这一点，而此前 AVL 之类的 BBST 却不能做到这一点。应该还记得中学物理所学过的折射现象，在两种介质的分界面处，光线的传播方向可能发生偏折。

你也应该记得物理学就此所给出的一个形象的解释，也就是所谓的最小光程原理，因为在这样两种介质并存的情况下，唯有如此才能够使得光线所传送的实际距离变得最短，或者反过来讲传播的最快。

从这一点讲，大自然是最聪明的设计者，而B树的设计原理也在于此，其设计过程某种意义上讲是在模仿自然的这种最优秀，也就是我们所说的道法自然。其实在这个图中，B 树大致有两个方向。

首先是水平方向，它对应的是在每个节点的内部所做的搜索。这种搜索因为是在内存中进行的，所以速度相对而言非常之快。同时我们还有垂直这个方向，也就是说沿着垂直方向它所对应的是磁盘操作。

也就是说在树中每下降一层我们都要付出一次 IO 操作的代价。我们知道这种时间代价相对于内存操作来说至少要高出5个数量级。这样一种情况，完全可以类比于光线穿越两种物质之间的分界面。

既然光线在这种情况下会聪明地通过改变方向达到速度上的最优，那么 B 树通过适当的调整自己的形态来适应这种现实也就再自然不过的了。