B树和B+树

第一节 B树

1.1 什么是B树

B树是一种自平衡的树，能够保持数据有序。保证查找数据、顺序访问、插入数据、删除等操作都能在对数时间内完成。

B树也属于二叉查找树，一个节点允许拥有两个以上的子节点。与平衡二叉树不同的是，B树适用于读写相对较大的数据块的存储系统，如磁盘。

B树减少定位记录时所经历的中间过程，从而加快存取速度。

2-3树、红黑树都是常见的B树。

1.2 应用场景

B树这种数据结构可以用来描述外部存储。常被应用在数据库和文件系统的实现上。

1.3 描述

几个定义：

• 内部节点：内部节点是除叶子节点和根节点之外的所有节点。它们通常被表示为一组有序的元素和指向子节点的指针。
• 根节点：根节点拥有的子节点数量的上限和内部节点相同，但是没有下限。
• 叶子节点：叶子节点对元素的数量有相同的限制，但是没有子节点，也没有指向子节点的指针。

B树的内部结点（非叶子）可以拥有可变数量的子结点。因为子结点可变数量这一特性，B树不需要像其他平衡二叉树那样频繁的进行重新保持平衡的操作，但相应的也造成了空间浪费（以空间换时间）。

子节点数量的上界和下界依特定的实现而设置。例如，在一个2-3 B树（通常简称2-3树），每一个内部节点只能有2或3个子节点。

1.4 操作

（1）搜索

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

（2）插入

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

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

（3）删除叶子节点中的元素

1. 搜索要删除的元素。
2. 如果它在叶子节点，将它从中删除。
3. 如果发生了下溢出，按照后面删除后重新平衡部分的描述重新调整树。

（4）删除内部节点中的元素

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

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

（5）删除后的重新平衡

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

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

1.5 变体

B树在内部结点上存储键值，但不需要在叶子结点上存储这些键值的记录。

• B+树：
  • 这些键值的拷贝被存储在内部结点；
  • 键值和记录存储在叶子结点；
  • 一个叶子结点可以包含一个指针，指向另一个叶子结点以加速顺序存取。
• B*树：分支出更多的内部邻居节点以保持内部节点更密集地填充。此变体要求非根节点至少2/3填充，而不是1/2。为了维持这样的结构，当一个节点填满之后将不会再立即分割节点，而是将它的键值与下一个节点共享。当两个节点都填满之后，分割成3个节点。
• 计数B树存储，每一树都带有一个指针和其指向子树的节点数目。这就允许了以键值为序快速查找第N笔记录，或是统计2笔记录之间的记录数目，还有其他很多相关的操作。

1.6 B树与平衡二叉树的区别

平衡二叉树通常是指查找路径只有两种（即只有二叉），而B树则不仅仅二叉，所以也叫平衡多路查找树。

B树相比平衡二叉树在每个结点所包含的内容更多，在应用到数据库中的时候，充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把结点大小限制和充分使用在磁盘块大小范围。所以树的结点能包含更多的内容后，树的层级比原来的二叉树少了，就可以减少数据查找的次数和复杂度。

---

第二节 B+树

2.1 什么是B+树

B+ 树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。

B+ 树在节点访问时间远远超过节点内部访问时间的时候，比其他可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。

B+ 背后的设计思想是内部节点可以有在预定范围内的可变量目的子节点。因此，B+ 树不需要像其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。

B+ 树的创造者 Rudolf Bayer 没有解释 B 代表什么。最常见的观点是 B 代表平衡(balanced)，因为所有的叶子节点在树中都在相同的级别上。B 也可能代表 Bayer，或者是波音（Boeing），因为他曾经工作于波音科学研究实验室。

如下图，把键 1-7 连接到值 d1-d7 的B+树。链表（红色）用于快速顺序遍历叶子节点。树的分叉因子 b=4 。

2.2 节点结构

在B+树中的节点通常被表示为一组有序的元素和子指针。如果此B+树的阶数是 m ，则除了根之外的每个节点都包含最少 m/2 个元素最多 m-1 个元素，对于任意的结点有最多 m 个子指针。对于所有内部节点，子指针的数目总是比元素的数目多一个。所有叶子都在相同的高度上，叶结点本身按关键字大小从小到大链接。

如下图所示，非叶子结点的关键字不保存数据，只用来索引，所有数据都保存在叶子节点。所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

2.3 算法

2.3.1 查找

查找以典型的方式进行，类似于二叉查找树。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用是二分查找来确定这个位置。

2.3.2 插入

节点要处于违规状态，它必须包含在可接受范围之外数目的元素。

1. 首先，查找要插入其中的节点的位置。接着把值插入这个节点中。
2. 如果没有节点处于违规状态则处理结束。
3. 如果某个节点有过多元素，则把它分裂为两个节点，每个都有最小数目的元素。在树上递归向上继续这个处理直到到达根节点，如果根节点被分裂，则创建一个新根节点。为了使它工作，元素的最小和最大数目典型的必须选择为使最小数不小于最大数的一半。

2.3.3 删除

1. 首先，查找要删除的值。接着从包含它的节点中删除这个值。
2. 如果没有节点处于违规状态则处理结束。
3. 如果节点处于违规状态则有两种可能情况：
   1. 它的兄弟节点，就是同一个父节点的子节点，可以把一个或多个它的子节点转移到当前节点，而把它返回为合法状态。如果是这样，在更改父节点和两个兄弟节点的分离值之后处理结束。
   2. 它的兄弟节点由于处在低边界上而没有额外的子节点。在这种情况下把两个兄弟节点合并到一个单一的节点中，而且我们递归到父节点上，因为它被删除了一个子节点。持续这个处理直到当前节点是合法状态或者到达根节点，在其上根节点的子节点被合并而且合并后的节点成为新的根节点。

2.4 实例说明

假设B+树结点最多容纳存放3个键和4个指针， m = 3 为奇数，d = 1 ，叶子结点至少2个条目（d + 1），非叶子结点至少2个指针（d + 1），1个条目。

首先插入1：判断根结点为空直接放入。

接着连续插入3、5：根结点未满，连续放入。

接着插入7：此时根结点达到max，判断需要分裂：当节点元素数量大于m-1的时候，从中间元素分裂成左右两部分，中间元素分裂到父节点当做索引存储，当然本身中间元素还是分裂右边这一部分的，保证左小右大的规则。所以分裂成两个子结点，1和3下沉到左边，5和7下沉到右边，内部结点只保存索引，最底层叶子结点连成有序链表。

接着插入9：找到位置，还有空间，直接放入。

接着插入2：如上放入。

接着插入4：此时对应叶子结点已放满，需要再度分裂成两个结点，1和2保留在左结点，3和4则移到新结点，并将新结点首个元素指向父结点（此时父结点仍有空间）。

接着插入6：对应叶子结点同样已满，继续相同分裂操作，并将新结点首个元素指向父结点。

接着插入8：仍有空间，直接放入。

接着插入10：此时对应叶子结点已满，所以先分裂开，7和8保留，9和10生成新叶子结点，将新叶子结点首个元素指向父结点，此时父结点超过上限（已是根结点，递归向上分裂，直到根结点分裂，增加高度），所以根结点分裂，中间元素7成为新的根结点，左小右大，新的结构仍是稳定的。

接下来我们看B+树的删除操作：

首先删除9：查找9所在结点，把它删除，然后判断此时树状态，发现叶子结点违规：叶子结点至少2个条目（d + 1），非叶子结点至少2个指针（d + 1），1个条目。合并兄弟结点，10、11和12合并，此时父结点因为少了一个子结点违规，所以需要继续处理。（此处为何为9还未搞懂）

接着删除7：

接着删除8：

2.5 B+树的特点

1. B+树的非叶子结点不保存关键字记录的指针，只进行数据索引，这样可以使B+树每个非叶子结点所能保存的关键字数大大增加。
2. B+树叶子结点保存了父结点的所有关键字记录的指针，所有数据地址必须到叶子结点才能获取到，所以每次数据查询的次数都相同。
3. B+树叶子结点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
4. 非叶子节点的子节点数 = 关键字数，或者非叶节点的关键字数 = 子节点数 - 1，虽然他们数据排列结构不一样，但其原理还是一样的，Mysql 的B+树是用第一种方式实现。

2.6 B+树与B树的区别

1. B+树的层级更少：相较于B树，B+树的每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
2. B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
3. B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
4. B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

S.NO	B TREE	B+ TREE
1.	所有的内部和叶子结点都有数据指针	只有叶子结点有数据指针
2.	由于叶子结点上的所有键都不可用，所以搜索通常更费时	所有键都在叶节点上，因此搜索更快，更准确
3.	树中没有重复的键	允许重复的键，并且所有结点都存在于叶子上
4.	插入会花费更多时间，有时无法预测	插入更容易，结果始终相同
5.	内部结点的删除非常复杂，并且树必须进行大量转换	删除任何节点都很容易，因为所有结点都可以在叶子上找到
6.	叶子结点不存储为结构链表	叶子结点存储为结构链表
7.	没有多余的搜索键	可能存在多余的搜索键

2.7 B+树与B*树的区别

B*树是B+树的变种，相对于B+树他们的不同之处如下：

1. 首先是关键字个数限制问题，B+树初始化的关键字初始化个数是 cei(m/2) ，b* 树的初始化个数为cei(2/3*m) 。

2. B+树节点满时就会分裂，而B树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；

3. 在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；

---

参考：

🔗 B树-维基百科

🔗 B+树-维基百科

🔗 《算法 第4版》