敞开生长之旅！这是我参与「日新计划 12 月更文挑战」的第5天，点击查看活动详情

回望B树，展望红黑树

写在前面

文章摘要

1. B-Tree的概念和性质
2. B-Tree的查询
3. B-Tree的增加
4. B-Tree的删去

阅览准备

• 建议花10 ~ 15分钟阅览
• 本文说到的二叉查找树，引荐阅览：《二叉查找树的完结与剖析》
• 本文对B树的剖析，是为了后边的红黑树做准备的。相对来说较为轻松
• 剧透：已然要展望红黑树，那么重点了解 4阶B树

一、B-Tree的概念&性质

（1）概念

B树（英语：B-tree），是一种在计算机科学自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、次序拜访、插入数据及删去的动作，都在O(logn)内完结。B树，归纳来说是一个一般化的二叉查找树（binary search tree）一个节点能够具有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储体系，例如磁盘。B树减少定位记录时所经历的中心过程，然后加快存取速度。B树这种数据结构能够用来描绘外部存储。这种数据结构常被应用在数据库和文件体系的完结上。

• B树是一种平衡的多路查找树
• 多用于文件体系、数据库的完结

• 如上有一颗B-Tree
• 其中 1 个节点能够存储超越 2 个元素、而且能够具有超越2个子节点
• 是一棵一般化的二叉查找树，具有二叉查找树的一些性质
• 非常平衡，每一节点的所有子树高度共同，而且较矮

（2）性质

• 有一棵 m 阶 B树（m ≥ 2），设一个节点存储的元素数量为 x。如果有子节点，设个数为 y 。那么，能够得出以下的定论：
  • 根节点：(1 ≤ x ≤ m - 1)、(2 ≤ y ≤ m)
  • 非根节点：(┍ m/2 ┑ - 1 ≤ x ≤ m - 1)、(┍ m/2 ┑ ≤ y ≤ m)
    • p.s：┍ x ┑表明对 x 向上取整（如：x = 2.1 => ┍ x ┑ = 3）
  • eg：非根节点
    • m = 3，2 ≤ y ≤ 3，1 ≤ x ≤ 2，可称为 (2, 3)树、2-3树
    • m = 4，2 ≤ y ≤ 4，1 ≤ x ≤ 3，可称为 (2, 4)树、2-3-4树
    • m = 5，3 ≤ y ≤ 5，2 ≤ x ≤ 4，可称为(3, 5)树、2-3-4-5树
    • …..

• 如果m = 2 呢？
• 如下图，二阶B树，其实便是一棵二叉查找树

• 定义中说：B树在逻辑上也是一棵二叉查找树
• 如果是阶数为二阶的B树，会退化，完全等同于为一棵二叉查找树
• 那咱们能否将一棵二叉查找树，变成一棵 B树呢？
• 其实是能够的，先来看一个概念：
  • 某节点含有多个元素，而且能够有大于两个的子节点。咱们称这样的节点为超级节点
• 将二叉查找树的多代兼并，可获得一个超级节点
  • 2代兼并的超级节点，最多具有4个子节点，所以至少是4阶B树

• 依此类推
  • 3代兼并的超级节点，最多具有8个子节点，所以至少是8阶B树
  • n代兼并的超级节点，最多具有 2 ^ n个子节点，所以至少是2的n次方阶B树
• 反推取对数可得：m阶B树，最多需求log2 m次兼并

二、B-Tree的查找

• 因为B树逻辑上与二叉查找树等价，在B树中查找元素，也是去比较节点大小。再持续寻找：
  • ①先在节点的内部从小到大开始查找元素
  • 如果找到，查找结束
  • ②如果未找到，再去对应的子节点中查找元素，重复步骤①

• 如图，咱们想要在这一棵4阶B树中，查找元素 15
• 从根节点（5、14、22）开始查找，发现 15 应该介于 14 和 22 之间
• 所以找到子节点（18），发现 15 应该在 18 的左面
• 所以找到子节点（15），返回成果

三、B-Tree的增加

• 新增加的元素必定是增加在叶子节点中
• 如下图，增加了元素：12 和 35

• 直接查找到应该放置的叶子节点，将其插入即可
• 应该很清晰，如果再增加一个元素31，会发生什么呢？

• 要是不知道B树的性质，是不是感觉也没问题，那要是知道B树的性质呢？
• 咱们会发现，增加后，右下角的节点中存在了4个元素，而4阶B树单个节点最多能包容 3 个元素
• 现已溢出了一个元素，咱们得将其修正。而这样的现象被称为：上溢（overflow）

上溢的处理

• 增加完结时，呈现了上溢节点，那么该节点的元素个数必定为 m（m为阶数）
• 且假设该节点最中心元素的方位为 k，则处理方案是：
  • 将k方位的元素向上与父节点兼并
  • 将[0, k-1] 和 [k+1, m-1]方位的元素分裂成2个子节点
• 如下图所示

• 如果m是偶数，那么上溢节点中的元素个数也是偶数，中心 k 可选的方位也会有2个，如上面就能够选择 32、35
• 咱们这里令k = 1，将其方位的元素取出来，将它上移到父节点中，变成：（25、30、32）
• 再将它[0, 0]和 [2, 3]方位的元素分裂为两个子节点（31）和（35、38）
• 经过上面的操作，现已没有上溢节点了
• 那咱们再增加 40 和 50 ，看看会有什么问题

• 也呈现了上溢节点，但再看到上溢节点，应该不会紧张了吧！那咱们再一起来处理上溢~

• 按照刚刚的思路处理完上溢，一开始呈现的上溢的节点确实没有问题了
• 可是咱们发现，向上兼并时，导致父节点也呈现了上溢现象
• 怎么办呢？持续处理呗~

• 这一次增加元素时，咱们发现一个现象：处理完上溢后，可能会导致父节点也上溢
• 最坏的状况便是像上图所示：一向上溢到了根节点
• 根节点的上溢被处理后，发现树长高了。是的，这是仅有会使 B 树长高的状况
• 可是好在，呈现这么多次上溢节点，处理上溢的思路都是共同的~

四、B-Tree的删去

• 之前二叉查找树的删去，思路是依据节点的度不同分类评论其删去的方式
• 那B树呢？其实也差不多，咱们先来看看删去的元素在叶子节点中
• 如下图，咱们想要删去 50

• 能够看到，50在叶子节点（40、50）中，直接删去即可
• 那咱们看看如果删去的对错叶子节点中的元素 14 呢？

• 能够发现，其实和二叉查找树中，删去度为 2 的节点差不多
• 思路是：
  • 先找到待删去元素所在节点的前驱或后继节点
  • 将其节点中最大或最小的元素赋值给待删去的元素
  • 最后删去前驱或后继中用来赋值的元素即可
• 而B树的前驱或后继节点，必定是叶子节点。 而删去叶子节点中的元素，就能够直接删去了
• 那再来看几种状况。为了方便描绘状况，咱们假设有一棵5阶B树

• 删去元素30，会发生什么呢？

• 发现30在叶子节点中，按刚刚的逻辑，直接将其元素删去。的确如此，这一步操作没问题
• 可是这是 5 阶 子树哎，有必要满意：┍ m/2 ┑ - 1 ≤ 非根节点中元素数量 ≤ m - 1，也便是元素数量有必要归于 [2, 4]中
• 而在上图中，咱们将节点（30，32）的 30 删去了。此节点变成了（32），元素数量为1，现已 低于最少元素数量的个数了。这种状况被称为：下溢（underflow）
• 那么怎么处理下溢呢？

下溢的处理

• 删去完结时，呈现了下溢节点，那么它必定满意：元素个数 == ┍ m/2 ┑ - 2（m为阶数）
• 如果当下溢节点的接近兄弟节点中的元素个数，最少为┍ m/2 ┑时，能够向其借一个元素。（也便是兄弟节点给你一个元素，它也不会产生下溢。那么就能够向它借一个元素）
• 如处理上图的下溢状况

• 向兄弟节点借元素时。因为有大小关系，不能够直接拿过来，只能通过巧妙的交流
  • 将父节点中（28，34），元素28移动到下溢节点，使其变成（28，32）
  • 将能够借元素的接近兄弟节点（22，24，27）中的元素27，移动到父节点中，使其变成（27，34）
  • 即可处理下溢。听我这样一描绘，是不是发现，其实这便是在旋转啊~
  • 我上面的操作其实便是在右旋，因为接近可借用元素的兄弟节点在左面，如果在右边，那么左旋即可修正下溢节点
• 咱们刚刚一向在评论，呈现下溢时，能够向兄弟节点借用一个元素的状况，那如果没得借呢？

• 如上图所示，被删去元素的节点都没有接近的兄弟节点
• 别谈不够借了，是底子借不到，那又该怎么处理呢？

• 如图所示，删去节点（1，2）中的元素2，呈现了下溢现象，可它底子就没有接近的兄弟节点
• 那么处理的思路是：在父节点中取出一个元素，向下与兄弟节点兼并（如果有兄弟节点）
• 在这里，兼并完结后确实修正了之前的下溢节点
• 与增加呈现上溢类似，又呈现了新的下溢节点，最坏的状况如上图所示：会一向下溢到根节点
• 刚刚说如果有兄弟节点，需求与兄弟节点一起兼并，也便是下面这种状况

• 如上图所示，有接近的兄弟节点，可是它没有多的元素借给下溢的兄弟节点
• 这时，需求从父节点中取出一个元素，将原先的下溢节点与它接近的兄弟节点兼并（如有多个不能外借的接近兄弟节点，只能兼并一个）
• 即可处理处理。若这样的操作使父节点也下溢了，重复上面的思路，依次处理即可
• 如果根节点的下一层呈现了下溢节点。当下溢节点悉数被修正，从头平衡时，该树整体的高度会减1
• 这也是仅有能使B树变矮的操作了

写在后边

本篇收获

1. 开始了解了B树
2. B树增加元素时，呈现上溢现象的处理方案
3. B树删去元素时，呈现下溢现象的处理方案

读后思考

• 心里有了B树，真的对红黑树有用吗？有什么用呢？又怎么用呢？
• 随机给定一组元素，来构建4阶B树，该怎么操作呢？
• 再将他们依次删去呢，又该怎么操作呢？