图解B树

2019 - 04 - 26

Posted by 小张

背景

注:本文假设读者有搜索树（排序树）的基础知识。

我们知道计算的存储系统是一个分级结构（一般来讲，存储器速度越快，价格也越高，因而也越难满足大容量的要求）

首先容量和类型不同的存储器在访问速度上的差异是极其悬殊的，就以我们最常见的磁盘以及内存这两级存储为例： 就传统的旋转式磁盘而言 它的访问速度大致是毫秒量级，而典型的内存呢 大致是在纳秒量级，如果 以一秒为基准，前者是10的-3次方 而后者呢是10的-9次方因此 二者的差异大致是在10的5至6次方，即使保守的估计 也是5个数量级,也就是说 如果将内存的一次访问比作是一秒 那么响应的一次外存操作则是一天（比喻，非精确计算），可谓天上方数日，人间已千年。

因此对于分级的存储系统，对于最常用的数据尽可能放在最高层，更小的存储器中，实在找不到数据，才向更低层，更大的存储器索取。

批量读取

如果我们希望从磁盘之类的外存中去读取一个字节，其时间成本与读入一千个字节几乎是一样的，典型的存储系统的确大多是采用批量式的方式来支持读或者写操作的，具体来说 无论我们是需要从内存向外存输出数据，还是需要从外存向内存读入数据，涉及的数据都是以页面为单位进行核算和组织的，这也给了应用预读功能奠定了基础（局部性原理）。

因此在涉及频繁而大量数据访问的算法中，我们就需要充分利用这样一个特性，也就是说我们要么就一次性的读写若干个KB 要么就一个字节也不访问，才能够达到尽可能的优化，那么我们的主角B树 在其间又能起到一个什么样的作用呢？

B树介绍

B树是为了磁盘或其他直接存取的辅助存储设备而设计的一种平衡的多路搜索树。B树类型于红黑树，但是它在降低磁盘I/O操作方面要表现得更好一些。这样一种多路的搜索树，与我们此前所熟知的二路搜索树在本质上讲 其实是等价的，如果我们将多路搜索树中的每一个节点称作超级节点的话那么每一个超级节点都可以认为是由若干个二路节点经过适当的合并以后得到的，来看这样一个实例

如果我们忽略掉这些方框，不难看出这其实就是一棵二叉搜索树的局部，现在我们两层两层的来考察其中的这些节点，具体来说 每一个节点以及它的左和右孩子，如果我们将每一组这样的父子三个节点合并成一个超级节点（也可称为内部节点），那么整棵树就可以等价的变换为这样一种形式，具体的 原先的父节点居中，原先的孩子则经过提升与之并行的列于左右，这种节点的确可以称作是超级节点，因为其中不再只含有一个关键码 而是多个。

就这个例子而言 每个超级节点都含有3个关键码，同时相应的也就拥有4个分支，可以看到 如此每两代两代的合并之后，每个节点都将拥有3个关键码 以及4个分支。

一般的 如果每d代都进行一次合并，那么每个超级节点都将拥有2的d次方路分支，以及相应再减少1个关键码。

注意：在上面叶节点中，我们画了指向外部的箭头，我们称这些箭头指向的是外部节点（external nodes），所谓的external nodes，就是叶节点的那些数值为空 其实并不存在的孩子，因此 在B树中 叶节点的深度统一，其实也就等效的蕴含着外部节点的深度统一，也与通常的二叉搜索树不同，B树的高度实际上是相对于外部节点而不是叶节点而言。可以这样来理解外部节点，在存储系统中，外部节点可能指向的是下一级的容量更大速度更慢的系统（或者另一个存储系统中的B树），为了简化，后面我们将不再把外部节点画出来。

既然我们已经看到 这种多路的搜索树，与我们此前的二路搜索树 并没有本质的区别，那么为什么还要引入B树呢？

B树的意义

在我们通常都是按多个层次来分级组织的存储系统中，如果使用B树可以针对我们此前所说的外部操作，大大降低IO访问的次数 从而极大的提高计算效率，那么难道我们前面学习过的的AVL树在这方面还不够么，我们不妨具体估算 考察某个由10的9次方 1G个记录的数据集，如果将它们组织为一棵AVL树 高度大致为30层，也就是说 在最坏的情况下 单次查找需要深入30层，而每一层我们都需要执行一次IO操作，那么B树又能如何呢，我们刚刚看到 B树中的超级节点同时包含多个而不是单个关键码，因此在B树中每下降一层 都可以超级节点为单位，读入一组而不是单个关键码，从而将外存批量访问的特点 转化为实在的优点。

那么这些超级节点具体的应该设计为多大呢，这取决于磁盘等外存本身所设定的数据缓冲页面的大小，通常的情况下 都是若干个KB，如果每个关键码通常取做4个字节的话，那么很自然的就应该将每个超级节点的规模设置为200至300之间。

比如若将超级节点的规模 取做256 也就是2的8次方，那么同样存放1G个记录的B树 高度不会超过4，这就意味着即便在最坏的情况下，单词查找所需进行的IO操作也同样不超过4次，或许到这里你会有一个疑问，难道4和30不都是可以视作常数吗，是的 就渐近的意义而言 的确如此，但是当这个常数的每一个单位都相当于10的5至6次方时，我们就不得不斤斤计较了，这就犹如虽然1秒和1天乃至1年 都可以视作是常数，但是对于有限的人生来说 却有本质的区别。

B树的定义

注: 不涉及复杂的数学公式计算

B 树又叫平衡多路查找树。一颗m阶的B 树的特性如下**：

• 每一个超级节点 最多有 m 个子节点
• 每一个超级节点最多有 m-1 个关键码
• 除根节点外，其于每个非叶子点至少有⌈m/2⌉ （上取整）个子节点（每个节点中的关键码至少⌈m/2⌉-1个）
• 根节点至少有两颗子树（除非B树只包含一个节点）
• 所有的叶子节点都在同一层

注：上面的节点 都指的是超级节点（包含一个或多个关键码的节点，而不是指关键码）

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

图示说明

为了方便画图，我们省略外部节点，同时超级节点的边框进行省略，如果超级节点中有多个关键码，那么每个关键码之间用水平有向箭头进行连接，同时每个关键码的左右孩子均画出来（这个和网上大部分的图示不太一样，为了方便，很多图中都是把相邻关键码的左右孩子进行合并，这样图更加干净，这里我就不省略了，所以树结构看起来可能稍微有点”乱”），下面是实例的B树图示展示:

注：对于下面说的节点，指的是超级节点，那怕该超级节点只有一个元素，对于超级节点中的元素，我们称为元素或者关键码。

B树的查找

B树的搜索和二叉搜索树类似。从根节点开始，从上到下递归的遍历树。在每一层上，搜索的范围被减小到包含了搜索值的子树中。子树值的范围被它的父节点的键确定。

比如 对于上面图示中查找元素40，首先从根（25）开始比较，发现40>25，进入25的右子树（34），同样的40>34,进行超级节点内部的比较，发现40B树的插入

先来看例子，在例子中来总结

初始B树

从零构建B树，需要很多的图进行展示，而这些并不是太有意义，所以这里我们直接从一个构建好的B树进行插入操作。

我们定义这是一颗3阶B树，即m=4，每个超级节点（内部节点）中的关键码个数不超过3，每个非叶子点至少有2个子节点。

简单插入

插入元素 5

这种插入很简单，超级节点 7 拥有的关键码的数量小于3，那么可以直接将新元素插入到这个节点中，同时对于超级节点内部，我们用单向箭头连接每个关键码（元素）。

插入元素 20

同样的，这个过程也很简单，对于19所在的超级节点，关键码数量小于3， 插入到超级节点中。

插入-上溢

对于这部分，插入元素后，会破坏B树的定义，需要进行相应的调整

插入元素 24

插入元素24后，对于24所在的超级节点，其内部的关键码为4，超过了3阶B树的上限，”超载”了，所以我们需要进行调整。

我们需要将该超级节点进分裂，我们先来看看调整后的图：

我们把元素24所在的超级节点中 相对中间位置的元素的22 提升到了父节点，然后该超级节点一分为二，元素22的左孩子指向其比自身小的子节点，右孩子指向比自身大的子节点。

经过这样的调整后搜索树满足B树的定义，所以此时的B树是平衡的。

插入元素 42

同样的，插入元素42后，其所在的超级节点”超载”了，我们同样按照上面的方法进行调整：

当我们把插入元素所在的超级节点进行分裂后，把元素41提升到父节点，虽然这个时候插入的超级节点平衡了，但是这个时候父节点又”超载”了,没办法，我们还得向上继续调整，同样的策略调整父节点：

幸运的是，当我们再次调整过后，整颗树中的节点，都没有”超载”了,本次插入操作结束了。

此外有可能我们会遇到糟糕的情况，一直到调整到根节点的情况，提升元素到根节点后，根节点”超载”，此时我们需要调整根节点，提升元素到最上层，此时新提升的元素变成新的根，此时这颗B树的高度增加了1. 这里就不再展示了，感兴趣的读者可以自己去try try。

到这里插入终于讲完了，从这些示例中，你总结出什么了吗？

插入总结

经过上面的步骤，现在我们再来总结整个插入过程：

所有的插入都从叶子节点开始。要插入一个新的元素，首先搜索这棵树找到新元素应该被添加到的叶子节点。将新元素插入到这一节点中的步骤如下：

1. 如果超级节点拥有的关键码的数量小于最大值，那么有空间容纳新的元素。将新元素插入到这一节点，且保持节点中元素有序。
2. 否则的话这一节点已经满了，将它平均地分裂成两个节点：
   1. 从叶子节点的元素和新的元素中选择出相对中间的元素
   2. 小于这个中间数的元素放入左边节点，大于这一中位数的元素放入右边节点，中间树作为分隔值。
   3. 分隔值被插入到父节点中，这可能会造成父节点分裂，分裂父节点时可能又会使它的父节点分裂，以此类推。如果没有父节点（这一节点是根节点），就创建一个新的根节点（增加了树的高度）。

如果分裂一直上升到根节点，那么一个新的根节点会被创建，它有一个分隔值和两个子节点。这就是根节点并不像内部节点一样有最少子节点数量限制的原因。

B树的删除

同样的，我们先通过图来展示这一过程，这里我们采用6阶B树，每个超级节点最多5个关键码，对于非叶子节点，至少3个孩子节点。

对于删除元素来说，存在删除叶子节点中的元素和非叶子节点中的元素两种情况，我们先来讨论删除叶子节点中元素的情况。

初始B树

我们采用前面插入操作过后的B树作为现在删除操作的初始树。

删除叶子元素

删除元素 5

删除元素5,其所在的超级节点还有两个元素，此时父超级节点仍然有三个孩子，满足6阶B树要求，不需要调整。

删除元素 6

删除元素6后，其超级节点就只有一个关键码了，不满足6阶B树约束的调节了，需要调整，我们知道6阶B树要求非叶子节点至少有两个关键码（6/2-1），我们观察超级节点6的兄弟节点，其还有三个关键码，这个相对来说是比较”富裕”的，在其它平衡树中，我们接触最多的词就是旋转，没错，这里的处理手法也是一样的，我们看看处理后的图：

左旋转，是的，观察关键码 7,13,19，我们发现他们似乎向左进行了旋转，旋转后，元素13下移一层，元素19上升了一层，经过这样操作后，搜索树的性质是不会变的。

这样我们相当于借用了被删除元素 右兄弟节点中的一个元素，这样让B树就保持平衡了。

删除元素 42

同样的，删除元素42后，其所在的超级节点只有一个关键码了，不满足约束条件，与前面类似的，其左兄弟节点还有富裕的元素，因此我们也可以借用一下。

右旋转， 这样一调整后，B树就再次平衡了，看到这里，也许有人就有疑问了，为什么选择提升元素40到父节点（右旋转），而不是提升元素35。同样，在前面提升元素19到父节点，而不是元素20。

其实如果对搜索树（排序树）很熟悉的话，其实这个是很显而易见的，在搜索树中，某个节点的左子树的元素一定大于其本身，其右子树一定小于其本身，在这里，既然我们要把左子树的元素提升到父节点，那么提升后的元素应该大于其左分支，也就是说，提升的元素，要是以前节点中最大的一个，那当然就是超节点中的最后一个咯（超级节点内部是有序的），同理也可以知道为什么提升19而不是20了，这个很简单，想想就明白了。

删除元素 37

删除元素37，其所在节点只有一个关键码了，不平衡，这个节点的右兄弟节点，只有两个关键码，这个是没法借了，现在该怎么办呢？，我们先看结果:

我们把子节点和父节点进行了合并，想想其实是有道理的，现在被删除的超级节点中的关键码不满足要求，其兄弟节点中的关键码也不能借了，那我们就把左右节点合并然后再和父节点中的关键码进行合并，本来属于两个不同的分支，现在要合并，那么肯定需要从父节点下移一个关键码，相当于桥梁，这样才符合搜索的要求。

但是现在我们看到，父节点下移一个关键码后，其自身只有一个关键码了，这个肯定是不符合6阶B树的要求了，现在的策略和我们刚刚执行的一样，继续向上合并。

经过再次合并过后，B树终于平衡了，而且我们看到B树的高度也减1了。

删除内部节点中元素

现在我们看看非叶子节点中删除关键码的情况

删除元素 22

删除元素22后，其所在的超级节点中关键码的个数为2，满足条件，B树是平衡的，但是我们看到这个时候元素22的孩子节点怎么处理呢？

删除了关键码22后，B树是平衡的，此时该关键码有左右孩子，那么可以从其孩子中找一个替代的关键码（左子树中最大的元素或右子树中最小的元素），这个和二叉搜索树中的删除是一样的原理，这里就不多讲了。

这里我们找了右子树中最小的元素23来替代被删除的关键码。仔细观察，我们发现出现了一个新问题，元素24所在的节点只有一个关键码了，这个是不符合6阶B的要求的，这个是可能出现的，当然，如果我们运气好，元素24所在的节点包含的关键码足够的多（这里不超过上限5个），那么就不会出现这种情况，那皆大欢喜，B树平衡，不用调整了。

但是如果出现这种情况，又该怎么办呢，这个我们在前面删除叶子元素的时候已经遇到过了，无非就是能借则借，不能借就合并，这里显然是不能借的了，只有合并了，下面是合并后的结果：

对于我们这里这种情况，虽然父节点中有元素下移了，但是并不会导致父节点失衡（想想为什么哟）

删除元素 41

这个其实和前面的情况是差不多的，不过有细微的不同，同样的，我们需要在元素41的左右子树中找到替代元素，如果我们找右子树最小的元素42，那么经过替换后，发现45元素所在的节点只包含一个关键码了，这种情况和上面一样，需要合并，如果我们选择左子树最大的元素40，那么经过替换操作后，B树依然是平衡的，而不需要再进行任何调整操作了（发现了什么吗）。

到这里删除终于讲完了，从这些示例中，你又总结出什么了吗？

删除总结

有两种常用的删除策略

1. 定位并删除元素，然后调整树使它满足约束条件； 或者
2. 从上到下处理这棵树，在进入一个节点之前，调整树使得之后一旦遇到了要删除的键，它可以被直接删除而不需要再进行调整

以下的算法使用了前一种策略。

删除叶子节点中的元素

1. 搜索要删除的元素
2. 如果它在叶子节点，将它从中删除
3. 如果发生了下溢（关键码低于下限），按照后边 “删除后重新平衡”部分的描述重新调整树

删除内部节点中的元素

节点中的每一个元素都作为分隔两颗子树的分隔值，因此我们需要重新划分。值得注意的是左子树中最大的元素仍然小于分隔值。同样的，右子树中最小的元素仍然大于分隔值。这两个元素都在叶子节点中，并且任何一个都可以作为两颗子树的新分隔值。算法的描述如下：

1. 选择一个新的关键码（左子树中最大的元素或右子树中最小的元素），将它从叶子节点中移除，替换掉被删除的元素作为新的关键码。
2. 前一步删除了一个叶子节点中的元素。如果这个叶子节点拥有的元素数量小于最低要求，那么从这一叶子节点开始重新进行平衡。

删除后的重新平衡

重新平衡从叶子节点开始向根节点进行，直到树重新平衡。如果删除节点中的一个元素使该节点的元素数量低于最小值，那么一些元素必须被重新分配。通常，移动一个元素数量大于最小值的兄弟节点中的元素。如果兄弟节点都没有多余的元素，那么缺少元素的节点就必须要和他的兄弟节点 合并。合并可能导致父节点失去了关键码，所以父节点可能缺少元素并需要重新平衡。合并和重新平衡可能一直进行到根节点，根节点变成惟一缺少元素的节点。重新平衡树的算法如下：

• 如果缺少元素节点的右兄弟存在且拥有多余的元素，那么向左旋转
  1. 将父节点的关键码复制到缺少元素节点的最后（关键码被移下来；缺少元素的节点现在有最小数量的元素）
  2. 将父节点的关键码替换为右兄弟的第一个元素（右兄弟失去了一个节点但仍然拥有最小数量的元素）
  3. 树又重新平衡
• 否则，如果缺少元素节点的左兄弟存在且拥有多余的元素，那么向右旋转
  1. 将父节点的关键码复制到缺少元素节点的最后（关键码被移下来；缺少元素的节点现在有最小数量的元素）
  2. 将父节点的关键码替换为左兄弟的第一个元素（左兄弟失去了一个节点但仍然拥有最小数量的元素）
  3. 树又重新平衡
• 否则，如果它的两个直接兄弟节点都只有最小数量的元素，那么将它与一个直接兄弟节点以及父节点中它们的关键码合并（父节点中的某个关键码被移下来）
  1. 父节点中的某个关键码和子树合并后，父节点失去了一个元素
     • 如果父节点是根节点并且没有元素了，那么释放它并且让合并之后的节点成为新的根节点（树的深度减小）
     • 否则，如果父节点的元素数量小于最小值，重新平衡父节点

所谓B+树

所谓B+树，我也不知道是不是真的存在这样的称呼，我知道B树的一个变种，典型的就是mysql 的 InnoDB索引存储结构，因为本文重点不是Mysql 的索引，因此这里就简单提一下就可以了。

mysql 官方文档中其实有提及

1
2
3
4
5
6
7
8
9
10

Everyone has seen a B-tree and knows that the entries in the root page point to the leaf pages. (I indicate those pointers with vertical ‘

’ bars in the drawing.) But sometimes people miss the detail that leaf pages can also point to each other (I indicate those pointers with a horizontal two-way pointer ‘’ in the drawing). This feature allows InnoDB to navigate from leaf to leaf without having to back up to the root level. This is a sophistication which you won’t find in the classic B-tree, which is why InnoDB should perhaps be called a B+-tree instead.

这段文字描述了Mysql InnoDB索引的数据结构，在B树的基础上进行了变形。

对于叶子节点，超级节点之间双向连接，这样叶子节点就构成了一个双向链表，这样将会更加方便的查找，关于Mysql 索引部分，后面会写，这里就点到为止了。

结语

终于把B树画完了，B树的一个关键知识点就在于 在原来二叉搜索树的基础上，把但个关键码合并成一个包含多个关键码的超级节点，通过这一改造过后，就可以很好的应用到磁盘存储方面，对于IO操作中的页或者块就间接的对于了B树中的一个或者多个超级节点，通过一次批量的读取，减少了I/O操作，同时根据局部性原理，也为预读功能提供了基础。

个人觉得B树的操作相比红黑树来说要简单很多，对于每一种情况，这个其实是比较容易想到的。

参考

B+ tree -维基百科

http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html

Rudolf Bayer, Edward M. McCreight-Organization and Maintenance of Large Ordered Indices

MySQL Internals Manual

数据结构（C++版）–邓俊辉